【正文】 eg(v1)＝ 1； deg(v2)＝ 3， deg+(v2)＝ 2， deg(v2)＝ 1； deg(v3)＝ 5， deg+(v3)＝ 2， deg(v3)＝ 3； deg(v4)＝ 1， deg+(v4)＝ 0， deg(v4)＝ 1； deg(v5)＝ deg+(v5)＝ deg(v5)＝ 0； v3 v2 v1 v5 v4 2022/2/13 計(jì)算機(jī)學(xué)院 26/172 例 deg(v1)＝ 3， deg+(v1)＝ 2， deg(v1)＝ 1； deg(v2)＝ 3， deg+(v2)＝ 2， deg(v2)＝ 1； deg(v3)＝ 5， deg+(v3)＝ 2， deg(v3)＝ 3； deg(v4)＝ 1， deg+(v4)＝ 0， deg(v4)＝ 1； deg(v5)＝ deg+(v5)＝ deg(v5)＝ 0； v3 v2 v1 v5 v4 2022/2/13 計(jì)算機(jī)學(xué)院 27/172 例 deg(v1)＝ 3， deg+(v1)＝ 2， deg(v1)＝ 1； deg(v2)＝ 3， deg+(v2)＝ 2， deg(v2)＝ 1； deg(v3)＝ 5， deg+(v3)＝ 2， deg(v3)＝ 3； deg(v4)＝ 1， deg+(v4)＝ 0， deg(v4)＝ 1； deg(v5)＝ deg+(v5)＝ deg(v5)＝ 0； v3 v2 v1 v5 v4 2022/2/13 計(jì)算機(jī)學(xué)院 28/172 例 deg(v1)＝ 3， deg+(v1)＝ 2， deg(v1)＝ 1； deg(v2)＝ 3， deg+(v2)＝ 2， deg(v2)＝ 1； deg(v3)＝ 5， deg+(v3)＝ 2， deg(v3)＝ 3； deg(v4)＝ 1， deg+(v4)＝ 0， deg(v4)＝ 1； deg(v5)＝ deg+(v5)＝ deg(v5)＝ 0； v3 v2 v1 v5 v4 2022/2/13 計(jì)算機(jī)學(xué)院 29/172 例 deg(v1)＝ 3， deg+(v1)＝ 2， deg(v1)＝ 1； deg(v2)＝ 3， deg+(v2)＝ 2， deg(v2)＝ 1； deg(v3)＝ 5， deg+(v3)＝ 2， deg(v3)＝ 3； deg(v4)＝ 1， deg+(v4)＝ 0， deg(v4)＝ 1； deg(v5)＝ deg+(v5)＝ deg(v5)＝ 0； v3 v2 v1 v5 v4 2022/2/13 計(jì)算機(jī)學(xué)院 30/172 握手定理（ Euler,1736年） ? 定理 （ 握手定理 ） 對(duì)于任何 （ n,m） 圖 G =（ V，E） ， 所有結(jié)點(diǎn)的度數(shù)的總和等于邊數(shù)的兩倍 ， 即： 證明： 根據(jù)結(jié)點(diǎn)度數(shù)的定義 ， 在計(jì)算結(jié)點(diǎn)度數(shù)時(shí)每條邊對(duì)于它所關(guān)聯(lián)的結(jié)點(diǎn)被計(jì)算了兩次 ， 因此 ， G中結(jié)點(diǎn)度數(shù)的總和恰好為邊數(shù) m的 2倍 。 2022/2/13 計(jì)算機(jī)學(xué)院 24/172 3) 對(duì)于圖 G＝ V， E， 度數(shù)為 0的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；只由孤立結(jié)點(diǎn)構(gòu)成的圖 G=（ V， ?） 稱為零圖；只由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖稱為平凡圖； 4) 在圖 G＝ V， E中 ， 稱度數(shù)為奇數(shù)的結(jié)點(diǎn)為奇度數(shù)結(jié)點(diǎn) ， 度數(shù)為偶數(shù)的結(jié)點(diǎn)為偶度數(shù)結(jié)點(diǎn) 。 2022/2/13 計(jì)算機(jī)學(xué)院 23/172 3) 對(duì)于圖 G＝ V， E， 度數(shù)為 0的結(jié)點(diǎn)稱為孤立結(jié)點(diǎn)；只由孤立結(jié)點(diǎn)構(gòu)成的圖 G=（ V， ?） 稱為零圖；只由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖稱為平凡圖； 4) 在圖 G＝ V， E中 ， 稱度數(shù)為奇數(shù)的結(jié)點(diǎn)為 奇度數(shù)結(jié)點(diǎn) ， 度數(shù)為偶數(shù)的結(jié)點(diǎn)為 偶度數(shù)結(jié)點(diǎn) 。 2) 在 有向圖 G＝ V， E中 ， 以結(jié)點(diǎn) v為始點(diǎn)引出的邊的條數(shù) ， 稱為該結(jié)點(diǎn)的 出度 ,記為 deg+(v)；以結(jié)點(diǎn) v為終點(diǎn)引入的邊的條數(shù) ， 稱為該結(jié)點(diǎn)的 入度 ,記為 deg(v)；而結(jié)點(diǎn)的引出度數(shù)和引入度數(shù)之和稱為該結(jié)點(diǎn)的 度數(shù) ， 記為 deg(v)，即 deg(v)＝ deg+(v)+deg(v)； 2022/2/13 計(jì)算機(jī)學(xué)院 22/172 3) 對(duì)于圖 G＝ V， E， 度數(shù)為 0的結(jié)點(diǎn)稱為 孤立結(jié)點(diǎn) ；只由孤立結(jié)點(diǎn)構(gòu)成的圖 G=（ V， ?） 稱為零圖； 只由一個(gè)孤立結(jié)點(diǎn)構(gòu)成的圖稱為 平凡圖； 4) 在圖 G＝ V， E中 ， 稱度數(shù)為奇數(shù)的結(jié)點(diǎn)為奇度數(shù)結(jié)點(diǎn) ， 度數(shù)為偶數(shù)的結(jié)點(diǎn)為偶度數(shù)結(jié)點(diǎn) 。 v3 v2 v1 v4 5 6 6 7 8 7 9 5 G1 2022/2/13 計(jì)算機(jī)學(xué)院 20/172 結(jié)點(diǎn)的度數(shù) 1) 在 無向圖 G＝ V， E中 ， 與結(jié)點(diǎn) v(v?V)關(guān)聯(lián)的邊的條數(shù) （ 有環(huán)時(shí)計(jì)算兩次 ） ， 稱為該結(jié)點(diǎn)的度數(shù) ， 記為 deg(v)；最大點(diǎn)度和最小點(diǎn)度分別記為 ?和 ?。 2022/2/13 計(jì)算機(jī)學(xué)院 19/172 圖的分類 (按權(quán) ) ? 賦權(quán)圖 G是一個(gè)三重組 V,E,g， 其中 V是結(jié)點(diǎn)集合 ，E是邊的集合 ， g是邊 E上的權(quán)值 。 2) 在無向圖中 ， 兩個(gè)結(jié)點(diǎn)間 (包括結(jié)點(diǎn)自身間 )若有幾條邊 ， 則這幾條邊稱為平行邊； 3) 含有平行邊的圖稱為多重圖； 4) 含有環(huán)的多重圖稱為廣義圖 （ 偽圖 ） ； 5) 滿足定義 。 6) 將多重圖和廣義圖中的平行邊代之以一條邊 ， 去掉環(huán) ，可以得到一個(gè)簡(jiǎn)單圖 ， 稱為原來圖的基圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 17/172 圖的分類 (按邊的重?cái)?shù) ) 1) 在有向圖中 ， 兩個(gè)結(jié)點(diǎn)間 (包括結(jié)點(diǎn)自身間 )若有同始點(diǎn)和同終點(diǎn)的幾條邊 ， 則這幾條邊稱為平行邊 。 2) 在無向圖中 ， 兩個(gè)結(jié)點(diǎn)間 (包括結(jié)點(diǎn)自身間 )若有幾條邊 ， 則這幾條邊稱為 平行邊 ； 3) 含有平行邊的圖稱為多重圖； 4) 含有環(huán)的多重圖稱為廣義圖 （ 偽圖 ） ； 5) 滿足定義 。 ?用 小圓圈 表示 V中的 結(jié)點(diǎn) ， 用由 u指向 v的 有向線段 表示u,v， 無向線段 表示 (u,v)。 v是邊 e的終點(diǎn) ， 統(tǒng)稱為 e的端點(diǎn)； e是 u的出邊 ， 是 v的入邊 。 ?用小圓圈表示 V中的結(jié)點(diǎn)，用由 u指向 v的有向線段表示u,v，無向線段表示 (u,v)。 v是邊 e的終點(diǎn) ， 統(tǒng)稱為 e的端點(diǎn)； e是 u的出邊 ， 是 v的入邊 。 ?用小圓圈表示 V中的結(jié)點(diǎn)，用由 u指向 v的有向線段表示u,v，無向線段表示 (u,v)。 v是邊 e的 終點(diǎn) ， 統(tǒng)稱為 e的 端點(diǎn) ； e是 u的出邊 ， 是 v的入邊 。 ?用小圓圈表示 V中的結(jié)點(diǎn)，用由 u指向 v的有向線段表示u,v，無向線段表示 (u,v)。 v是邊 e的終點(diǎn) ， 統(tǒng)稱為 e的端點(diǎn)； e是 u的出邊 ， 是 v的入邊 。 3） 圖 G的結(jié)點(diǎn)數(shù)稱為 G的 階 ， 用 n表示 ， G的邊數(shù)用 m表示 ，也可表示成 ?(G)=m 。 3） 圖 G的結(jié)點(diǎn)數(shù)稱為 G的階 ， 用 n表示 ， G的邊數(shù)用 m表示 ，也可表示成 ?(G)=m 。 3） 圖 G的結(jié)點(diǎn)數(shù)稱為 G的階 ， 用 n表示 ， G的邊數(shù)用 m表示 ，也可表示成 ?(G)=m 。 ?與序偶不同 ， 無論 a,b是否相等 ， 均有： (a,b)＝ (b,a)。 圖的基本概念 ?無序積的定義：設(shè) A,B 為任意集合 ， 稱集合Aamp。 ?與序偶不同 ， 無論 a,b是否相等 ， 均有： (a,b)＝ (b,a)。 圖的基本概念 ?無序積的定義： 設(shè) A,B 為任意集合 ， 稱集合Aamp。陳瑜 Email： 13402838800 2022年 2月 13日星期日 2022/2/13 計(jì)算機(jī)學(xué)院 2/172 167。 圖的基本概念 2022/2/13 計(jì)算機(jī)學(xué)院 3/172 主要內(nèi)容 ? 圖的基本概念 ① 什么是圖 ② 圖的分類 ③ 結(jié)點(diǎn)的度數(shù) ④ 握手定理 ⑤ 子圖與補(bǔ)圖 ⑥ 完全圖 ⑦ 補(bǔ)圖 ⑧ 圖的同構(gòu) 2022/2/13 計(jì)算機(jī)學(xué)院 4/172 167。B ＝ {(a,b)|a∈A ， b∈B} 為 A 與 B 的 無序積 ， （ a,b ） 稱為 無序?qū)? 。 2022/2/13 計(jì)算機(jī)學(xué)院 5/172 167。B ＝ {(a,b)|a∈A ， b∈B} 為 A 與 B 的無序積 ， （ a,b ） 稱為無序?qū)? 。 2022/2/13 計(jì)算機(jī)學(xué)院 6/172 圖的定義 ? 定義 一個(gè) 圖 是一個(gè)序偶 V,E， 記為 G＝ V,E， 其中： 1） V（ G） ＝ {v1,v2,v3,… ,vn}是一個(gè)有限的非空集合 ，vi(i＝ 1,2,3,… ,n)稱為 結(jié)點(diǎn) ,簡(jiǎn)稱 點(diǎn) ， V為 結(jié)點(diǎn)集 ； 2） E（ G） ＝ {e1,e2,e3,… ,em}是一個(gè)有限的集合 ， ei(i＝ 1,2,3,… ,m)稱為邊 ， E為邊集 ， E中的每個(gè)元素都是由 V中不同結(jié)點(diǎn)所構(gòu)成的無序?qū)?， 且不含重復(fù)元素 。 2022/2/13 計(jì)算機(jī)學(xué)院 7/172 圖的定義 ? 定義 一個(gè) 圖 是一個(gè)序偶 V,E， 記為 G＝ V,E， 其中： 1） V（ G） ＝ {v1,v2,v3,… ,vn}是一個(gè)有限的非空集合 ，vi(i＝ 1,2,3,… ,n)稱為結(jié)點(diǎn) ,簡(jiǎn)稱點(diǎn) ， V為結(jié)點(diǎn)集； 2） E（ G） ＝ {e1,e2,e3,… ,em}是一個(gè)有限的集合 ， ei(i＝ 1,2,3,… ,m)稱為 邊 ， E為 邊集 ， E中的每個(gè)元素都是由 V中不同結(jié)點(diǎn)所構(gòu)成的無序?qū)?， 且不含重復(fù)元素 。 2022/2/13 計(jì)算機(jī)學(xué)院 8/172 圖的定義 ? 定義 一個(gè) 圖 是一個(gè)序偶 V,E， 記為 G＝ V,E， 其中： 1） V（ G） ＝ {v1,v2,v3,… ,vn}是一個(gè)有限的非空集合 ，vi(i＝ 1,2,3,… ,n)稱為結(jié)點(diǎn) ,簡(jiǎn)稱點(diǎn) ， V為結(jié)點(diǎn)集； 2） E（ G） ＝ {e1,e2,e3,… ,em}是一個(gè)有限的集合 ， ei(i＝ 1,2,3,… ,m)稱為邊 ， E為邊集 ， E中的每個(gè)元素都是由 V中不同結(jié)點(diǎn)所構(gòu)成的無序?qū)?， 且不含重復(fù)元素 。 2022/2/13 計(jì)算機(jī)學(xué)院 9/172 圖的分類 (按邊的方向 ) 1) 若邊 e與無序結(jié)點(diǎn)對(duì) (u， v)相對(duì)應(yīng) ， 則稱邊 e為 無向邊 ,記為 e＝ (u， v)， 這時(shí)稱 u， v是邊 e的兩個(gè) 端點(diǎn) ； 2) 若邊 e與有序結(jié)點(diǎn)對(duì) u， v相對(duì)應(yīng) ， 則稱邊 e為有向邊 ，記為 e＝ u， v， 這時(shí)稱 u是邊 e的始點(diǎn) 。 3) 每條邊都是無向邊的圖稱為無向圖； 4) 每條邊都是有向邊的圖稱為有向圖； 5) 有些邊是無向邊 ， 而另一些是有向邊的圖稱為混合圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 10/172 圖的分類 (按邊的方向 ) 1) 若邊 e與無序結(jié)點(diǎn)對(duì) (u， v)相對(duì)應(yīng) ， 則稱邊 e為無向邊 ,記為 e＝ (u， v)， 這時(shí)稱 u， v是邊 e的兩個(gè)端點(diǎn) ； 2) 若邊 e與有序結(jié)點(diǎn)對(duì) u， v相對(duì)應(yīng) ， 則稱邊 e為 有向邊 ，記為 e＝ u， v， 這時(shí)稱 u是邊 e的 始點(diǎn) 。 3) 每條邊都是無向邊的圖稱為無向圖； 4) 每條邊都是有向邊的圖稱為有向圖； 5) 有些邊是無向邊 ， 而另一些是有向邊的圖稱為混合圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 11/172 圖的分類 (按邊的方向 ) 1) 若邊 e與無序結(jié)點(diǎn)對(duì) (u， v)相對(duì)應(yīng) ， 則稱邊 e為無向邊 ,記為 e＝ (u， v)， 這時(shí)稱 u， v是邊 e的兩個(gè)端點(diǎn)； 2) 若邊 e與有序結(jié)點(diǎn)對(duì) u， v相對(duì)應(yīng) ， 則稱邊 e為有向邊 ，記為 e＝ u， v， 這時(shí)稱 u是邊 e的始點(diǎn) 。 3) 每條邊都是無向邊的圖稱為 無向圖 ； 4) 每條邊都是有向邊的圖稱為 有向圖 ； 5) 有些邊是無向邊 ， 而另一些是有向邊的圖稱為 混合圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 12/172 圖的分類 (按邊的方向 ) 1) 若邊 e與無序結(jié)點(diǎn)對(duì) (u， v)相對(duì)應(yīng) ， 則稱邊 e為無向邊 ,記為 e＝ (u， v)， 這時(shí)稱 u， v是邊 e的兩個(gè)端點(diǎn)； 2) 若邊 e與有序結(jié)點(diǎn)對(duì) u， v相對(duì)應(yīng) ， 則稱邊 e為有向邊 ，記為 e＝ u， v， 這時(shí)稱 u是邊 e的始點(diǎn) 。 3) 每條邊都是無向邊的圖稱為無向圖； 4) 每條邊都是有向邊的圖稱為有向圖； 5) 有些邊是無向邊 ， 而另一些是有向邊的圖稱為混合圖 。 2022/2/13 計(jì)算機(jī)學(xué)院 13/172 幾個(gè)概念 1) 在一個(gè)圖中 ， 關(guān)聯(lián)結(jié)點(diǎn) vi和 vj的邊 e， 無論是有向的還是無向的 ， 均稱邊 e與結(jié)點(diǎn) vI和 vj相關(guān)聯(lián) ， 而 vi和 vj稱為