【正文】 點(diǎn) 。 2022/2/13 計(jì)算機(jī)學(xué)院 7/63 圖的定義 ? 定義 一個(gè) 圖 是一個(gè)序偶 V,E， 記為 G＝ V,E， 其中： 1） V（ G） ＝ {v1,v2,v3,… ,vn}是一個(gè)有限的非空集合 ，vi(i＝ 1,2,3,… ,n)稱為結(jié)點(diǎ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é)院 6/63 圖的定義 ? 定義 一個(gè) 圖 是一個(gè)序偶 V,E， 記為 G＝ V,E， 其中： 1） V（ G） ＝ {v1,v2,v3,… ,vn}是一個(gè)有限的非空集合 ，vi(i＝ 1,2,3,… ,n)稱為結(jié)點(diǎ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é)院 5/63 圖的定義 ? 定義 一個(gè) 圖 是一個(gè)序偶 V,E， 記為 G＝ V,E， 其中： 1） V（ G） ＝ {v1,v2,v3,… ,vn}是一個(gè)有限的非空集合 ，vi(i＝ 1,2,3,… ,n)稱為 結(jié)點(diǎ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ù)元素 。B ＝ {(a,b)|a∈A ， b∈B} 為 A 與 B 的無序積 ， （ a,b ） 稱為無序?qū)? 。 2022/2/13 計(jì)算機(jī)學(xué)院 4/63 167。B ＝ {(a,b)|a∈A ， b∈B} 為 A 與 B 的 無序積 ， （ a,b ） 稱為 無序?qū)? 。陳瑜 Email： 13402838800 2022年 2月 13日星期日 2022/2/13 計(jì)算機(jī)學(xué)院 2/63 主要內(nèi)容 ? 圖的基本概念 ① 什么是圖 ② 圖的分類 ③ 結(jié)點(diǎn)的度數(shù) ④ 握手定理 ⑤ 子圖與補(bǔ)圖 ⑥ 完全圖 ⑦ 補(bǔ)圖 ⑧ 圖的同構(gòu) 2022/2/13 計(jì)算機(jī)學(xué)院 3/63 167。 圖的基本概念 ?無序積的定義： 設(shè) A,B 為任意集合 ， 稱集合Aamp。 ?與序偶不同 ， 無論 a,b是否相等 ， 均有： (a,b)＝ (b,a)。 圖的基本概念 ?無序積的定義：設(shè) A,B 為任意集合 ， 稱集合Aamp。 ?與序偶不同 ， 無論 a,b是否相等 ， 均有： (a,b)＝ (b,a)。 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 。 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的入邊 。 ?用 小圓圈 表示 V中的 結(jié)點(diǎn) ， 用由 u指向 v的 有向線段 表示u,v， 無向線段 表示 (u,v)。 2) 在無向圖中 ， 兩個(gè)結(jié)點(diǎn)間 (包括結(jié)點(diǎn)自身間 )若有幾條邊 ， 則這幾條邊稱為 平行邊 ； 3) 含有平行邊的圖稱為多重圖； 4) 含有環(huán)的多重圖稱為廣義圖 （ 偽圖 ） ； 5) 滿足定義 。 2022/2/13 計(jì)算機(jī)學(xué)院 16/63 圖的分類 (按邊的重?cái)?shù) ) 1) 在有向圖中 ， 兩個(gè)結(jié)點(diǎn)間 (包括結(jié)點(diǎn)自身間 )若有同始點(diǎn)和同終點(diǎn)的幾條邊 ， 則這幾條邊稱為平行邊 。 6) 將多重圖和廣義圖中的平行邊代之以一條邊 ， 去掉環(huán) ，可以得到一個(gè)簡單圖 ， 稱為原來圖的基圖 。 2) 在無向圖中 ， 兩個(gè)結(jié)點(diǎn)間 (包括結(jié)點(diǎn)自身間 )若有幾條邊 ， 則這幾條邊稱為平行邊； 3) 含有平行邊的圖稱為多重圖； 4) 含有環(huán)的多重圖稱為廣義圖 （ 偽圖 ） ； 5) 滿足定義 。 2022/2/13 計(jì)算機(jī)學(xué)院 18/63 圖的分類 (按權(quán) ) ? 賦權(quán)圖 G是一個(gè)三重組 V,E,g， 其中 V是結(jié)點(diǎn)集合 ，E是邊的集合 ， g是邊 E上的權(quán)值 。 v3 v2 v1 v4 5 6 6 7 8 7 9 5 G1 2022/2/13 計(jì)算機(jī)學(xué)院 19/63 結(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)度分別記為 ?和 ?。 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é)院 21/63 3) 對于圖 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é)院 22/63 3) 對于圖 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