離散數(shù)學(xué)第七章圖論

1、第七章圖 論離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM2圖論的起源圖論的起源問題：能否從河岸或小島出發(fā)，不重復(fù)地經(jīng)過所問題：能否從河岸或小島出發(fā)，不重復(fù)地經(jīng)過所有的橋回到原地。有的橋回到原地。ACBDKonigsberg(哥尼斯堡哥尼斯堡)七橋問題七橋問題離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM3 Euler將河岸和小島作為圖的結(jié)點，七座橋為將河岸和小島作為圖的結(jié)點，七座橋為邊，構(gòu)成一個無向重圖，問題化為圖論中簡單道路邊，構(gòu)成一個無向重圖，問題化為圖論中簡單道路的問題。的問題。ACBD Euler (歐拉歐拉) 1736年對這個

2、問題給出了否定的回答。年對這個問題給出了否定的回答。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM4一、圖的基本概念一、圖的基本概念洛杉磯洛杉磯舊金山舊金山芝加哥芝加哥丹佛丹佛華盛頓華盛頓底特律底特律紐約紐約離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM5設(shè)設(shè)A A、B B是兩個集合，稱是兩個集合，稱 A&B=a,b|aA&B=a,b|a A, bA, b BB為為A A與與B B的的無序積無序積。為方便起見，常將無序?qū)榉奖闫鹨?，常將無序?qū),ba,b記為記為(a,b)(a,b)定義定義1.1 1.1 一個一個無向圖無向

