緒論哥尼斯堡七橋問題:abdcca2bd緒論周游世界問題3緒論網(wǎng)絡布線問題4緒論印刷線路板布線問題bcde5f緒論匹配問題12乙

丙3甲6圖(graph)ca7b（無向）圖：G=(V，E)V：頂點集E：邊集d有向圖(directed

graph)abce1e2V={a,b,c}E={<a,b>,<a,c>}={e1,e2}有向邊:帶有方向的邊（用序偶表示）有向圖：所有的邊都是有向邊的圖。8圖的一些概念和規(guī)定9(P107)V(G)，E(G)分別表示G的頂點集和邊集。若|V(G)|＝n，則稱G為n階圖。若|V(G)|與|E(G)|均為有限數(shù)，則稱G為有限圖。若邊集E(G)＝，則稱G為零圖，此時，又若G為n階圖，則稱G為n階零圖，記作Nn，特別地，稱N1為平凡圖。10標定圖與非標定圖、基圖(P108)將圖的集合定義轉(zhuǎn)化成圖形表示之后，常用ek表示無向邊(vi,vj)（或有向邊<vi,vj>），并稱頂點或邊用字母標定的圖為標定圖，否則稱為非標定圖。將有向圖各有向邊均改成無向邊后的無向圖稱為原來圖的基圖。11關(guān)聯(lián)與關(guān)聯(lián)次數(shù)、環(huán)、孤立點設(shè)G＝<V,E>為無向圖，ek＝(vi,vj)∈E，稱vi,vj為ek的端點,ek與vi或ek與vj是彼此相關(guān)聯(lián)的。若vi≠vj，則稱ek與vi或ek與vj的關(guān)聯(lián)次數(shù)為1。

若vi＝vj,則稱ek與vi的關(guān)聯(lián)次數(shù)為2,并稱ek為環(huán)。無邊關(guān)聯(lián)的頂點均稱為孤立點。相鄰與鄰接設(shè)無向圖G＝<V，E>，vi，vj∈V，ek，el∈E。若et∈E，使得et＝(vi，vj)，則稱vi與vj是相鄰的若ek與el至少有一個公共端點，則稱ek與el是相鄰的設(shè)有向圖D＝<V，E>，vi，vj∈V。若et∈E，使得et＝<vi，vj>，則稱vi為et的始點，vj為et的終點abce1e2ab12c鄰域設(shè)無向圖G＝<V，E>，v∈V，稱{u|u∈V∧(u,v)∈E∧u≠v}為v的鄰域，記做NG(v)或N(v)ab13cN(a)={b,c}鄰域設(shè)有向圖D＝<V，E>，v∈V，稱{u|u∈V∧<v,u>∈E∧u≠v}為v的后繼元集，記做Г+D(v)。稱{u|u∈V∧<u,v>∈E∧u≠v}為v的先驅(qū)元集，D記做Г-

(v)。稱Г+

(v)∪Г-

(v)為v的鄰域，記做N

(v)。D

D

Dabce1e2N+(a)={b,c}N-(a)=1415簡單圖與多重圖定義(P109,定義7.5)在無向圖中，關(guān)聯(lián)一對頂點的無向邊如果多于1條，則稱這些邊為平行邊，平行邊的條數(shù)稱為重數(shù)。在有向圖中，關(guān)聯(lián)一對頂點的有向邊如果多于

1條，并且這些邊的始點和終點相同(也就是它們的方向相同)，則稱這些邊為平行邊。含平行邊的圖稱為多重圖。既不含平行邊也不含環(huán)的圖稱為簡單圖。abce1e2abce116e3e2e417頂點的度數(shù)定義(P109,定義7.6)設(shè)G＝<V,E>為一無向圖，v∈V，稱v作為邊的端點次數(shù)之和為v的度數(shù)，簡稱為度，記做

dG(v)或d(v)。設(shè)D＝<V，E>為有向圖，v∈V，稱v作為邊的始點次數(shù)之和為v的出度，記做d+D(v)，簡記作d+(v)。稱v作為邊的終點次數(shù)之和為v的入度，記做dD(v)，簡記作d

(v)。-

-稱d+(v)+d-(v)為v的度數(shù)，記做d(v)。abce1e2abce1e21819圖的度數(shù)的相關(guān)概念(P110)在無向圖G中，最大度

△(G)＝max{d(v)|v∈V(G)}最小度

δ(G)＝min{d(v)|v∈V(G)}在有向圖D中，最大出度△+(D)＝max{d+(v)|v∈V(D)}最小出度δ+(D)＝min{d+(v)|v∈V(D)}最大入度△-(D)＝max{d-(v)|v∈V(D)}最小入度δ-(D)＝min{d-(v)|v∈V(D)}圖的度數(shù)的相關(guān)概念稱度數(shù)為1的頂點為懸掛頂點，與它關(guān)聯(lián)的邊稱為懸掛邊。度為偶數(shù)(奇數(shù))的頂點稱為偶度(奇度)頂點。ab20ce1e2握手定理aab

b

c2

4

6ab21c注：遇到環(huán)要加2。計算以下各圖中頂點度之和。22握手定理定理(P110,定理7.1)設(shè)G＝<V,E>為任意無向圖，V＝{v1,v2,…,vn}，n|E|＝m，則

d

(vi

)

2mi

