離散數(shù)學：6-1 特殊的圖

復習思考題14若G連通,E為邊割集，則p(GE)>2。()若G連通,V為點割集，則p(GV)>2。()

Kn無點割集。()設G1,G2均為無向簡單圖，G1、G2分別是G1,G2的補圖，則G1≌G2G1≌G2。()設有向圖D=<V,E>，其中V={a,b,c,d}，其鄰接矩陣為A(D),則

d-(a)=_____

d(c)=_____第5章圖的基本概念

5.1無向圖及有向圖5.2通路、回路、圖的連通性5.3圖的矩陣表示

5.4最短路徑及關鍵路徑項目網(wǎng)絡圖項目網(wǎng)絡圖:表示項目的活動之間前后順序一致的帶權有向圖.邊——表示活動,邊的權——是活動的完成時間,頂點——表示事項(項目活動的開始和結(jié)束).要求:

(1)有一個始點(入度為0)和一個終點(出度為0).

(2)任意兩點之間只能有一條邊.(3)沒有回路.

(4)每一條邊始點的編號小于終點的編號.ABC引入虛活動ABC項目網(wǎng)絡圖實例41235678ABCDEFGHIJKL123434424611活動ABCDEFGHIJKL緊前活動－－－AAA,BA,BA,BC,HD,FE,IG,K時間(天)123434424611

邊

——活動,

權

——活動的完成時間頂點——事項關鍵路徑問題關鍵路徑——

項目網(wǎng)絡圖中從始點到終點的最長路徑。關鍵活動——

關鍵路徑上的活動。設D=<V,E,W>,V={1,2,,n},1是始點,n是終點.41235678ABCDEFGHIJKL123434424611關鍵路徑問題事項i的最早開始時間ES(i):

i最早可能開始的時間，即從始點到i的最長路徑的長度.

ES(1)=0ES(i)=max{ES(j)+wji|<j,i>E},i=2,3,,n

事項i的最晚完成時間LF(i):

在不影響項目工期的條件下,事項

i最晚必須完成的時間LF(i)=min{LF(j)-wij|<i,j>E},

(i=n-1,n-2,,1)

LF(n)=ES(n)41235678ABCDEFGHIJKL123434424611設D=<V,E,W>,V={1,2,,n},1是始點,n是終點.整個項目的完成時間=終點的最早開始時間ES(n)關鍵路徑問題實例事項i的最早開始時間ES(i):i最早可能開始的時間,即從始點到i的最長路徑的長度.

ES(1)=0

ES(i)=max{ES(j)+wji|<j,i>E},i=2,3,,n

ES(1)=0ES(2)=max{0+1}=1ES(3)=max{0+2,1+0}=2ES(4)=max{0+3,2+2}=4ES(5)=max{1+3,4+4}=8ES(6)=max{2+4,8+1}=9ES(7)=max{1+4,2+4}=6ES(8)=max{9+1,6+6}=1241235678ABCDEFGHIJKL123434424611關鍵路徑問題實例事項i的最晚完成時間LF(i):

在不影響項目工期的條件下,事項

i最晚必須完成的時間LF(n)=ES(n)

LF(i)=min{LF(j)-wij|<i,j>E},

(i=n-1,n-2,,1)

LF(8)=12LF(7)=min{12-6}=6LF(6)=min{12-1}=11LF(5)=min{11-1}=10LF(4)=min{10-4}=6LF(3)=min{6-2,11-4,6-4}=2LF(2)=min{2-0,10-3,6-4}=2LF(1)=min{2-1,2-2,6-3}=041235678ABCDEFGHIJKL123434424611關鍵路徑問題實例事項j的緩沖時間SL(j):

SL(j)=

LF(j)-ES(j)關鍵路徑上各頂點的緩沖時間均為041235678ABCDEFGHIJKL123434424611總工期:12天關鍵路徑:1378

關鍵活動:B,F,J事項LFESSL100022113220464251082611927660812120第6章特殊的圖

6.1二部圖6.2歐拉圖6.3哈密頓圖6.4平面圖

6.1二部圖

在實際工作中可能會遇到一類問題：單位有不同類型的工作空缺，也有一群填補空缺的應征者，每個人能勝任其中的某些工作，如何聘任應征者，使得被聘任的人得到他適合的工作崗位。在CBA聯(lián)賽中，如何把參賽隊配對？學校有多個社團，各學生可參加多個社團，若社長不可兼任，在什么情況下可選出合法的社長？這些都涉及到匹配問題。xyzabcd二部圖

定義

設無向圖G=<V,E>,若能將V分成V1和V2

(V1V2=V,V1V2=),使得G中的每邊的兩個端點都一個屬于V1,另一個屬于V2,則稱G為二部圖,記為<V1,V2,E>,稱V1和V2為互補頂點子集.

