離散數(shù)學(xué)第八章

1、1第1頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五8.1 二部圖 二部圖完全二部圖匹配極大匹配最大匹配匹配數(shù)完備匹配 2第2頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五二部圖 定義 設(shè)無向圖 G=, 若能將V 劃分成V1 和 V2 (V1V2=V, V1V2=), 使得G中的每條邊的兩個(gè)端點(diǎn)都一個(gè)屬于V1, 另一個(gè)屬于V2, 則稱G為二部圖, 記為, 稱V1和V2為互補(bǔ)頂點(diǎn)子集. 又若G是簡(jiǎn)單圖, 且V1中每個(gè)頂點(diǎn)都與V2中每個(gè)頂點(diǎn)相鄰,則稱G為完全二部圖, 記為Kr,s, 其中r=|V1|, s=|V2|. 注意: n 階零圖為二部圖. 3第3頁，共26頁，202

2、2年，5月20日，11點(diǎn)13分，星期五二部圖的判別法 定理 無向圖G=是二部圖當(dāng)且僅當(dāng)G中無奇圈 例 下述各圖都是二部圖 4第4頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五匹配 設(shè)G=,匹配(邊獨(dú)立集): 任2條邊均不相鄰的邊子集極大匹配: 添加任一條邊后都不再是匹配的匹配最大匹配: 邊數(shù)最多的匹配匹配數(shù): 最大匹配中的邊數(shù), 記為1 例 下述3個(gè)圖的匹配數(shù) 依次為3, 3, 4. 5第5頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五匹配 (續(xù))設(shè)M為G中一個(gè)匹配vi與vj被M匹配: (vi,vj)Mv為M飽和點(diǎn): M中有邊與v關(guān)聯(lián)v為M非飽和點(diǎn): M中沒有邊與v關(guān)聯(lián)

3、M為完美匹配: G的每個(gè)頂點(diǎn)都是M飽和點(diǎn) 例 關(guān)于M1, a,b,e,d是飽和點(diǎn) f,c是非飽和點(diǎn) M1不是完美匹配 M2是完美匹配M1M26第6頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五二部圖中的匹配 定義 設(shè)G=為二部圖, |V1|V2|, M是G中最大匹配, 若V1中頂點(diǎn)全是M飽和點(diǎn), 則稱M為G中V1到V2的完備匹配. 當(dāng)|V1|=|V2|時(shí), 完備匹配變成完美匹配.(1)(2)(3)例 圖中紅邊組成各圖的一個(gè)匹配，(1)為完備的, 但不是完美的; (2)不是完備的, 其實(shí)(2)中無完備匹配; (3) 是完美的.7第7頁，共26頁，2022年，5月20日，11點(diǎn)13分，

4、星期五Hall定理 定理(Hall定理) 設(shè)二部圖G=中，|V1|V2|. G中存在從V1到V2的完備匹配當(dāng)且僅當(dāng)V1中任意k 個(gè)頂點(diǎn)至少與V2中的k個(gè)頂點(diǎn)相鄰(k=1,2,|V1|).由Hall定理不難證明, 上一頁圖(2)沒有完備匹配. 定理 設(shè)二部圖G=中, 如果存在t1, 使得V1中每個(gè)頂點(diǎn)至少關(guān)聯(lián) t 條邊, 而V2中每個(gè)頂點(diǎn)至多關(guān)聯(lián)t條邊，則G中存在V1到V2的完備匹配. Hall定理中的條件稱為“相異性條件”, 第二個(gè)定理中的條件稱為 t 條件. 滿足 t 條件的二部圖一定滿足相異性條件.8第8頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五一個(gè)應(yīng)用實(shí)例 例 某課題組要

5、從a, b, c, d, e 5人中派3人分別到上海、廣州、香港去開會(huì). 已知a只想去上海，b只想去廣州，c, d, e都 表示想去廣州或香港. 問該課題組在滿足個(gè)人要求的條件下，共有幾種派遣方案？ 解 令G=, 其中V1=s, g, x, V2=a, b, c, d, e, E=(u,v) | uV1, vV2, v想去u,其中s, g, x分別表示上海、廣州和香港. G如圖所示. G 滿足相異性條件，因而可給出派遣方案，共有9種派遣方案(請(qǐng)給出這9種方案). 9第9頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五8.2 歐拉圖歐拉通路歐拉回路歐拉圖半歐拉圖 10第10頁，共26頁

6、，2022年，5月20日，11點(diǎn)13分，星期五哥尼斯堡七橋問題 歐拉圖是能一筆畫出的邊不重復(fù)的回路. 11第11頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五歐拉圖 歐拉通路: 圖中行遍所有頂點(diǎn)且恰好經(jīng)過每條邊一次的通路. 歐拉回路: 圖中行遍所有頂點(diǎn)且恰好經(jīng)過每條邊一次的回路.歐拉圖: 有歐拉回路的圖.半歐拉圖: 有歐拉通路而無歐拉回路的圖.幾點(diǎn)說明：上述定義對(duì)無向圖和有向圖都適用.規(guī)定平凡圖為歐拉圖.歐拉通路是簡(jiǎn)單通路, 歐拉回路是簡(jiǎn)單回路.環(huán)不影響圖的歐拉性. 12第12頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五歐拉圖(續(xù))例 圖中, (1), (4)為歐拉圖