1定理(P110,定義7.2)設(shè)D＝<V,E>為任意有向圖，V＝{v1,v2,…,vn}，|E|＝m，則ni

1ni

1ni

1iid

(v

)

id

(v

)

2m,且md

(v

)

握手定理推論：奇度點（度數(shù)為奇數(shù)）有偶數(shù)個。ce2奇度點為2個。K4cdae1bab

e奇度點為4個。2324度數(shù)列(P110)設(shè)G＝<V,E>為一個n階無向圖，V＝{v1,v2,…,vn}，稱d(v1)，d(v2)，…，d(vn)為G的度數(shù)列。對于頂點標定的無向圖，它的度數(shù)列是唯一的。反之，對于給定的非負整數(shù)列d＝{d1,d2,…,dn}，若存在V＝{v1,v2,…,vn}為頂點集的n階無向圖G，使得d(vi)＝di，則稱d是可圖化的。特別地，若所得圖是簡單圖，則稱d是可簡單圖化的。25可圖化的充要條件定理(P110,定理7.3)

設(shè)非負整數(shù)列d＝(d1，d2，…，dn)，則d是可圖化的當且僅當0(mod

2)n

dii

126定理定理設(shè)G為任意n階無向簡單圖，則△(G)≤n-1例判斷下列各非負整數(shù)列哪些是可圖化的？哪些是可簡單圖化的？(1)

(5,4,4,3,3,2)(2)

(5,3,3,2,1)27定理nd

)，定理(P112,定理7.5)

