【正文】 計(jì)算機(jī)科學(xué)廣泛應(yīng)用于運(yùn)籌學(xué) ， 信息論 ， 控制論 ， 網(wǎng)絡(luò)理論 ， 化學(xué)生物學(xué) ， 物理學(xué) 。 原因在于這些學(xué)科的許多實(shí)際問題和理論問題可以概括為圖論 。 第八 、 九章介紹與計(jì)算機(jī)科學(xué)關(guān)系密切的圖論內(nèi)容及其在實(shí)際中的應(yīng)用 。 無向圖及有向圖 稱 {{a,b} | a?A?b?B} 為 A與 B的無序積，記作： Aamp。B。 習(xí)慣上，無序?qū)?{a,b}改記成 (a, b) 有序組 (a,b)均用 a,b 無序積 ： 設(shè) A， B為二集合， 一、基本圖類及相關(guān)概念 1. 無向圖 無向圖 ： 無向圖 G是一個(gè)二元組 V,E ， 其中 (1) V是一個(gè)非空集 ––– 頂點(diǎn)集 V(G)， 每個(gè)元素為 頂點(diǎn)或結(jié)點(diǎn) ； (2) E是無序積 V amp。 V的 可重子集 (元素可重復(fù)出現(xiàn) )， E ––– 邊集 E(G)， E中元素稱為 無向邊 。 v4 實(shí)際中，圖是畫出來的，畫法：用小圓圈表示 V中的每一個(gè)元素，如果 (a,b)?E， 則在頂點(diǎn) a與 b之間連線段。 如： a d c b e1 e1 e2 e3 e4 e5 e6 e1 e2 e3 e4 e5 e6 v1 v2 v3 v5 有向圖 ： 有向圖 D是一個(gè)二元組 V,E ， 其中 (1) V是非空集 ––– 頂點(diǎn)集 V(D) (2) E是笛卡爾積 V?V的可重子集，其元素為有向邊 實(shí)際中 ， 畫法同無向圖 ， 只是要根據(jù) E中元素的次序 ， 由第一元素用方向線段指向第二元素 。 2. 有向圖 有限圖 ： V， E均為有窮集合 零 圖 ： E ? ? 平凡圖 ： E ? ? 且 |V| = 1 (n, m)圖 ： |V| = n 且 |E| = m 頂與邊關(guān)聯(lián) ： 如果 ek = (vi,vj) ?E， 稱 ek與 vi關(guān)聯(lián) ，或 ek與 vj關(guān)聯(lián) 。 3. 相關(guān)概念 頂與頂相鄰 ： 如果 ek = (vi,vj) ?E， 稱 vi與 vj相鄰； 環(huán) ： ek = vi,vj 中，若 vi = vj， 則 ek稱為環(huán)。 邊與邊相鄰 ： 如果 ek和 ei至少有一個(gè)公共頂點(diǎn)關(guān)聯(lián)，則稱 ek與 ei相鄰 。 若 ek為有向邊，則稱 vi鄰接到 vj, vj鄰接于 vi 。 孤立點(diǎn) ： 無邊關(guān)聯(lián)的頂點(diǎn)。 平行邊 ： 無向圖中，關(guān)聯(lián)一對(duì)結(jié)點(diǎn)的無向邊多于一條，平行邊的條數(shù)為 重?cái)?shù) ； 多重圖 ： 包含平行邊的圖。 有向圖中，關(guān)聯(lián)一對(duì)頂點(diǎn)的無向邊多于一條，且始、終點(diǎn)相同。 簡(jiǎn)單圖 ： 既不包含平行邊又不包含環(huán)的圖。 度 ： (1) 在無向圖 G = V, E 中，與頂點(diǎn) v(v?V)關(guān)聯(lián)的邊的數(shù)目 (每個(gè)環(huán)計(jì)算兩次 )，記作： d(v)。 二、度 (2) 在有向圖 D = V,E 中，以頂點(diǎn) v(v?V)作為始點(diǎn)的邊的數(shù)目，稱為該頂點(diǎn)的 出度 ，記作： d+(v)； 出度與入度之和，稱為頂點(diǎn) v的度： 度是圖的性質(zhì)的重要判斷依據(jù)。 d(v) = d+(v)+ d–(v) 以頂點(diǎn) v作為終點(diǎn)的邊的數(shù)目，稱為該頂點(diǎn)的 入度 ，記作： d–(v)。 最大度 ： ? (G) = max {d(v) | v?V} 最小度 ： ? (G) = min {d(v) | v?V} 度與邊數(shù)的關(guān)系 ： 在任何圖中，頂點(diǎn)度數(shù)的總和等于邊數(shù)之和的兩倍。 ???Vv||2)( Evd即握手定理的推論 ： 任何圖中，度為奇數(shù)的頂點(diǎn)個(gè)數(shù)一定為偶數(shù)。 (握手定理 ) 出度與入度的關(guān)系 ： 在有向圖中，各頂點(diǎn)的出度之和等于各頂點(diǎn)的入度之和。 度數(shù)序列 ： 設(shè) V = {v1,v2,…, vn}為圖 G的頂點(diǎn)集， 稱 (d(v1), d(v2),…, d(vn))為 G的度數(shù)序列。 度數(shù)序列之和必為偶數(shù) (?)。 mvdvdniinii ?? ??????11)()(例 (3,3,2,3)， (5,2,3,1,4)能成為圖的度數(shù)序列嗎？為什么？ 解： 由于這兩個(gè)序列中，奇數(shù)個(gè)數(shù)均為奇數(shù)，由握手定理知，它們不能成為圖的度數(shù)序列。 例 已知圖 G中有 10條邊， 4個(gè) 3度頂點(diǎn)，其余頂點(diǎn)的度數(shù)均小于等于 2，問 G中至少有多少個(gè)頂點(diǎn)？為什么？ 解 ：圖中邊數(shù) m=10， 由握手定理知，G中各頂點(diǎn)度數(shù)之和為 20， 4個(gè) 3度頂點(diǎn)占去 12度，還剩 8度， 若其余全是 2度頂點(diǎn) , 則需要 4個(gè)頂點(diǎn)來占用 8度，所以 G至少有 8個(gè)頂點(diǎn)。 正則圖 ： 各頂點(diǎn)的度都相同的圖為正則圖； 各頂點(diǎn)的度均為 k的圖為 k次 正則圖。 完全圖 ： (1) 設(shè) G = V,E 是 n階的無向簡(jiǎn)單圖，如果G中任何一個(gè)頂點(diǎn)都與其余 n–1個(gè)頂點(diǎn)相鄰，則 G為無向完全圖，記作： Kn。 三、正則圖與完全圖 (2) 設(shè) D = V,E 是 n階的有向簡(jiǎn)單圖，如果 D中任意頂點(diǎn) u， v?V(u?v)， 即有有向邊 u,v ， 又有有向邊 v,u ， 則稱 D為 n階有向完全圖。 如： 四、子圖與母圖： (1) G = V,E ， G39。 = V39。 , E39。 若 V39。?V， E39。?E， 則 G是 G39。的 母圖 ， G39。是G的 子圖 ，記作： G39。 ?G。 (2) 若 G39。?G 且 V39。=V， 則 G39。是 G的 生成子圖 。 (3) 設(shè) V1?V， 且 V1??， 以 V1為頂點(diǎn)集 ， 以 2端點(diǎn)均在 V1中的全體邊為邊集的 G的子圖 ，稱為 V1導(dǎo)出的 導(dǎo)出子圖 。 (4) 設(shè) E1?E，