3、圖是一個有序的二元組是一個有序的二元組，記為記為G G，其中，其中（1 1）稱為稱為結(jié)點結(jié)點集集，元素稱為，元素稱為結(jié)點結(jié)點或或頂點頂點；（2 2）稱為）稱為邊集邊集，它是無序積，它是無序積V&VV&V的多重子集，的多重子集，其元素稱為其元素稱為無向邊無向邊，簡稱為，簡稱為邊邊。 常把無向圖記為常把無向圖記為G=G=離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM6例例1 1、G G1 1= V Vvv0 0, v, v1 1, v, v2 2,v,v3 3 E E(v(v0 0,v,v2 2),(v),(v0 0,v,v3 3),(v),(v1 1,

4、v,v2 2),(v),(v1 1,v,v3 3),(v),(v2 2，v v3 3)v0v3v2v1G1離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM7G2v0v1v2v3例例2 2、G G2 2= V Vvv0 0, v, v1 1, v, v2 2,v,v3 3 E E(v(v0 0,v,v3 3),(v),(v1 1,v,v3 3),(v),(v1 1,v,v3 3),(v),(v2 2，v v3 3),(v),(v0 0,v,v0 0)平行邊平行邊環(huán)環(huán)G 簡單圖簡單圖（不含平行邊也不含環(huán)）不含平行邊也不含環(huán)）多重圖多重圖離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論

5、論 7/5/2022 12:22 PM8洛杉磯洛杉磯舊金山舊金山芝加哥芝加哥丹佛丹佛華盛頓華盛頓底特律底特律紐約紐約離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM9定義定義1.2 1.2 一個一個有向圖有向圖是一個有序的二元組是一個有序的二元組，記為記為D D，其中，其中（1 1）同無向圖；）同無向圖；（2 2）稱為）稱為邊集邊集，它是笛卡爾積，它是笛卡爾積V VV V的多重子集，的多重子集，其元素稱為其元素稱為有向邊有向邊，簡稱為，簡稱為邊邊。 v0v1v2DD= Vv0, v1, v2， E, , 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:

6、22 PM10例例3、 D=, 其中其中V=v1，v2 ，v3 ，v4 E=, ,v1v2v3v4平行邊平行邊離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM11有時用有時用G泛指圖（有向的或無向的）泛指圖（有向的或無向的）|V(G)|表示表示G的結(jié)點數(shù)的結(jié)點數(shù)|E(G)|表示表示G的邊數(shù)的邊數(shù)有限圖有限圖 |V(G)|和和 |E(G)|均有限均有限n階圖階圖|V(G)|=n零圖零圖 E(G)= 洛杉磯洛杉磯舊金山舊金山芝加哥芝加哥丹佛丹佛華盛頓華盛頓底特律底特律紐約紐約平凡圖平凡圖1階零圖階零圖空圖空圖 V(G)= 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2

7、022 12:22 PM12標定圖標定圖非標定圖非標定圖在無向圖在無向圖G=中，若中，若ek=（vi，vj） ，則，則稱稱vi，vj 為為邊邊ek的的端點端點, ek與與vi或或ek與與vj是是彼此關(guān)聯(lián)的彼此關(guān)聯(lián)的；關(guān)聯(lián)次數(shù)關(guān)聯(lián)次數(shù)鄰接點、鄰接邊鄰接點、鄰接邊v1v2v3v4v5 孤立點孤立點 e1e0e4e3e2e5(v3，v4)離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM13在有向圖在有向圖D=中，若中，若ek= ，則，則稱稱vi為為ek 的的起點起點， vj 為為ek的的終點終點 ；并稱；并稱vi鄰接到鄰接到vj ， vj鄰接于鄰接于vi 。v1v2v3v4

8、離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM14定義定義1.3 1.3 在圖在圖G=G= 中，中，與結(jié)點與結(jié)點v v（v v V V）關(guān)聯(lián)的）關(guān)聯(lián)的邊數(shù)稱為結(jié)點邊數(shù)稱為結(jié)點v v的的度數(shù)，度數(shù)，簡稱簡稱度，度，記為記為deg(v)deg(v)。( (結(jié)點上的環(huán)關(guān)聯(lián)次數(shù)為結(jié)點上的環(huán)關(guān)聯(lián)次數(shù)為2)2)e2v1v2v3v4e4e3e5e1v2e3v4v1v3e1e2e4e5設(shè)設(shè)D=為有向圖，為有向圖，以結(jié)點以結(jié)點v（v V）作為始）作為始點的邊數(shù)稱為點的邊數(shù)稱為v的的出度，出度，記作記作deg+(v)；以以v作為終作為終點的邊數(shù)稱為點的邊數(shù)稱為v的的入度，入度，記作記作

9、deg-(v)稱稱deg+(v)+deg-(v)為為v的度數(shù)，記作的度數(shù)，記作deg(v) deg(v1)=deg(v4)=2 deg(v2)=deg(v3)=3 deg+(v1)=3 deg+(v2)= deg+(v4)=1 deg+(v3)=0 deg-(v1)= deg-(v2)=deg-(v4)=1 deg-(v3)=2 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM15在無向圖在無向圖G G中，中， 令令(G)=maxdeg(v)|v(G)=maxdeg(v)|v V(G)V(G) (G)=mindeg(v)|v(G)=mindeg(v)|v V(G)V(

10、G)最大度最大度最小度最小度類似可定義有向圖的類似可定義有向圖的最大出度最大出度和和最小出度最小出度、最大入最大入度度和和最小入度最小入度。有向圖中，所有結(jié)點的入度之和等于所有結(jié)點的出有向圖中，所有結(jié)點的入度之和等于所有結(jié)點的出度之和。度之和。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM16定理定理1.1 設(shè)設(shè)G=為無向圖，為無向圖， |V(G)|= n，|E(G)|=m，則，則niimv12)deg(e2v1v2v3v4e4e3e5e1對圖的所有頂點的度求和時，得出了什么？對圖的所有頂點的度求和時，得出了什么？即使出現(xiàn)多重邊和環(huán)，這即使出現(xiàn)多重邊和環(huán)，這個式子仍

11、然成立個式子仍然成立握手定理握手定理n=4m=4頂點度之和為頂點度之和為8n=4m=5結(jié)點度之和為結(jié)點度之和為10一個具有一個具有10個頂點，每個頂點，每個結(jié)點的度都為個結(jié)點的度都為6的圖，的圖，有多少條邊？有多少條邊？離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM17定理定理1.2 設(shè)設(shè)D=為為有有向圖，向圖， |V(D)|= n，|E(D)|=m，則，則v2e3v4v1v3e1e2e4e5niimv1)(degniimv1)(degniimv12)deg(n=4m=5結(jié)點入度之和為結(jié)點入度之和為5結(jié)點出度之和為結(jié)點出度之和為5離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論

12、論 7/5/2022 12:22 PM18推論推論 無向圖中度數(shù)為奇數(shù)的結(jié)點個數(shù)是偶數(shù)。無向圖中度數(shù)為奇數(shù)的結(jié)點個數(shù)是偶數(shù)。證明：證明：設(shè)設(shè)V1和和V2分別是偶度結(jié)點和奇度結(jié)點的集合分別是偶度結(jié)點和奇度結(jié)點的集合,則則12iiVviVVv)deg()deg()deg(2viiivvvm偶數(shù)偶數(shù)偶數(shù)偶數(shù)偶數(shù)偶數(shù)因此因此|V2 |為偶數(shù)為偶數(shù)任何圖任何圖e2v1v2v3v4e4e3e1離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM19例例4、已知無向圖已知無向圖G中結(jié)點數(shù)中結(jié)點數(shù)n與邊數(shù)與邊數(shù)m相等，相等，2度度結(jié)點與結(jié)點與3度結(jié)點各度結(jié)點各2個，其余結(jié)點的度數(shù)均為個，

13、其余結(jié)點的度數(shù)均為1，試，試求求G的邊數(shù)的邊數(shù)m。niivm1)deg(2=2 2+ 3 2+ 1 (n-4)=n+62m=n+6m=n m=6解：由握手定理解：由握手定理離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM20定義定義1.4 設(shè)設(shè)G為為n階無向簡單圖，若階無向簡單圖，若G中每一對中每一對結(jié)點之間都有邊，則稱結(jié)點之間都有邊，則稱G為為n階無向完全圖階無向完全圖，簡稱簡稱n階完全圖階完全圖，記作，記作Kn (n1)k1k2k3k4aedcbk5離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM21定義定義1.4 設(shè)設(shè)D為為n階有向簡單

14、圖，若階有向簡單圖，若D中每個結(jié)中每個結(jié)點都鄰接到其余的點都鄰接到其余的n-1個結(jié)點，又鄰接于其余個結(jié)點，又鄰接于其余的的n-1個結(jié)點，則稱個結(jié)點，則稱D為為n階有向完全圖階有向完全圖。k1k3k2離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM22定義定義1.5 1.5 設(shè)設(shè) 為為n n階無向簡單圖，階無向簡單圖，以以V V為結(jié)點集，以所有使為結(jié)點集，以所有使G G成為完全圖成為完全圖K Kn n的添加的添加邊組成的集合為邊集的圖，稱為邊組成的集合為邊集的圖，稱為的相對于完的相對于完全圖的全圖的補圖補圖，記作，記作k4GGG定理定理1.3 n階無向完全圖階無向完全圖

15、Kn的邊數(shù)為的邊數(shù)為n(n-1)/2；n階有向完全圖的邊數(shù)為階有向完全圖的邊數(shù)為？ 。n(n-1)離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM23aedcb圖 K5圖 Gedcbadbaec圖 G1aedcb圖 G3離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM24k4GG離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM25定義定義1.6 設(shè)設(shè)G=，G= 為兩個圖，為兩個圖，若若V V且且E E，則稱，則稱為的為的子圖子圖，G G為為G G的的母圖母圖，記作，記作 ；又若又若V V或或E E，則稱，則稱為的為的

16、真子圖。真子圖。若若V=V，則稱，則稱為的為的生成子圖生成子圖k4G2G1離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM26在下圖中，在下圖中，G1，G2，G3均是均是G的真子圖，其中的真子圖，其中G2、G是是G的生成子圖。的生成子圖。e3e2e1e4e5e7e6abdeGe3e2e1e4abdG1cce3e4e6abdeG2ce4e5adeG3離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM27定義定義1.7 1.7 設(shè)設(shè)G G = V= 是是 的子的子圖，若給定另外一個圖圖，若給定另外一個圖 ，使得使得=E-E=E-E ，且，且中僅包含

17、中僅包含的邊所的邊所關(guān)聯(lián)的結(jié)點，則稱為關(guān)聯(lián)的結(jié)點，則稱為是子圖相對于圖是子圖相對于圖G G的的補圖補圖。 GdbaecdbecGdbaeGdbaeG離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM28定義定義1.8 1.8 設(shè)設(shè)G G1 1=V=,G,G2 2= V= 為兩個無向為兩個無向圖，若存在一一映射圖，若存在一一映射 g g： V V1 1 V V2 2 對于對于 v vi i,v,vj j V V1 1，(v(vi i,v,vj j) ) E E1 1 當且僅當當且僅當 (g(v(g(vi i),g(v),g(vj j) E E2 2, ,并且并且(v(vi

18、 i,v,vj j) )與與(g(v(g(vi i),g(v),g(vj j)的重數(shù)相同，的重數(shù)相同，則稱則稱G G1 1與與G G2 2是是同構(gòu)同構(gòu)的，記作的，記作G G1 1 G G2 2怎樣定義有向圖的同構(gòu)？怎樣定義有向圖的同構(gòu)？離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM29 a d c b b (c)a (b)c (a)d例例7、(d)離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM30彼得松圖彼得松圖(petersen)1234567891012345689710離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:

19、22 PM31離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM32兩個圖同構(gòu)必有：兩個圖同構(gòu)必有：（1）結(jié)點數(shù)相同；）結(jié)點數(shù)相同；（2）邊數(shù)相同；）邊數(shù)相同；（3）度數(shù)列相同）度數(shù)列相同但不是充分條件但不是充分條件（滿足這三個條件的兩圖（滿足這三個條件的兩圖不一定同構(gòu)）不一定同構(gòu)）離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM33例例8、 畫出畫出K4的所有非同構(gòu)的生成子圖。的所有非同構(gòu)的生成子圖。 解：解： K4的所有非同構(gòu)的生成子圖如下圖所示。的所有非同構(gòu)的生成子圖如下圖所示。 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022

20、12:22 PM34二、路與回路二、路與回路定義定義2.1 設(shè)設(shè)為無向標定圖，為無向標定圖，G G中結(jié)點與邊中結(jié)點與邊的交替序列的交替序列 = =v vi0i0e ej1j1v vi1i1e ej2j2e ejljlv vilil稱為稱為v vi0i0到到v vilil的的路路。v vi0i0，v vilil分別稱為分別稱為 的始點和終點，的始點和終點， 中邊的條數(shù)稱為它的中邊的條數(shù)稱為它的長度。長度。 當當v vi0i0= v= vilil時，該路稱為時，該路稱為回路回路。e2v1v2v3v4e4e3e5e1離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM35 若路

21、中沒有重復(fù)的邊，則稱為若路中沒有重復(fù)的邊，則稱為跡跡。若若路路中沒有重復(fù)的點，則稱為中沒有重復(fù)的點，則稱為通路通路。閉的通路稱為閉的通路稱為圈圈。e2v1v2v3v4e4e3e5e1離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM36e3e5e2e1dcbae4（5，1 ，2 ，3，4）是跡，不是通路，因）是跡，不是通路，因為（，）中，均出現(xiàn)了為（，）中，均出現(xiàn)了兩次。（兩次。（c，d，b，c）是圈。）是圈。有向圖中，路、回路等概念與無向圖類似有向圖中，路、回路等概念與無向圖類似離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM37 定理定理2

22、.1 2.1 在在n n階圖中，若從結(jié)點階圖中，若從結(jié)點v vi i到到v vj j（v vi i v vj j）存在一條路，則從存在一條路，則從v vi i到到v vj j存在長度不大于存在長度不大于n-1n-1的路。的路。推論推論 在在n n階圖中，若從階圖中，若從結(jié)點結(jié)點vi到到vj（vivj）存在一存在一條路，則從條路，則從vi到到vj存在長度小于存在長度小于n的通路。的通路。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM38定義定義2.2 2.2 設(shè)無向圖設(shè)無向圖， u,v ，若，若u,v之間存在路，則稱之間存在路，則稱u,v是是連通連通的，記作的，記作u

23、 v 。定義定義2.3 設(shè)無向圖是平凡圖或設(shè)無向圖是平凡圖或G中任何兩個結(jié)中任何兩個結(jié)點都是連通的，則稱點都是連通的，則稱G為為連通圖連通圖，否則稱，否則稱G為為非連非連通圖通圖或或分離圖分離圖。 任意一個連通無向圖的任意一個連通無向圖的任兩個不同結(jié)任兩個不同結(jié)點都存在一條通路。點都存在一條通路。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM39k4 A B W（G）=1W（G）=2 非連通圖可分為幾個不相連通的子圖，非連通圖可分為幾個不相連通的子圖，每一子圖本身都是連通的。稱這幾個子圖為每一子圖本身都是連通的。稱這幾個子圖為的連通分支的連通分支,G,G的連通分支數(shù)

24、記為的連通分支數(shù)記為W W（G G）。）。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM40設(shè)設(shè)G=為無向圖為無向圖(1)設(shè)設(shè)e E，用，用G-e表示從表示從G中去掉邊中去掉邊e，稱為，稱為刪刪除邊除邊e；又設(shè)；又設(shè)E E，用，用G-E 表示從表示從G中刪除中刪除E 中的所有邊，稱為刪除中的所有邊，稱為刪除E 。(2)設(shè)設(shè)v V，用，用G-v表示從表示從G中去掉中去掉v及所關(guān)聯(lián)的及所關(guān)聯(lián)的一切邊，稱為一切邊，稱為刪除結(jié)點刪除結(jié)點v；又設(shè)；又設(shè)V V，用，用G-V 表示從表示從G中刪除中刪除V 中所有結(jié)點，稱為刪除中所有結(jié)點，稱為刪除V 。e離離散散數(shù)數(shù)學(xué)學(xué)第第七七章

25、章 圖圖論論 7/5/2022 12:22 PM41定義定義2.4 2.4 設(shè)無向圖設(shè)無向圖為連通圖，為連通圖， 若存若存在在V1 V ，且，且V1 ，使得，使得W(G-V1) 1， 而對于而對于任意的任意的V2 V1，均有，均有W(G-V2)= 1， 則稱則稱V1是是G的的點割集點割集，若是，若是V1=v，則稱，則稱v為為割點割點。W(G)W(G)離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM42定義定義2.5 2.5 設(shè)無向圖設(shè)無向圖， 若存在若存在E E ，且且E ，使得，使得W(G-E )W(G)，而對于任意的，而對于任意的E E ，均有，均有W(G-E)=

26、W(G)，則稱，則稱E 是是G的的邊割邊割集集，若是，若是E =e，則稱，則稱e為為割邊割邊或或橋橋。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM43定義定義2.6 2.6 設(shè)為非完全的無向連通圖，設(shè)為非完全的無向連通圖， 稱稱 (G)=min|V | | V 為為G的點割集的點割集為為G的的點連通度點連通度（或連通度）（或連通度） 設(shè)為無向連通圖，設(shè)為無向連通圖， 稱稱 (G)=min|E | | E 為為G的邊割集的邊割集為為G的的邊連通度邊連通度。 為了產(chǎn)生一個不連通圖為了產(chǎn)生一個不連通圖需要刪去的最少的點數(shù)需要刪去的最少的點數(shù)易見：非連通圖的點連通度為易見

27、：非連通圖的點連通度為0，邊連通度也為，邊連通度也為0。完全圖完全圖Kn的點連通度為的點連通度為n-1。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM44定理定理2.2 對于任何無向圖對于任何無向圖G，有，有 (G) (G) (G)證明：證明：若若G不連通，則不連通，則 (G)= (G)=0 (G)若若G連通連通 1）證）證 (G)(G) 若若G是平凡圖，則是平凡圖，則 (G)=0 (G) 若若G不是平凡圖，則因每個結(jié)點的所有關(guān)不是平凡圖，則因每個結(jié)點的所有關(guān)聯(lián)的邊必含一個邊割集，所以聯(lián)的邊必含一個邊割集，所以 (G)(G) 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論

28、7/5/2022 12:22 PM452）證）證 (G) (G) 設(shè)設(shè) (G)=1，即有一割邊，則，即有一割邊，則 (G)=1 設(shè)設(shè) (G) 2，離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM46定理定理2.3 一個連通無向圖一個連通無向圖G中的結(jié)點中的結(jié)點v是割點是割點的充分必要條件是存在兩個結(jié)點的充分必要條件是存在兩個結(jié)點u和和w，使得，使得結(jié)點結(jié)點u和和w的每一條路都通過的每一條路都通過v。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM47定義定義2.7 2.7 設(shè)設(shè)D=D=為有向圖，為有向圖， vi，vj V V，若從，若從vi到

29、到vj存在路，則稱存在路，則稱vi可達可達vj ，記作記作vivj，規(guī)定，規(guī)定vivi ，如果，如果vivj，且，且vjvi，則稱則稱vj與與vi是互相可達的，是互相可達的，記作記作vi vj 定義定義2.8 2.8 設(shè)設(shè)D為有向圖為有向圖， vi，vj ，若若vivj，稱稱vi到到vj長度最短的路稱為長度最短的路稱為vi 到到vj的的短程短程線線，短程線的長度稱為短程線的長度稱為vi 到到vj的距離，的距離，記作記作d。易見易見 d 0 d+ d d 如果從如果從vi到到vi不可達，則記為不可達，則記為d = 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM48定義

30、定義2.9 2.9 設(shè)設(shè)D=D=為簡單有向圖，為簡單有向圖，若若 vi，vj V V，vivj與與vjvi至少有一個成立，則稱至少有一個成立，則稱D D是是單側(cè)連通單側(cè)連通圖圖。若對。若對 vi，vj V V，均有，均有vi vj，則稱，則稱D為為強連強連通圖通圖。若在若在D D中略去邊的方向，將它看成無向圖后是中略去邊的方向，將它看成無向圖后是連通圖，連通圖，則稱為則稱為弱連通圖弱連通圖。弱弱連連通通 強強連連通通: 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM49定理定理2.4 2.4 設(shè)設(shè)D D為有向圖，為有向圖，D D是強連通圖當且僅當是強連通圖當且僅當D

31、 D中中存在經(jīng)過每個結(jié)點至少一次的回路存在經(jīng)過每個結(jié)點至少一次的回路。D D是單向連通圖當且僅當是單向連通圖當且僅當D D中存在經(jīng)過每個結(jié)點至少中存在經(jīng)過每個結(jié)點至少一次的路一次的路。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM50定義定義2.10 2.10 在簡單有向圖中，具有強連通性質(zhì)的最在簡單有向圖中，具有強連通性質(zhì)的最大子圖，稱為強分圖；具有單側(cè)連通性質(zhì)的最大子大子圖，稱為強分圖；具有單側(cè)連通性質(zhì)的最大子圖，稱為單側(cè)分圖；具有弱連通性質(zhì)的最大子圖，圖，稱為單側(cè)分圖；具有弱連通性質(zhì)的最大子圖，稱為弱分圖稱為弱分圖。定理定理2.5 2.5 在有向圖在有向圖D

32、D中，它的每個結(jié)點位于且只位中，它的每個結(jié)點位于且只位于一個強分圖中于一個強分圖中。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM51三、圖的矩陣表示三、圖的矩陣表示圖圖G的三種表示方法：的三種表示方法：（1）集合表示）集合表示（2）圖形表示）圖形表示（3）矩陣表示）矩陣表示 1、鄰接矩陣表示、鄰接矩陣表示 2、關(guān)聯(lián)矩陣表示、關(guān)聯(lián)矩陣表示離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM52定義定義3.1 設(shè)無向圖設(shè)無向圖G=是簡單圖，是簡單圖，V=v1,v2,vn, 稱稱(aij)nn為為G的的鄰接矩陣鄰接矩陣，記作，記作A(G)，其中，其

33、中v1v2v3v40 1 1 01 0 1 11 1 0 10 1 1 0A(G)=此矩陣有何特征？此矩陣有何特征？對稱對稱aij=1 （vi，vj） E0 （vi，vj） E 或或i=j第第i行上行上1的個數(shù)等于結(jié)點的個數(shù)等于結(jié)點vi的度數(shù)的度數(shù)離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM53定義定義3.1 設(shè)有向圖設(shè)有向圖D=，V=v1,v2,vn, E=e1,e2,em, 令令aij為頂點為頂點vi鄰接到頂點鄰接到頂點vj的邊的條數(shù)，則稱的邊的條數(shù)，則稱(aij)nn為為D的的鄰接矩陣鄰接矩陣，記作，記作A(D)。v1v2v3v4V1V2V3v4 v1 v2

34、 v3 v4 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0此矩陣有何特征？此矩陣有何特征？A(D)=第第i行上行上1的個數(shù)等于結(jié)點的個數(shù)等于結(jié)點vi的出度，的出度，第第j行上行上1的個數(shù)等于結(jié)點的個數(shù)等于結(jié)點vj的入度的入度離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM54v1v2v3v4 0 1 1 1 1 0 0 0 0 0 0 0 0 0 1 0A(D)=計算計算(A(D)2， (A(D)3v1v2v3v4對無向圖G，計算(A(G)2， (A(G)3離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM55定理定理3.1

35、設(shè)設(shè)A為圖為圖G的鄰接矩陣，的鄰接矩陣，V=v1,v2,vn為為G的結(jié)點集，的結(jié)點集，則則A的的k次冪次冪Ak(k1)中元素中元素aij(k)為為G中中vi到到vj長度為長度為k的路數(shù)，的路數(shù)，其中其中aii(k)為到自身長度為為到自身長度為k的回路數(shù)，而的回路數(shù)，而 aij(k)i=1 j=1n n為為G中長度為中長度為k的路的總數(shù)，的路的總數(shù)， aii(k)i=1n其中其中為為G中長度為中長度為k的回路總數(shù)。的回路總數(shù)。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM56定義定義3.2 設(shè)簡單有向圖設(shè)簡單有向圖D=，V=v1,v2,vn, 令令pij=1 vi可達

36、可達 vj0 否則否則則稱則稱(pij)nn為為D的的可達矩陣可達矩陣，記作，記作P(D)。v1v2v3v4e1e2e3e4e5V1V2V3v4 v1 v2 v3 v4 1 1 1 1 1 1 1 1 0 0 1 0 0 0 1 1P(D)=離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM57無向簡單圖無向簡單圖G定義定義3.3 設(shè)無向圖設(shè)無向圖G=，V=v1,v2,vn, E=e1,e2,em, 令令mij為結(jié)點為結(jié)點vi與邊與邊ej的關(guān)聯(lián)次數(shù)，則稱的關(guān)聯(lián)次數(shù)，則稱(mij)nm為為G的的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣，記作，記作M(G)。v1v2v3v4e1e4e3e2e50

37、0 0 11 1 1 0 00 0 1 1 10 1 0 1 0M(G)=此矩陣有何特征？此矩陣有何特征？離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM58有向簡單圖有向簡單圖D定義定義3.3 設(shè)有向圖設(shè)有向圖D=，V=v1,v2,vn, E=e1,e2,em, 令令則稱則稱(mij)nm為為D的的關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣，記作，記作M(D)。1 vi為為ej的始點的始點 0 vi與與ej不關(guān)聯(lián)不關(guān)聯(lián) -1 vi為為ej的終點的終點 mij=離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM59v1v2v3v4e1e2e3e4e5V1V2V3v4e1

38、 e2 e3 e4 e5 1 0 1 -1 1 0 0 0 1 -1 0 -1 -1 0 0-1 1 0 0 0M(D)=離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM60 【例例8.1.4】 證明在證明在n（n2）個人的團）個人的團體中，總有兩個人在此團體中恰好有相同個數(shù)體中，總有兩個人在此團體中恰好有相同個數(shù)的朋友。的朋友。 解解 以結(jié)點代表人，二人如果是朋友，則以結(jié)點代表人，二人如果是朋友，則在代表他們的結(jié)點間連上一條邊，這樣可得無在代表他們的結(jié)點間連上一條邊，這樣可得無向簡單圖向簡單圖G，每個人的朋友數(shù)即圖中代表它的，每個人的朋友數(shù)即圖中代表它的結(jié)點的度數(shù)，

39、于是問題轉(zhuǎn)化為：結(jié)點的度數(shù)，于是問題轉(zhuǎn)化為：n階無向簡單階無向簡單圖圖G中必有兩個結(jié)點的度數(shù)相同。中必有兩個結(jié)點的度數(shù)相同。 用反證法，設(shè)用反證法，設(shè)G中各頂點的結(jié)數(shù)均不相中各頂點的結(jié)數(shù)均不相同，則度數(shù)列為同，則度數(shù)列為0，1，2，n-1，說明圖中，說明圖中有孤立結(jié)點，這與有有孤立結(jié)點，這與有n-1度結(jié)點相矛盾（因為度結(jié)點相矛盾（因為是簡單圖），所以必有兩個結(jié)點的度數(shù)相同。是簡單圖），所以必有兩個結(jié)點的度數(shù)相同。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM61 【例8.2.1】 一個人帶著一只狼、一只羊和一捆草要渡河，由于船太小，人做擺渡者一次只能運送一個“乘客”

40、，很顯然，如果人不在，狼要吃羊，羊要吃草，問人怎樣才能把它們平安地渡過河去？離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM62 解解 這是通路問題的一個典型實例。用這是通路問題的一個典型實例。用f表表示人，示人，w表示狼，表示狼，s表示羊，表示羊，h表示草。表示草。 集合集合f，w，s，h中能平安在一起的子中能平安在一起的子集有：集有：f，w，s，h，f，w，s，f，s，h，f，w，h，f，w，f，s，f，h，w，h，f，w，s，h。用。用頂點表示渡河過程中的狀態(tài)，狀態(tài)是二元組：頂點表示渡河過程中的狀態(tài)，狀態(tài)是二元組：第一元素是集合第一元素是集合f，w，s，h在渡河

41、過程中在渡河過程中留在原岸的子集，第二元素是在彼岸的子集，留在原岸的子集，第二元素是在彼岸的子集，將一次渡河后代表狀態(tài)變化的頂點間連邊，得將一次渡河后代表狀態(tài)變化的頂點間連邊，得圖圖8.2.1。容易看出，一條路徑就是一種渡河。容易看出，一條路徑就是一種渡河方案。方案。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM63 圖 8.2.1 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM64 【例例8.2.4】 在一次國際會議中，由七人在一次國際會議中，由七人組成的小組組成的小組a,b,c,d,e,f,g中，中，a會英語、阿拉會英語、阿拉伯語；伯

42、語；b會英語、西班牙語；會英語、西班牙語；c會漢語、俄語；會漢語、俄語；d會日語、西班牙語；會日語、西班牙語；e會德語、漢語和法語；會德語、漢語和法語；f會會日語、俄語；日語、俄語；g會英語、法語和德語。問：他們會英語、法語和德語。問：他們中間任何二人是否均可對話（必要時可通過別人中間任何二人是否均可對話（必要時可通過別人翻譯）？翻譯）？dabfgce離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM65 解解 用頂點代表人，如果二人會同一種語用頂點代表人，如果二人會同一種語言，則在代表二人的頂點間連邊，于是得到圖言，則在代表二人的頂點間連邊，于是得到圖8.2.3。問題

43、歸結(jié)為：在這個圖中，任何兩個。問題歸結(jié)為：在這個圖中，任何兩個頂點間是否都存在著通路？由于圖頂點間是否都存在著通路？由于圖8.2.3是一是一個連通圖，因此，必要時通過別人翻譯，他們個連通圖，因此，必要時通過別人翻譯，他們中間任何二人均可對話。中間任何二人均可對話。 在連通圖中，如果刪去一些頂點或邊，在連通圖中，如果刪去一些頂點或邊，則可能會影響圖的連通性。所謂從圖中刪去某則可能會影響圖的連通性。所謂從圖中刪去某個頂點個頂點v，就是將頂點，就是將頂點v和與和與v關(guān)聯(lián)的所有的邊關(guān)聯(lián)的所有的邊均刪去，我們用均刪去，我們用G-v記之，并用記之，并用G-V表示從表示從G中刪去中刪去V的子集的子集V。用。

44、用G-e表示刪去邊表示刪去邊e，用，用G-E表示從表示從G中刪去中刪去E的子集的子集E。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM66【例例8.4.1】 判斷下列各命題是否是真命題。判斷下列各命題是否是真命題。（1）任何有相同頂點數(shù)和邊數(shù)的無向圖都同構(gòu)。）任何有相同頂點數(shù)和邊數(shù)的無向圖都同構(gòu)。（2）圖中的初級回路均是簡單回路。）圖中的初級回路均是簡單回路。（3）任一圖）任一圖G的最大度數(shù)的最大度數(shù)（G）必小于）必小于G的頂點數(shù)。的頂點數(shù)。（4）在）在n（n2）個人中，不認識另外奇數(shù)個人的有）個人中，不認識另外奇數(shù)個人的有偶數(shù)個人。偶數(shù)個人。離離散散數(shù)數(shù)學(xué)學(xué)第第七

45、七章章 圖圖論論 7/5/2022 12:22 PM67 解答與分析解答與分析（1）假命題。兩個圖有相同頂點數(shù)和邊數(shù)是二圖同）假命題。兩個圖有相同頂點數(shù)和邊數(shù)是二圖同構(gòu)的必要條件，而非充分條件。構(gòu)的必要條件，而非充分條件。（2）真命題。由初級回路和簡單回路的定義可知。）真命題。由初級回路和簡單回路的定義可知。（3）假命題。當）假命題。當G非簡單圖時，非簡單圖時，（G）可大于頂點）可大于頂點數(shù)。數(shù)。（4）真命題。將）真命題。將n個人抽象成個人抽象成n個頂點，若兩個人不個頂點，若兩個人不認識，則在他們的對應(yīng)頂點之間畫一條邊，得到無認識，則在他們的對應(yīng)頂點之間畫一條邊，得到無向圖向圖G。G中每個頂點

46、的度數(shù)就是該頂點所對應(yīng)的中每個頂點的度數(shù)就是該頂點所對應(yīng)的人不認識的其他人的個數(shù)，由握手定理的推論可知，人不認識的其他人的個數(shù)，由握手定理的推論可知，G中奇度數(shù)的頂點必有偶數(shù)個。故在中奇度數(shù)的頂點必有偶數(shù)個。故在n個人中，不個人中，不認識另外奇數(shù)個人的有偶數(shù)個人。認識另外奇數(shù)個人的有偶數(shù)個人。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM68 【例例8.4.2】 在六個人的團體中，至少有在六個人的團體中，至少有三個人彼此認識或彼此不認識。三個人彼此認識或彼此不認識。 分析分析 將六個人抽象成六個頂點，若兩個將六個人抽象成六個頂點，若兩個人認識，則在他們的對應(yīng)頂點之間

47、畫一條邊，人認識，則在他們的對應(yīng)頂點之間畫一條邊，得到無向圖得到無向圖G，則，則G是是6階無向簡單圖，階無向簡單圖， 中中的邊則表示他們關(guān)聯(lián)的兩個頂點代表的人彼此的邊則表示他們關(guān)聯(lián)的兩個頂點代表的人彼此不認識，本題即：證明不認識，本題即：證明G或它的補圖或它的補圖 中存中存在在3個頂點彼此鄰接。個頂點彼此鄰接。GG離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM69圖 8.4.1 bca離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM70 解解 因為因為K6是是5-正則圖，所以正則圖，所以vV（G）（）（v（ ），），d（v）在）在G中或在中

48、或在 中大于等于中大于等于3。不妨設(shè)在。不妨設(shè)在G中中d（v）3，則，則v在在G中至少關(guān)聯(lián)三個頂點設(shè)為中至少關(guān)聯(lián)三個頂點設(shè)為a、b、c（見圖（見圖8.4.1），若此三頂點在），若此三頂點在G中彼此不鄰接，則必中彼此不鄰接，則必有三邊（有三邊（a，b）、（）、（a，c）、（）、（b，c）均在）均在 中（圖中虛線），亦即中（圖中虛線），亦即a、b、c三點在三點在 中中彼此鄰接，否則三頂點至少有兩個在彼此鄰接，否則三頂點至少有兩個在G中鄰接，中鄰接，不妨設(shè)（不妨設(shè)（a，b）E（G），則），則v、a、b為在為在G中彼此鄰接的三頂點，故在中彼此鄰接的三頂點，故在G或或 中存在中存在3個個頂點彼此鄰接。頂

49、點彼此鄰接。GGGGG離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM71 【例例8.4.3】 證明無向圖證明無向圖G與其補圖與其補圖 至少有一個是連通圖。至少有一個是連通圖。 分析分析 是是G的補圖，即的補圖，即G是一個無向完是一個無向完全圖。對全圖。對G中任一邊中任一邊e，若，若eE（G），則），則eE（ ）；反之若）；反之若eE（ ），則），則eE（G）。又）。又G與與 有相同的頂點集，故只需考有相同的頂點集，故只需考慮慮G中的任意二頂點。若中的任意二頂點。若G是連通圖，則命題是連通圖，則命題已成立，所以不妨設(shè)已成立，所以不妨設(shè)G不是連通圖。不是連通圖。GGGG

50、離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM72 解解 假設(shè)假設(shè)G不是連通圖，則不是連通圖，則G至少有兩個至少有兩個連通分支，不妨設(shè)為連通分支，不妨設(shè)為G1、G2。對于。對于G中的任意中的任意二頂點二頂點u、v，設(shè)，設(shè)uG1，此時若，此時若vG2，則必，則必有邊（有邊（u，v） ，所以，所以u、v在在 中連通。中連通。此時若此時若vG2，即，即vG1,則必存在頂點則必存在頂點wG2，使得（使得（u，w） 且（且（v，w） ，所，所以以u、v仍在仍在 中連通。故中連通。故 是連通圖。所是連通圖。所以，以，G與其補圖與其補圖 至少有一個是連通圖。至少有一個是連通圖。G

51、GGGGGG離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM73習(xí) 題 八 3設(shè)圖設(shè)圖G有有n個頂點，個頂點，n+1條邊，證明條邊，證明G中至少有一個頂點的度數(shù)大于等于中至少有一個頂點的度數(shù)大于等于3。 4在簡單圖中若頂點數(shù)大于等于在簡單圖中若頂點數(shù)大于等于2，則至，則至少有兩個頂點的度數(shù)相同。少有兩個頂點的度數(shù)相同。 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM74 6G是是n階無向簡單圖，階無向簡單圖，n2為奇數(shù)，為奇數(shù)，則則G與與G所含的奇度數(shù)頂點數(shù)相等。所含的奇度數(shù)頂點數(shù)相等。 7證明圖證明圖8.1中，圖（中，圖（a）與（）與（b

52、）同構(gòu)，）同構(gòu)，圖（圖（c）與（）與（d）不同構(gòu)。）不同構(gòu)。 8畫出畫出4階無向完全圖階無向完全圖K4的所有非同構(gòu)的所有非同構(gòu)的子圖，并指出哪些是生成子圖和生成子圖的的子圖，并指出哪些是生成子圖和生成子圖的互補情況?；パa情況。 9畫出畫出3階有向完全圖的所有非同構(gòu)的階有向完全圖的所有非同構(gòu)的生成子圖，指出每個圖的補圖和生成子圖的互生成子圖，指出每個圖的補圖和生成子圖的互補情況。補情況。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM75 圖 8.1 (c)(d)(b)(a)離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM76 10如果一個圖如

53、果一個圖G同構(gòu)于自己的補圖同構(gòu)于自己的補圖G，則稱該圖為自補圖。則稱該圖為自補圖。 （1）有幾個非同構(gòu)的）有幾個非同構(gòu)的4階和階和5階的自補圖？階的自補圖？ （2）是否有）是否有3階和階和6階的自補圖？階的自補圖？ 11G是是n（n3）階連通圖，）階連通圖，G沒有橋，沒有橋，當且僅當對當且僅當對G的每一對頂點和每一條邊，有一的每一對頂點和每一條邊，有一條連接這兩個頂點而不含這條邊的通路。條連接這兩個頂點而不含這條邊的通路。 12一個連通無向圖一個連通無向圖G中的頂點中的頂點(是割點是割點的充分必要條件是存在兩個頂點的充分必要條件是存在兩個頂點u和和w，使得，使得頂點頂點u和和w之間的每一條路都

54、通過之間的每一條路都通過v。 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM77n 13試求圖8.2中有向圖的所有強分圖、單分圖和弱分圖。n 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM78圖 8.2 1245673離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM79 15證明：圖的每一個頂點和每一條邊證明：圖的每一個頂點和每一條邊都只包含在一個弱分圖中。都只包含在一個弱分圖中。 16有向圖有向圖G如圖如圖8.3所示，計算所示，計算G的鄰的鄰接矩陣的前接矩陣的前4次冪，回答下列問題。次冪，回答下列問題。 （1）

55、G中中v1到到v4的長度為的長度為4的通路有幾條？的通路有幾條？ （2）G中中v1到到v1的長度為的長度為4的回路有幾條？的回路有幾條？離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM80 （3）G中長度為中長度為4的通路總數(shù)是多少？其的通路總數(shù)是多少？其中有多少條是回路？中有多少條是回路？ （4）G中長度小于等于中長度小于等于4的通路有幾條？的通路有幾條？其中有多少條是回路？其中有多少條是回路？ （5）寫出）寫出G的可達矩陣。的可達矩陣。 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM81圖 8.3 1243離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章

56、圖圖論論 7/5/2022 12:22 PM82Konigsberg(Konigsberg(哥尼斯堡哥尼斯堡) )七橋問題七橋問題ACBD問題：能否從河岸或小島出發(fā)，通過每一座橋，問題：能否從河岸或小島出發(fā)，通過每一座橋，而且僅僅通過一次回到原地。而且僅僅通過一次回到原地。離離散散數(shù)數(shù)學(xué)學(xué)第第十十五五章章 歐歐拉拉圖圖與與哈哈密密頓頓圖圖 四、歐拉圖與哈密頓圖四、歐拉圖與哈密頓圖歐拉圖 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM83 Euler(歐拉歐拉)1736年對這個問題，給出了否年對這個問題，給出了否定的回答。將河岸和小島作為圖的結(jié)點，七座定的回答。將河岸

57、和小島作為圖的結(jié)點，七座橋為邊，構(gòu)成一個無向重圖，問題化為圖論中橋為邊，構(gòu)成一個無向重圖，問題化為圖論中跡的問題。跡的問題。定義定義4.14.1 通過圖中通過圖中所有邊所有邊一次且僅一次的路稱為一次且僅一次的路稱為歐拉路歐拉路。 通過圖中通過圖中所有邊所有邊一次且僅一次的回路稱為一次且僅一次的回路稱為歐拉回歐拉回路路。 具有歐拉回路的圖稱為具有歐拉回路的圖稱為歐拉圖歐拉圖，具有，具有歐拉路歐拉路而無而無歐拉回路的圖稱為歐拉回路的圖稱為半歐拉圖半歐拉圖。離離散散數(shù)數(shù)學(xué)學(xué)第第十十五五章章 歐歐拉拉圖圖與與哈哈密密頓頓圖圖 離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM8

58、4離離散散數(shù)數(shù)學(xué)學(xué)第第十十五五章章 歐歐拉拉圖圖與與哈哈密密頓頓圖圖 e2v1v2v3v4e4e3e5e1aedcb離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM85定理定理4.14.1 無向圖無向圖G G是歐拉圖當且僅當是歐拉圖當且僅當G G是連通的，且是連通的，且G G中沒有奇度結(jié)點。中沒有奇度結(jié)點。定理定理4.24.2 無向圖無向圖G G是半歐拉圖當且僅當是半歐拉圖當且僅當G G是連通的，是連通的，且且G G中恰有兩個奇度結(jié)點。中恰有兩個奇度結(jié)點。離離散散數(shù)數(shù)學(xué)學(xué)第第十十五五章章 歐歐拉拉圖圖與與哈哈密密頓頓圖圖 哥尼斯堡七橋問題，由于四個結(jié)點哥尼斯堡七橋問題

59、，由于四個結(jié)點都是奇度結(jié)點，不可能有歐拉回路。都是奇度結(jié)點，不可能有歐拉回路。e2v1v2v3v4e4e3e5e1aedcb離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM86如下圖中（a）是歐拉圖，圖（b）是半歐拉圖，圖（c）既非歐拉圖也非半歐拉圖。e10e1e9e3e4e2e5e6e7e8(a)(b)(c)105432離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM87離離散散數(shù)數(shù)學(xué)學(xué)第第十十五五章章 歐歐拉拉圖圖與與哈哈密密頓頓圖圖 e3e5e2e1dcbae4 定義定義4.14.1 通過圖中通過圖中所有邊所有邊一次且僅一次的單向一次且

60、僅一次的單向路稱為路稱為單向單向歐拉路歐拉路。 通過圖中通過圖中所有邊所有邊一次且僅一次的回路稱為一次且僅一次的回路稱為歐拉回歐拉回路路。 具有歐拉回路的圖稱為具有歐拉回路的圖稱為歐拉圖歐拉圖，具有，具有單向歐拉路單向歐拉路而無歐拉回路的圖稱為而無歐拉回路的圖稱為半歐拉圖半歐拉圖。離離散散數(shù)數(shù)學(xué)學(xué)第第七七章章 圖圖論論 7/5/2022 12:22 PM88離離散散數(shù)數(shù)學(xué)學(xué)第第十十五五章章 歐歐拉拉圖圖與與哈哈密密頓頓圖圖 定理定理4.34.3 有向圖有向圖D D是歐拉圖當且僅當是歐拉圖當且僅當D D是強連是強連通的且每個結(jié)點的入度都等于出度。通的且每個結(jié)點的入度都等于出度。定理定理4.44.4 有向圖有向圖D D是半歐拉