設(shè)非負整數(shù)列d＝(d

，d

，…，n

1

2且n-1d1d2…dn0,則d是可簡單圖化的當且僅當d’＝(d2-1，d2-1…dd1+1-1，dd1+2…，dn)可簡單圖化。例判斷下列各非負整數(shù)列哪些是可圖化的？哪些是可簡單圖化的？(1)

(5,5,4,4,2,2)(2)

(4,4,3,3,2,2)i

1id

0(mod

2)同構(gòu)(isomorphic)abcdG123428G’29圖的同構(gòu)定義(P113,定義7.7)

設(shè)G1＝<V1,E1>，G2＝<V2,E2>為兩個無向圖，若存在雙射函數(shù)f：V1→V2，對于vi,vj∈V1，(vi,vj)∈E1當且僅當(f(vi),f(vj))∈E2，并且(vi,vj)與(f(vi),f(vj))的重數(shù)相同，則稱G1與G2是同構(gòu)的，記做G1≌G2。同構(gòu)GG’abcdefbcd

efaG與G’是否同構(gòu)？30(Petersen)圖3132完全圖定義7.8(P114)設(shè)G為n階無向簡單圖，若G中每個頂點均與其余的n-1個頂點相鄰，則稱G為n階無向完全圖，簡稱n階完全圖，記做

Kn(n≥1)。設(shè)D為n階有向簡單圖，若D中每個頂點都鄰接到其余的n-1個頂點，又鄰接于其余的n-1個頂點，則稱D是n階有向完全圖。設(shè)D為n階有向簡單圖，若D的基圖為n階無向完全圖Kn，則稱D是n階競賽圖。完全圖舉例33n階無向完全圖的邊數(shù)為：n階有向完全圖的邊數(shù)為：n階競賽圖的邊數(shù)為：K53階有向完全圖4階競賽圖正則圖定義(P114,定義7.9)

設(shè)G為n階無向簡單圖，若v∈V(G)，均有d(v)＝k，則稱G為k-正則圖。舉例

n階無向完全圖圖34K正則圖abcd2正則圖abcd3正則圖3536二部圖定義

(P114定義7.10)設(shè)G＝<V,E>為一個無向圖，若能將V劃分成V1和V2(V1∪V2＝V,V1∩V2＝)，使得G中的每條邊的兩個端點都是一個屬于V1，另一個屬于V2，則稱G

為二部圖（或稱二分圖，偶圖等），稱V1和V2為互補頂點子集。常將二部圖G記為<V1,V2,E>。若G是簡單二部圖，V1中每個頂點均與V2中所有頂點相鄰，則稱G為完全二部圖，記為Kr,s，其中r＝|V1|，s＝|V2|。二部圖以下是否為二部圖？cdefbaccdef37二部圖判斷以下各圖是否為二部圖？cfdba

cdbe

ace38f二分圖判斷下圖是否為二分圖？39完全二分圖(1)bdfacK2,3K2,2完全二部圖a

cb40cd41子圖定義(P116定義7.11)設(shè)G＝<V,E>，G＝<V,E>為兩個圖(同為無向圖或同為有向圖)，若V

V且EE，則稱G是G的子圖，G為G的母圖，記作G

G。若V

＝V，則稱G

為G的生成子圖。42子圖設(shè)G＝<V,E>為一圖，V1V且V1≠，稱以V1為頂點集，以G中兩個端點都在V1中的邊組成邊集E1的圖為G的V1導出的子圖，記作G[V1]。設(shè)E1E且E1≠，稱以E1為邊集，以E1中邊關(guān)聯(lián)的頂點為頂點集V1的圖為G的E1導出的子圖，記作G[E1]。導出子圖舉例取V1＝{a,b,c}，G[V1]為(2)中圖所示。取E1＝{e1,e3}，G[E1]為(3)中圖所示。4344定義定義(P116定義7.12)設(shè)G＝<V,E>為n階無向簡單圖，以V為頂點集，以所有使G成為完全

圖

Kn的添加邊組成的集合為邊集的圖，稱為G的補圖，記作G。若圖G≌G，則稱為G是自補圖。(1)為自補圖(2)和(3)互為補圖45定義定義(P117定義7.13)設(shè)G＝<V,E>為無向圖。設(shè)e∈E，用G-e表示從G中去掉邊e，稱為刪除e。設(shè)EE，用G-E表示從G中刪除E中所有的邊，稱為刪除E

。設(shè)v∈V，用G-v表示從G中去掉v及所關(guān)聯(lián)的一切邊，稱為刪除頂點v。設(shè)VV，用G-V表示從G中刪除V中所有頂點，稱為刪除V

。46定義定義設(shè)G＝<V,E>為無向圖。設(shè)邊e＝(u,v)∈E，用G\e表示從G中刪除e后，將e的兩個端點u,v用一個新的頂點w(或用u或v充當w)代替，使w關(guān)聯(lián)除e外u,v關(guān)聯(lián)的所有邊，稱為邊e的收縮。設(shè)u,v∈V(u,v可能相鄰，也可能不相鄰)，用

G∪(u,v)(或G+(u,v))表示在u,v之間加一條邊(u,v)，稱為加新邊。舉例收縮邊(2)Petersen圖及其一種收縮圖4849通路與回路定義(P119定義7.18)設(shè)G為無向圖，G中頂點與邊的交替序列Г＝vi0ej1vi1ej2vi2…ejivil稱為vi0到vil的通路，其中，vir-1,vir為ejr的端點，vi0，vil分別稱為Г的始點與終點，Г中邊的條數(shù)稱為它的長度。若vi0＝vil，則稱通路為回路。若Г的所有邊各異，則稱Г為簡單通(回)路，若Г的所有頂點(除vi0與vij可能相同外)各異，則稱Г為初級通(回)路或路徑(圈)，將長度為奇數(shù)的圈稱為奇圈，長度為偶數(shù)的圈稱為偶圈。abce150e3e2e4e3

e1

e2是簡單通路但不是初級通路初級通路一定是簡單通路，反之不一定。通路與回路關(guān)于通路與回路的說明在有向圖中，通路、回路及分類的定義與無向圖中非常相似，只是要注意有向邊方向的一致性。bcdae151e2e3abcd不是通路，dcba是通路通路與回路定理(P120定理7.6)在n階圖G中，若從頂點vi到vj（vi≠vj）存在通路，則從vi到vj存在長度小于或等于n-1的通路。abce152e3e2e453無向圖的連通性定義(P121

定義7.20)

設(shè)無向圖G＝<V,E>，

u,v∈V，若u,v之間存在通路，則稱u,v是連通的，記作u～v。v∈V，規(guī)定v～v。無向圖中頂點之間的連通關(guān)系～＝{（u,v）|

u,v∈V且u與v之間有通路}是自反的、對稱的、傳遞的，因而～是V上的等價關(guān)系。54連通圖與連通分支定義

(P122定義7.21)若無向圖G是平凡圖或G中任何兩個頂點都是連通的，則稱G為連通圖，否則稱G是非連通圖或分離圖。定義(P122定義7.22)設(shè)無向圖G＝<V,E>，V關(guān)于頂點之間的連通關(guān)系～的商集V/～＝{V1,V2,…,Vk}，Vi為等價類，稱導出子圖G[Vi](i＝1,2,…,k)為G的連通分支，連通分支數(shù)k常記為p(G)。連通分支也可定義為:極大連通子圖。abcabcG155G256無向圖中頂點之間的短程線及距離定義(P122定義7.23)設(shè)u,v為無向圖G中任意兩個頂點，若u～v，稱u,v之間長度最短的通路為u,v之間的短程線，短程線的長度稱為u,v之間的距離，記作d(u,v)。當u,v不連通時，規(guī)定d(u,v)＝∞。距離有以下性質(zhì)：(1)d(u,v)≥0，u＝v時，等號成立。(2)具有對稱性，d(u,v)＝d(v,u)。(3)滿足三角不等式：u,v,w∈V(G)，則d(u,v)+d(v,w)≥d(u,w)57二部圖的判定定理定理7.8一個無向圖G＝<V,E>是二部圖當且僅當G中無奇圈（或奇數(shù)長度的回路）。定理7.9

設(shè)G是n階無向連通圖，則G的邊數(shù)mn-1。無向圖的點割集定義7.25(P123)

設(shè)無向圖G＝<V,E>，若存在VV，且V≠，使得p(G-V)>p(G)，而對于任意的V

V

，均有p(G-V

)＝p(G)，則稱V是G的點割集。若V

是單元集，即V

＝{v}，則稱v為割點。{v2,v4},{v3},{v5}都是點割集v3,v5都是割點v1與v6不在任何割集中。58無向圖的邊割集定義

(P123定義7.26)設(shè)無向圖G＝<V,E>，若存在EE，且E≠，使得p(G-E)>p(G)，而對于任意的EE，均有p(G-E)＝p(G)，則稱E是G的邊割集，或簡稱為割集。若E

是單元集，即E

＝{e}，則稱e為割邊或橋。{e6},{e5},{e2,e3},{e1,e2},{e3,e4},{e1,e4},{e1,e3},{e2,e4}都是割集，e6,e5是橋。5960有向圖的連通性定義7.30

設(shè)D＝<V,E>為一個有向圖。

vi,vj∈V，若從vi到vj存在通路，則稱vi可達vj，記作vi→vj，規(guī)定vi總是可達自身的，即vi→vi。若vi→vj且vj→vi，則稱vi與vj是相互可達的，記作vi

vj。規(guī)定vivi。61有向圖的連通性定義(P129

定義7.31)

設(shè)D＝<V,E>

為有向圖，vi,vj∈V，若vi→vj，稱vi到vj長度最短的通路為vi到vj的短程線，短程線的長度為vi到vj的距離記

作d

<vi,vj>。連通圖定義(P129定義7.30)設(shè)D＝<V,E>為一個有向圖。若D的基圖是連通圖，則稱D是弱連通圖，簡稱為連通圖。若vi,vj∈V，vi→vj與vj→vi至少成立其一，則稱D是單向連通圖。若均有vi

vj，則稱D是強連通圖。強連通圖62單向連通圖弱連通圖63強連通圖與單向連通圖的判定定理定理7.22

設(shè)有向圖D＝<V,E>，V＝{v1,v2,…,vn}。D是強連通圖當且僅當D中存在經(jīng)過每個頂點至少一次的回路。第八章E圖和H圖圖一筆畫問題65圖哥尼斯堡七橋問題cabdcabd66圖(P132)半

圖：如果G的一條簡單通路含有G中所有的邊，則稱G是半

圖，該通路稱為通路。

圖：如果G的一條回路含有G中所有的邊，則稱G是圖（E圖），該回路稱為歐拉回路67圖有向

圖、有向半

圖可類似定義68圖(P132)定理8.1

設(shè)G是無向連通圖，則以下等價G是

圖G中所有頂點的度都為偶數(shù)。G是若干個邊不重的圈的并。定理8.2無向連通圖G是半中恰有兩個奇度頂點。圖當且僅當G69圖(P134)定理8.3

有向圖D是 圖當且僅當D是強連通的且每個頂點的入度都等于出度。定理8.4

有向圖D是半 圖當且僅當D是單向連通的，且D中恰有兩個奇度頂點，其中一個的入度比出度大1，另一個的出度比入度大1，而其余頂點的入度都等于出度。70求 圖中 回路的算法(P134)Fleury算法，能不走橋就不走橋任取v0∈V(G)，令P0＝v0。設(shè)Pi＝v0e1v1e2…eivi已經(jīng)行遍，按下面方法來從E(G)-{e1,e2,…,ei}中選取ei+1：ei+1與vi相關(guān)聯(lián)；除非無別的邊可供行遍，否則ei+1不應該為Gi＝G-{e1,e2,…,ei}中的橋。當(2)不能再進行時，算法停止。71求 回路的算法求

回路的算法（一）：擴充回路法從G中一點出發(fā)找一回路C1如果G-C1不是空圖,則C1中必有點v和G-C1中某邊相連從v出發(fā)在G-C1中找一回路C2用C2來代替v使C1中含有

的邊重復這一過程便得一個

回路72應用磁鼓定位7374磁鼓定位5磁鼓定位76磁鼓定位77圖(P137)1859年,哈密爾頓:周游世界問題78圖定義8.2

經(jīng)過圖（有向圖或無向圖）中所有頂點一次且僅一次的通路稱為

通路。經(jīng)過圖中所有頂點一次且僅一次的回路稱為哈密頓回路。具有

回路的圖稱為圖，具有圖稱為半通路但不具有

回路的圖。79定理圖，對于定理8.6設(shè)無向圖G＝<V,E>是任意V1V，且V1≠，均有p(G-V1)≤|V1|其中，p(G-V1)為G-V1的連通分支數(shù)。80推論圖，對于推論設(shè)無向圖G＝<V,E>是半任意的V1V且V1≠，均有p(G-V1)≤|V1|+181哈密爾頓圖判斷下列圖是否為H圖。82定理定理8.7設(shè)G是n(n2)階無向簡單圖，若對于G中任意不相鄰的頂點vi,vj，均有d(vi)+d(vj)≥n-1則G中存在

通路。83推論推論設(shè)G為n(n≥3)階無向簡單圖，若對于G中任意兩個不相鄰的頂點vi,vj，均有d(vi)+d(vj)≥n則G中存在

回路，從而G為(15.2)圖。84定理定理8.8

設(shè)u,v為n階無向圖G中兩個不相鄰的頂點，且d(u)+d(v)≥n，則G為

圖當圖((u,v)是加的新且僅當G∪(u,v)為邊)。定理8.9

競賽圖是半H圖。定理8.10

強連通的競賽圖是H圖。85例例在某次國際會議的預備會議有8人參加，他們來自不同的國家。已知他們中任何兩個無共同語言的人中的每一個，與其余有共同語言的人數(shù)之和大于或等于8，問能否將這8個人排在圓桌旁，使其任何人都能與兩邊的人交談。86定理定理8.9

若D為n(n≥2)階競賽圖，則D中具有哈密頓通路。定理8.10

強連通的競賽圖是

通圖。87第九章

樹樹的定義(144)樹：連通無回路的無向圖。樹中的1度點稱為樹葉，其余稱為分支點。89樹的定義9091樹的定義定理9.1：如果G有n2個頂點，m條邊，則以下等價：G是樹，即無回路、連通。G中任何兩點間恰有一條路徑G無回路且m=n-1G連通且有m=n-1G連通且每條邊都是橋G無回路且添加任何一條邊恰好構(gòu)成一個含新邊的圈。定理非平凡樹中至少有兩片樹葉。92樹的定義例畫出所有6階非同構(gòu)的樹。例7階樹中有3片樹葉和1個3度點，其余3個頂點的度數(shù)均無1和3，試畫出滿足要求的所有非同構(gòu)的樹。樹的定義生成樹(P146定義9.2)

G=<V,E>，如果樹T是G的生成子圖，則稱T是G的生成樹。T中

的邊稱為T的樹枝。稱GT-T為T的余樹，記為

。余樹中的邊稱為T的弦。9394樹的定義定理9.3無向圖G有生成樹當且僅當G是連通圖。例7階樹中有3片樹葉和1個3度點，其余3個頂點的度數(shù)均無1和3，試畫出滿足要求的所有非同構(gòu)的樹。推論1G

為n

階m

條邊的無向連通圖，則m≥n1。推論2設(shè)G是n階m條邊的無向連通圖，T為G的生成樹，則T的余樹中含有m-n+1條邊（即T有m-n+1條弦）。推論3設(shè)T是連通圖G的一棵生成樹，T為T的余樹，C為G

中任意一個圈，則E(T)∩E(C)≠推論95定理9.4設(shè)T為無向連通圖G中一棵生成樹，e為T的任意一條弦，則T∪e中含G中只含一條弦其余邊均為樹枝的圈，而且不同的弦對應的圈也不同。定理96定義9.3設(shè)T是n階m條邊的無向連通圖G的一棵生成樹，設(shè)e1,e2,…,emn+1為T的弦。設(shè)Cr為T添加弦er產(chǎn)生的G中只含弦er，其余邊均為樹枝的圈，稱Cr為G的對應T的弦er的基本回路或基本圈，r＝1,

2,…,mn+1。稱{C1,

C2,

…,

Cmn+1}為G對應T的基本回路系統(tǒng)，稱mn+1為G的圈秩，記作(G)?；净芈放c基本回路系統(tǒng)的定義97求基本回路設(shè)弦e=(u,v)，先求T中u到v的路徑(u,v)，再并上弦e，即得對應e的基本回路。基本回路與基本回路系統(tǒng)的定義98無向連通圖G的圈秩與生成樹的選取無關(guān)，但不同生成樹對應的基本回路系統(tǒng)可能不同。求下圖中的基本回路系統(tǒng)。舉例99100定理定理9.5

設(shè)T是連通圖G的一棵生成樹，e為T的樹枝，則G中存在只含樹枝e，其余邊都是弦的割集，且不同的樹枝對應的割集也不同。101基本割集與基本割集系統(tǒng)的定義定義9.4

設(shè)T是n階連通圖G的一棵生成樹，e1,e2,…,en1為T的樹枝，Si

是G的只含樹枝ei的割集，則稱Si為G的對應于生成樹T由樹枝ei生成的基本割集，i＝1,2,…,n1。稱{S1,S2,…,Sn1}為G對應T的基本割集系統(tǒng)，稱n1為G的割集秩，記作(G)。102基本割集與基本割集系統(tǒng)的定義求基本割集設(shè)e為生成樹T的樹枝，Te為兩棵小樹T1與T2，令Se

＝{e|eE(G)且e的兩個端點分別屬于T1與T2}，則Se為e對應的基本割集。求下圖中的基本割集系統(tǒng)。舉例103最小生成樹最小生成樹：G是帶權(quán)圖，G的權(quán)值最小的生成樹稱為G的最小生成樹。（樹的權(quán)值指它所有的邊的權(quán)值之和）61042

24

41G1T:權(quán)為7105最小生成樹Kruskal算法T=;while

(|T|<n-1

&

E)e=E中最短邊E=E-e若T+e無回路，則T=T+e若|T|<n-1,則失敗退出，否則成功退出。106最小生成樹Prim算法（設(shè)G連通,V是頂點集，v1∈V)t=v1;T=;U={t};while