7、; (2), (5)為半歐拉圖; (3)，(6)既不 是歐拉圖, 也不是半歐拉圖. 在(3), (6)中各至少加幾條邊才能成為歐拉圖?13第13頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五歐拉圖的判別法 定理 無向圖G為歐拉圖當(dāng)且僅當(dāng)G連通且無奇度頂點(diǎn). 無向圖G是半歐拉圖當(dāng)且僅當(dāng)G連通且恰有兩個(gè)奇度頂點(diǎn). 定理 有向圖D是歐拉圖當(dāng)且僅當(dāng)D連通且每個(gè)頂點(diǎn)的入度都等于出度. 有向圖D具有歐拉通路當(dāng)且僅當(dāng)D連通且恰有兩個(gè)奇度頂點(diǎn), 其中一個(gè)入度比出度大1, 另一個(gè)出度比入度大1, 其余頂點(diǎn)的入度等于出度.14第14頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五實(shí)例例1 哥

8、尼斯堡七橋問題例2 下面兩個(gè)圖都是歐拉圖. 從A點(diǎn)出發(fā), 如何一次成功地走出一條歐拉回路來？ 15第15頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五8.3 哈密頓圖 哈密頓通路哈密頓回路哈密頓圖半哈密頓圖 16第16頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五哈密頓周游世界問題 17第17頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五哈密頓圖的定義哈密頓通路: 經(jīng)過圖中所有頂點(diǎn)一次且僅一次的通路.哈密頓回路: 經(jīng)過圖中所有頂點(diǎn)一次且僅一次的回路.哈密頓圖: 具有哈密頓回路的圖.半哈密頓圖: 具有哈密頓通路而無哈密頓回路的圖. 幾點(diǎn)說明：平凡圖是哈密頓圖.

9、哈密頓通路是初級(jí)通路，哈密頓回路是初級(jí)回路.環(huán)與平行邊不影響圖的哈密頓性.18第18頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五實(shí)例例 圖中, (1), (2)是哈密頓圖; (3) 是半哈密頓圖.(4)既不是哈密頓圖, 也不是半哈密頓圖，為什么？ 19第19頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五無向哈密頓圖的一個(gè)必要條件 定理 設(shè)無向圖G=是哈密頓圖, 則對(duì)于任意V1V且V1, 均有 p(GV1)|V1|.證 設(shè)C為G中一條哈密頓回路, 有p(CV1) |V1|. 又因?yàn)镃G, 故 p(GV1) p(CV1) |V1|. 幾點(diǎn)說明定理中的條件是哈密頓圖的必要條

10、件, 但不是充分條件.可利用該定理判斷某些圖不是哈密頓圖. 由定理可知, Kr,s當(dāng)sr+1時(shí)不是哈密頓圖. 當(dāng)r2時(shí), Kr,r是哈密頓圖, 而Kr,r+1是半哈密頓圖. 20第20頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五實(shí)例例 設(shè)G為n階無向連通簡(jiǎn)單圖, 若G中有割點(diǎn)或橋, 則G不是哈密頓圖.證 (1) 設(shè)v為割點(diǎn), 則p(Gv) 2|v|=1. 根據(jù)定理, G不是哈密頓圖. (2) 若G是K2(K2有橋), 它顯然不是哈密頓圖. 除K2外, 其他的有橋連通圖均有割點(diǎn). 由(1), 得證G不是哈密頓圖.21第21頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五無

11、向哈密頓圖的一個(gè)充分條件 定理 設(shè)G是n階無向簡(jiǎn)單圖, 若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于n1, 則G中存在哈密頓通路. 當(dāng)n3時(shí), 若任意兩個(gè)不相鄰的頂點(diǎn)的度數(shù)之和大于等于n, 則G中存在哈密頓回路, 從而G為哈密頓圖. 22第22頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五哈密頓通路(回路)的存在性(續(xù))定理中的條件是存在哈密頓通路(回路)的充分條件, 但不是必要條件.例如, 設(shè)G為長(zhǎng)度為n1(n4)的路徑, 它不滿足定理中哈密頓通路的條件, 但它顯然存在哈密頓通路.設(shè)G是長(zhǎng)為n的圈, 它不滿足定理中哈密頓回路的條件, 但它顯然是哈密頓圖.由定理, 當(dāng)n3時(shí), Kn均為

12、哈密頓圖.判斷某圖是否為哈密頓圖至今還是一個(gè)難題 23第23頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五判斷是否是哈密頓圖的可行方法觀察出一條哈密頓回路 例如 右圖(周游世界問題)中紅邊給出一條哈密頓回路, 故它是哈密頓圖.注意, 此圖不滿足定理的條件. 滿足充分條件例如 當(dāng)n3時(shí), Kn中任何兩個(gè)不同的頂點(diǎn) u,v, 均有d(u)+d(v) = 2(n1) n, 所以Kn為哈密頓圖. 24第24頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五判斷是否是哈 密頓圖的可行方法(續(xù))例 44國(guó)際象棋盤上的跳馬問題: 馬是否能恰好經(jīng)過每一個(gè)方格一次后回到原處?解 每個(gè)方格看作一個(gè)頂點(diǎn), 2個(gè)頂點(diǎn)之間有邊當(dāng)且僅當(dāng)馬可以從一個(gè)方格跳到另一個(gè)方格, 得到16階圖G, 如左圖紅邊所示. 取V1=a, b, c, d, 則p(GV1) = 6 |V1|, 見右圖. 由定理, 圖中無哈密頓回路, 故問題無解.在88國(guó)際象棋盤上, 跳馬問題是否有解? 不滿足必要條件25第25頁，共26頁，2022年，5月20日，11點(diǎn)13分，星期五應(yīng)用實(shí)例例 某次國(guó)際會(huì)議8人參加，已知每人至少與其余7人中的4人有共同語言，問服務(wù)員能否將他們安排在同一張圓桌就座，使得每個(gè)人都能與兩邊的人交談？解 圖是描述事物之間關(guān)系的最好的手段之一. 作無向圖G