完全二部圖

定義

設無向圖G=<V,E>,若能將V分成V1和V2(V1V2=V,V1V2=),使得簡單圖G中的每邊的兩個端點都一個屬于V1,另一個屬于V2,且V1中每個頂點均與V2中每個頂點都相鄰,則稱G為完全二部圖,記為Kr,s,其中r=|V1|,s=|V2|.

注意:n階零圖為二部圖.

K3,3K2,3二部圖的判別法

例:下述各圖是否是二部圖?

定理

無向圖G=<V,E>是二部圖當且僅當G中無奇長度的回路。不是匹配

設G=<V,E>匹配(邊獨立集):

任2條邊均不相鄰的邊子集。極大匹配:添加任一條邊后都不再是匹配的邊子集。最大匹配:邊數(shù)最多的匹配。匹配數(shù):最大匹配中的邊數(shù),記為1

例:求下面3個圖中匹配數(shù)匹配數(shù)依次為3,3,4.

匹配

設M為G中一個匹配vi與vj被M匹配:(vi,vj)Mv為M飽和點:M中有邊與v關聯(lián)v為M非飽和點:M中沒有邊與v關聯(lián)M為完美匹配:G的每個頂點都是M飽和點

例關于M1,

a,b,e,d是飽和點

f,c是非飽和點

M1不是完美匹配M2是完美匹配二部圖中的匹配

定義設G=<V1,V2,E>為二部圖,

|V1||V2|,M是G中最大匹配,若V1中頂點全是M飽和點,則稱M為G中V1到V2的完備匹配.

當|V1|=|V2|時,完備匹配變成完美匹配.例：圖中紅邊組成各圖的一個匹配，(1)(2)(3)

是完備匹配,但不是完美匹配是最大匹配不是完備匹配,圖中無完備匹配是完美匹配Hall定理

Hall定理：設二部圖G=<V1,V2,E>中，|V1||V2|.G中存在從V1到V2的完備匹配當且僅當V1中任意k個頂點至少與V2中的k個頂點相鄰(k=1,2,…,|V1|)由Hall定理不難證明,下圖(2)沒有完備匹配.

(1)(2)(3)相異性條件二部圖完備匹配判定的充分條件

定理

設二部圖G=<V1,V2,E>中,若t>0,使得V1中每個頂點至少關聯(lián)t條邊，V2中每個頂點至多關聯(lián)t條邊，則G中存在V1到V2的完備匹配。

(1)(2)(3)完備匹配的充分條件——

V1中k個頂點至少關聯(lián)kt條邊，這

kt條邊至少關聯(lián)V2中k個頂點，即V1中任意k個頂點至少鄰接V2中的k個頂點.

t條件二部圖的應用實例1

某課題組要從a,b,c,d,e

這5人中派3人分別到上海、廣州、香港去開會。已知：a只想去上海，b只想去廣州，c,d,e都表示想去廣州或香港.

問該課題組在滿足個人要求的條件下，共有幾種派遣方案？

解：

令G=<V1,V2,E>,其中

V1={s,g,x},V2={a,b,c,d,e},E={(u,v)|uV1,vV2,v想去u},其中s,g,x分別表示上海、廣州和香港.G滿足相異性條件，因而可給出派遣方案，相當于求完備匹配數(shù)，

共有9種派遣方案二部圖的應用實例2證明：在88的國際象棋棋盤的一條主對角線上移去兩端的方格后，所得棋盤不能用12的長方形不重疊地填滿。證：作二部圖G=<V1,V2,E>如下：

V1={v|v位于白格內(nèi)},V2={v|v位于黑格內(nèi)},E={(u,v)|uV1vV2

u和v所在方格相鄰}

所以，|V1|=30,|V2|=32,

所得棋盤能用12的長方格填滿，

當且僅當G中存在完美匹配。

但|V1|

|V2|，完美匹配不存在！6.2歐拉圖

歐拉回路:(一筆畫無重復邊經(jīng)所有頂點的回路)圖中行遍所有頂點且恰好經(jīng)過每條邊一次的回路.歐拉圖:有歐拉回路的圖.幾點說明：上述定義對無向圖和有向圖都適用.規(guī)定——平凡圖為歐拉圖.歐拉回路是簡單回路.環(huán)不影響圖的歐拉性.歐拉圖

歐拉通路:(一筆畫無重復邊經(jīng)所有頂點的通路)圖中行遍所有頂點且恰好經(jīng)過每條邊一次的通路.

半歐拉圖:有歐拉通路而無歐拉回路的圖.幾點說明：上述定義對無向圖和有向圖都適