(UV)w(t,u)=min{w(t,v)|v∈V-U}T=T+e(t,u)U=U+ufor(v∈V-U)w(t,v)=min{w(t,v),w(u,v)3.

輸出T。第十章圖的矩陣表示108有向圖的關(guān)聯(lián)矩陣vi為ej的始點定義10.1

設(shè)有向圖D＝<V,E>中無環(huán)，V＝{v1,v2,…,vn}，E＝{e1,e2,…,em}，令

1ji1

v

為e

的終點jiv

為e

不關(guān)聯(lián)ijm

0則稱(mij)n×m為D的關(guān)聯(lián)矩陣，記作M(D)。有向圖的關(guān)聯(lián)矩陣109-1

01

00

-1

1

0

0

0

1

-1

1

00

0

10

-1

-1M

(D

)

圖的矩陣表示定義10.2

設(shè)無向圖G＝<V,E>，V＝{v1,v2,…,vn}，E＝{e1,e2,…,em}，令mij為頂點vi與邊ej的關(guān)聯(lián)次數(shù)，則稱(mij)n×m為G的關(guān)聯(lián)矩陣，記作M(G)。11010100

2

1

1

1

0

0

1

1

00

0

10

0

0M

(G

)

有向圖的鄰接矩陣定義10.4

設(shè)有向圖D＝<V,E>，V＝{v1,v2,…,vn}，E＝{e1,e2,…，em}，令aij(1)為頂點vi鄰接到頂點vj邊的條數(shù)，稱(aij(1))n×n為D的鄰接矩陣，記作A(D)，或簡記為A。111000

2

1

00

0

1

0

0

10

0

1

1A

112定理

設(shè)Ｄ是有向圖，Ｖ＝｛u1,u2,···

,un}，Ｍ＝（mij)是Ｄ的鄰接矩陣，則矩陣Ｍk（k=1,2,3···

)中第i行第j列的元素，等于從ui到uj長度為k的通路的條數(shù)。11113001111

01

11

02102212

12

10

110011101001000000112101有向圖的可達矩陣定義10.5

設(shè)D＝<V,E>為有向圖。V＝{v1,v2,…,vn}，令ijp

＝1

vi

可達vj0

否則114稱(pij)n×n為D的可達矩陣，記作P(D)，簡記為P。101

1

1

10

1

1

0

1

10

0

1

1P

第十一章平面圖116平面圖(P165)K4abcdK4abcd定義11.1G可嵌入曲面S：如果圖G能以這樣的方式畫在曲面S上，即除頂點處外無邊相交。G是可平面圖或平面圖：若G可嵌入平面。G的平面嵌入：畫出的無邊相交的平面圖。非平面圖：無平面嵌入的圖。平面圖K5是否為平面圖？K5K5117平面圖bcdefK3,3是否為平面圖？aK3,3bcdefK3,3118平面圖f1119f2f3無窮面面（域）：由閉曲線分割而成的區(qū)域。無窮面：面積為無窮的面。邊界：包圍某個面的各條邊稱為該面的邊界。面的次數(shù)：該面的邊界的長度。平面圖定理若G為平面圖，則在G中加平行邊或環(huán)所得圖還是平面圖。定理11.2

平面圖G中所有面的次數(shù)之和等于邊數(shù)m的兩倍。aK4bcd120極大平面圖定義11.3若在簡單平面圖G中的任意兩個不相鄰的頂點之間加一條新邊所得圖為非平面圖，則稱G為極大平面圖。121122極大平面圖定理

極大平面圖是連通的。定理11.4

設(shè)G為n(n3)階簡單連通的平面圖，

G為極大平面圖當且僅當G的每個面的次數(shù)均為3。123Euler公式定理11.6(Euler公式-1750）：連通平面圖G有n個頂點，m條邊和r個面，則n-m+r=2。定理11.7：平面圖G有p分圖，則n-m+r=p+1。定理11.8：連通平面圖G中每個面的次數(shù)至少為L(L>2)，則有m(n-2)L/(L-2)。推論：K5和K3，3都不是平面圖。124極大平面圖定理11.10：如果G是連通平面圖，有n(>2)個點，m條邊，則m3n-6。定理11.11：如果G是極大連通平面圖，有n(>2)個點，m條邊，則m=3n-6。定理11.12：簡單平面圖G的最小度5。非平面圖定義11.6同胚：如果圖H可以通過在圖G的邊上或“消去”有限多個2次點得到，則稱這G和H是同胚的。125126非平面圖定理11.13：（Kuratowski

1930）一個圖是平面圖當且僅當它不含與K5或K3,3同胚的子圖。定理11.14：(Wagner

1936)一個圖是平面圖當且僅當它不含可以收縮成K5或K3,3的子圖。非平面圖請找一個Petersen圖的子圖與K3,3同胚127Petersen圖不是平面圖對偶圖定義11.17

對偶圖：G是平面圖，G的對偶圖G*定義如下：①在G的每個面中選定一個點作為G*的頂點。②對G中的每條邊e，作G*中的一條邊e*，使之僅與e相交，并且關(guān)聯(lián)以e為公共邊的兩個面所對應的G*中的點。128129對偶圖n=5

r*=4定理11.15：連通平面圖G有n個頂點，m條邊和r個面，G的對偶圖G*有n*個頂點，m*條邊和r*個面，則r=n*,m=m*,n=r*。第十二章圖的色數(shù)與色數(shù)多項式(P180)k可點：如果圖G的每個頂點都可用k種顏色之一，使得任意兩個不同的相鄰頂點有不同顏色，則稱G是k可點的。點色數(shù)：如果G是k可點的，但不是k-1可點的，則稱G的點色數(shù)為k，記為X(G)。k可邊(面)，邊(面)色數(shù)G2G1131色數(shù)定理12.5：G是無環(huán)的無向圖，最大度為Δ,則G是Δ+1可點的。定理12.6：(Brooks)如果G是簡單連通非完全圖，并且G的最大度為Δ（≥3），則G是Δ可點的。例：Petersen圖的點色數(shù)為3.132面色數(shù)定義12.3連通無橋的平面圖稱為地圖。定理12.13

地圖G是k可面

的當且僅當G*是k可點

的。定理12.15：每個平面圖都是6可點(面)的。定理12.16：每個平面圖都是5可點(面)的。四色猜想：任何平面圖都是4可面

的。133134邊色數(shù)定理12.17(Vizing)

簡單無向圖G的邊色數(shù)為(G)或(G)+1。例12.5二部圖G的邊色數(shù)為(G)。例

當n>1

為奇數(shù)時，

Kn

的邊色數(shù)為n

。當n>1為偶數(shù)時，Kn的邊色數(shù)為n-1。135邊色數(shù)例12.7某中學,星期一由m位教師給n個班上課:這一天至少要安排多少節(jié)課？在節(jié)數(shù)不增加的條件下至少需要幾個教室？若m=4,n=5，設(shè)教員為t1,t2,t3,t4,班級c1,c2,c3,c4,c5。t1為c1,c2,c3分別上2節(jié)1節(jié)1節(jié).

t2為c2,c3各上1節(jié)課。t3為c2,c3,c4各上1節(jié)課。t4為c4,c5上1節(jié)和2節(jié)。請給出一個最節(jié)省教室的課表。第十三章匹配匹配結(jié)婚問題：假定有m個男孩和若干個，其中每個男孩認識若干個，問在什么條件下，才有可能使每個男孩都與他所認識的結(jié)婚？男孩137匹配n個人做實驗，2人一組。如果2個點之間有邊就表示這2人愿意組合，問：最多能有多少人同時做實驗？138139邊覆蓋集與匹配定義13.6

設(shè)G=<V,E>,

若E*(E*E)中任何兩條邊均不相鄰,則稱E*為G中邊獨立集,也稱E*為G中的匹配(Matching);若在E*中加入任意一條邊所得集合都不是匹配,則稱E*為極大匹配;邊數(shù)最多的匹配稱為最大匹配;最大匹配的邊數(shù)稱為邊獨立數(shù)或匹配數(shù),記作1(G),

簡記為1。匹配140邊覆蓋集與匹配(P193)定義

假設(shè):

M為圖G中一個匹配:若(vi,vj)M,則稱vi與vj被M所匹配;對vV(G),

若存在邊eM,

使e與v關(guān)聯(lián),則稱v為M-飽和點,否則,稱v為M-非飽和點;若G中每個頂點都是M-飽和點,則稱M為G中的完美匹配;稱在M和E(G)-M

替取邊的路徑為M的交錯路徑,起點和終點都是M-非飽和點的交錯路徑稱為可增廣的交錯路徑;稱在M和E(G)-M

替取邊的圈為交錯圈。141a

b

c

d142uv

x

y

z143匹配定理13.7設(shè)M1和M2是G中匹配，則G[M1M2]的每個連通分支或為由M1和M2中的邊組成的交錯圈，或為交錯路徑。定理13.8設(shè)M是G中匹配，Γ是M增廣路徑，則M’＝MΓ仍是G的匹配且|M’|=|M|+1定理13.9

M是G的最大匹配

iffG中不存在關(guān)于M可增廣路徑。二部圖中的匹配定義13.7

設(shè)G

=

<V1,V2,

E>為二部圖,

|V1|

|V2|,M為G中一個匹配,

且|M|

=

|V1|,

則稱M為V1到V2的完備匹配;若|V1|=|V2|,

則完備匹配為完美匹配;若|V1|<|V2|,

則完備匹配為G中最大匹配。V1V2144Hall定理(5.2)定理13.11(Hall定理)

二部圖G

=

<V1,

V2,

E>,

|V1|

|V2|,

G中存在從V1到V2的完備匹配,當且僅當V1中任意k個頂點至少與V2中的k個頂點相鄰

k(k=1..|V1|)。Hall定理：m個男孩的結(jié)婚問題有解

iff對每個正整數(shù)k(1≤k≤m),任意k個男孩所認識的 的總數(shù)至少是k個。145146Hall定理的應用(5.2)定理13.12二部圖G=<V1,V2,E>,V1中各點的度都t，V2中各點的度都

t,則G中存在從

V1到V2的完備匹配。定理13.12

k正則二部圖存在k個邊不重的完美匹配。例：有n男n女參加舞會,每人恰好認識2個異性，則2n個人可同時配對跳舞。147匹配匈牙利算法：輸入：二分圖G=(X,Y,E)結(jié)點標記：0：尚未搜索1：飽和點2：無法擴大匹配148匈牙利算法(5.1)任取一初始匹配M，給飽和點標記為1X中各點都有非0標記？是。M是最大匹配。結(jié)束。否。在X中找一標0的點x，令U={x},V=(U)=V?是。給x標2，轉(zhuǎn)2。否。在(U)-V中找點y，y標記為1？是。有邊yzM。令U=U{z},V=V{y},轉(zhuǎn)3否。存在x到y(tǒng)的可增廣道路P，令M=MP，給x,y標記1，轉(zhuǎn)2匹配x1x2x3x4x5x6y1y2y3y4y5y6149150x1x2x3x4x5x6y1

x1y2

x2y3

x3y4

x4y5

x5y6

x6y1y2y3y4y5y6x1x2x3x4x5x6y1

x1y2

x2y3

x3y4

x4y5

x5y6

x6y1y2y3y4y5y6x5y2y5

X4y6

x2151y4

x3x1x2x3x4x5x6y1y2y3y4y5y6y1y2y3y4y5y6x1x2x3x4x5x6x6y6x5152y5

x4Minimum

coverx1x2x3x4x5x6y1y2y3y4y5y6153154點覆蓋集定義13.3

設(shè)G

=

<V,

E>,

V*V,

若對于e

E,v

V*,

使得:v與e相關(guān)聯(lián),則稱v覆蓋e,并稱V*為G的點覆蓋集或簡稱點覆蓋;若點覆蓋V*的任何真子集都不是點覆蓋,則稱V*是極小點覆蓋;頂點個數(shù)最少的點覆蓋稱為最小的點覆蓋;最小點覆蓋的頂點數(shù)稱為點覆蓋數(shù),記作0(G),簡記為0。點覆蓋集a

b

c

duv

x

y

z155第十四章帶權(quán)圖157帶權(quán)圖與貨郎擔問題(P201)定義給定圖G＝<V,E>，設(shè)W：E→R(R為實數(shù)集)，對G中任意的邊e＝(vi,vj)，設(shè)W(e)＝wij，稱實數(shù)wij為邊e上的權(quán)，稱G為帶權(quán)圖。G中各邊的權(quán)之和稱為G的權(quán)。158貨郎擔問題設(shè)有n個城市，城市之間均有道路，道路的長度均大于或等于0，可能是∞（對應關(guān)聯(lián)的城市之間無交通線）。一個旅行商從某個城市出發(fā)，要經(jīng)過每個城市一次且僅一次，最后回到出發(fā)的城市，問他如何走才能使他走的路線最短？這就是著名的旅行商問題或貨郎擔問題。（TSP問題）(Travelling

Salesman

Problem)貨郎擔問題這個問題可化歸為如下的圖論問題。設(shè)G＝<V,E,W>，為一個n階完全帶權(quán)圖Kn，各邊的權(quán)非負，且有的邊的權(quán)可能為∞。求G中一條最短的

回路，這就是貨郎擔問題的數(shù)學模型。159例例下圖為4階完全帶權(quán)圖K4。求出它的不同的回路，并

最短的

回路。160帶權(quán)圖的說明n階完全帶權(quán)圖

存在(n-1)!/2種不同的回路，經(jīng)過比較，可找出最短回路。n＝4時，有3種不同n＝5時，有12種，n＝6時，有60種，回路。n＝7時，有360種，…，n＝10時，有5×9!=1

814

400種，…。161TSP相關(guān)算法最鄰近法(P216)以v1為起點，形成初始路徑P1＝v1.若已

了k個頂點，形成路徑pk=v1v2…vk,下一步

Pk之外離vk最近的頂點。當

完G中所有頂點后，回到v1得H回路。162TSP問題例14.12aedbca(41)baedcb

(36，最好情況）ac

dabdeca(48, 情況）b95169558127e8163TSP相關(guān)算法例：00164TSP相關(guān)算法最小生成樹法(P218)求G的一棵最小生成樹T。將T中各邊均添加一條權(quán)值相同的平行邊，得圖G*求G*中以某點v出發(fā)的

回路E。從v出發(fā)沿E

G*中各頂點，其原則是：在未

完所有頂點之前，一旦出現(xiàn)重復的頂點就跳過它走到下一個頂點（抄近路法），直到完所有頂點為止，得H回路。作為近似解165TSP相關(guān)算法從b出發(fā)：E回:bcbaeadab

得H圈：bcaedb(41)E回：

baeadabcb

得H圈：baedcb(36最優(yōu))ac

db95169558127e8166167TSP相關(guān)算法定理14.16

設(shè)G中各邊權(quán)值滿足三角不等式，d0是最短H回路，d是由最小生成樹法求出的回路，則d<2d0。TSP相關(guān)算法最小權(quán)匹配法(P219)求G的一棵最小生成樹T。設(shè)T中奇度點集合為V’,求出G[V’]的最小完美匹配M，令G*＝T∪M求G*中以某點v出發(fā)的

回路E。從v出發(fā)沿E

G*中各頂點，其原則是：在未

完所有頂點之前，一旦出現(xiàn)重復的頂點就跳過它走到下一個頂點（抄近路法），直到完所有頂點為止，得H回路。作為近似解168T中奇度點集V’={a,c,d,e}，最小權(quán)匹配M={cd,ae}。從a出發(fā)：E回:aeadcba

得H圈:aedcba(36最優(yōu))b出發(fā)E回：

baeadcb

得H圈：baedcb(36最優(yōu))169TSP相關(guān)算法ac

db959558127

16e8ac

deb95955170TSP相關(guān)算法定理14.17

設(shè)G中各邊權(quán)值滿足三角不等式，d0是最短H回路，d是由最小生成樹法求出的回路，則d<1.5d0。便宜算法便宜算法設(shè)頂點為1,2,…,n令S={2,3,…,n};w(1,1)=0;k=1;T=(1,1)令w(

j,t)=min{w(i,k)|i∈S,k∈T}對T中邊(t,t1),(t,t2),若w(j,t1)-w(t,t1)≤

w(j,t2)-w(t,t2)則將j

到t,t1之間，否則

到t,t2之間S=S-j，若S=,結(jié)束。對所有i∈S,令w(i,k)=min(w(i,k),w(i,j))轉(zhuǎn)b171172便宜算法定理

設(shè)G中各邊權(quán)值滿足三角不等式，d0是最短H回路，d是由便宜算法求出的回路，