為連通分支課件

第五部分

圖論圖論(GraphTheory)是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述事物之間的某種關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。圖論起源于著名的哥尼斯堡七橋問題。歐拉在1736年用圖的形式解決了這個(gè)問題，證明了這個(gè)問題沒有解，這項(xiàng)工作使歐拉成為圖論的創(chuàng)始人。作為描述事務(wù)之間關(guān)系的手段和工具，目前，圖論在許多領(lǐng)域，諸如，計(jì)算機(jī)科學(xué)、物理學(xué)、化學(xué)、運(yùn)籌學(xué)、信息論、控制論、網(wǎng)絡(luò)通訊、社會(huì)科學(xué)以及經(jīng)濟(jì)管理、軍事、國防、工農(nóng)業(yè)生產(chǎn)等方面都得到廣泛的應(yīng)用，也正是因?yàn)樵诒姸喾矫娴膽?yīng)用中，圖論自身才得到了非常迅速的發(fā)展。

1第五部分圖論圖論(GraphTheory第十四章

圖的基本概念主要內(nèi)容圖通路與回路圖的連通性圖的矩陣表示圖的運(yùn)算預(yù)備知識(shí)無序積——AB={{a,b}|aAbB}，(與笛卡爾積區(qū)別)無序?qū)a,b}記作(a,b)，并且(a,b)=(b,a)多重集合——元素可以重復(fù)出現(xiàn)的集合2第十四章圖的基本概念主要內(nèi)容214.1圖定義14.1

無向圖G是一個(gè)有序二元組G=<V,E>,其中(1)V是非空有窮集，稱為頂點(diǎn)集，其中的元素稱為頂點(diǎn)(2)E是無序積VV的有窮多重子集，稱為邊集，其元素稱為無向邊，簡(jiǎn)稱邊實(shí)例設(shè)V={v1,v2,…,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}則G=<V,E>是無向圖，如右圖所示314.1圖定義14.1無向圖G是一個(gè)有序二元組G=有向圖定義14.2有向圖D=<V,E>,只需注意E是笛卡爾積VV的有窮多重子集。下圖表示的是一個(gè)有向圖，試寫出它的V和E

V={a,b,c,d}E={<a,a>,<a,b>,<a,b>,<a,d>,<c,b>,<d,c>,<c,d>}注意：圖的數(shù)學(xué)定義（D=<V,E>）與圖形表示（上圖）都要熟練掌握，要能夠把兩者互相對(duì)應(yīng)起來4有向圖定義14.2有向圖D=<V,E>,只需注意E是笛相關(guān)概念1.圖①無向圖G，有向圖D（有時(shí)也用G泛指圖）②V(G),E(G),V(D),E(D)，用ek表示無向邊或有向邊2.n階圖3.零圖，n階零圖Nn與平凡圖N14.規(guī)定：空?qǐng)D——5.標(biāo)定圖與非標(biāo)定圖，基圖6.頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系①關(guān)聯(lián)、關(guān)聯(lián)次數(shù)②環(huán)③孤立點(diǎn)7.頂點(diǎn)之間的相鄰與邊相鄰5相關(guān)概念1.圖58.鄰域與關(guān)聯(lián)集①vV(G)(G為無向圖)

v的關(guān)聯(lián)集②vV(D)(D為有向圖)相關(guān)概念68.鄰域與關(guān)聯(lián)集v的關(guān)聯(lián)集②vV(D)(D為有向圖)多重圖與簡(jiǎn)單圖定義14.3(1)無向圖中的平行邊及重?cái)?shù)(2)有向圖中的平行邊及重?cái)?shù)（注意方向性）(3)多重圖——含平行邊的圖(4)簡(jiǎn)單圖——不含平行邊，也不含環(huán)的圖在定義14.3中定義的簡(jiǎn)單圖是極其重要的概念7多重圖與簡(jiǎn)單圖定義14.37頂點(diǎn)的度數(shù)定義14.4(1)設(shè)G=<V,E>為無向圖,vV,d(v)——v的度數(shù),簡(jiǎn)稱度(2)設(shè)D=<V,E>為有向圖,vV,

d(v)——v的出度

d+(v)——v的入度

d(v)——v的度或度數(shù)(3)(G)——最大度,(G)——最小度(4)+(D),+(D),(D),(D),(D),(D)(5)懸掛頂點(diǎn)，懸掛邊，奇度頂點(diǎn)與偶度頂點(diǎn)注意：環(huán)在無向圖和有向圖中的度。8頂點(diǎn)的度數(shù)定義14.48定理14.1設(shè)G=<V,E>為任意無向圖，V={v1,v2,…,vn},|E|=m,則證G中每條邊(包括環(huán))均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，m條邊共提供2m度.

本定理的證明類似于定理14.1定理14.2設(shè)D=<V,E>為任意有向圖，V={v1,v2,…,vn},|E|=m,則握手定理9定理14.1設(shè)G=<V,E>為任意無向圖，V={v1,v握手定理推論推論任何圖(無向或有向)中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù).證設(shè)G=<V,E>為任意圖，令

V1={v|vVd(v)為奇數(shù)}

V2={v|vVd(v)為偶數(shù)}則V1V2=V,V1V2=，由握手定理可知由于2m,均為偶數(shù)，所以為偶數(shù)，但因?yàn)閂1中頂點(diǎn)度數(shù)為奇數(shù)，所以|V1|必為偶數(shù).10握手定理推論推論任何圖(無向或有向)中，奇度頂點(diǎn)的個(gè)例1無向圖G有16條邊，3個(gè)4度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其余頂點(diǎn)度數(shù)均小于3，問G的階數(shù)n為幾？解本題的關(guān)鍵是應(yīng)用握手定理.設(shè)除3度與4度頂點(diǎn)外，還有x個(gè)頂點(diǎn)v1,v2,…,vx，則

d(vi)2，i=1,2,…,x，于是得不等式3224+2x得x4,階數(shù)n4+4+3=11.握手定理應(yīng)用11例1無向圖G有16條邊，3個(gè)4度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其圖的度數(shù)列1.V={v1,v2,…,vn}為無向圖G的頂點(diǎn)集，稱d(v1),d(v2),…,d(vn)為G的度數(shù)列

2.V={v1,v2,…,vn}為有向圖D的頂點(diǎn)集，D的度數(shù)列：d(v1),d(v2),…,d(vn)D的入度列：d+(v1),d+(v2),…,d+(vn)D的出度列：d(v1),d(v2),…,d(vn)3.非負(fù)整數(shù)列d=(d1,d2,…,dn)的可圖化，可簡(jiǎn)單圖化.定理14.3：非負(fù)整數(shù)列d可圖化的充要條件為偶數(shù)。易知：(2,4,6,8,10)是可圖化的（不一定是惟一的圖），而(3,3,3,4)是不可圖化的，定理14.4：n階無向簡(jiǎn)單圖G，(G)≤n-1.12圖的度數(shù)列1.V={v1,v2,…,vn}為無向圖圖的同構(gòu)定義14.5設(shè)G1=<V1,E1>,G2=<V2,E2>為兩個(gè)無向圖(兩個(gè)有向圖)，若存在雙射函數(shù)f:V1V2,對(duì)于vi,vjV1,(vi,vj)E1當(dāng)且僅當(dāng)(f(vi),f(vj))E2

（<vi,vj>E1當(dāng)且僅當(dāng)<f(vi),f(vj)>E2在有向圖中)并且,(vi,vj)（<vi,vj>）與(f(vi),f(vj))（<f(vi),f(vj)>）的重?cái)?shù)相同，則稱G1與G2是同構(gòu)的，記作G1G2.圖之間的同構(gòu)關(guān)系具有自反性、對(duì)稱性和傳遞性.能找到多條同構(gòu)的必要條件，但它們都不是充分條件：①邊數(shù)相同，頂點(diǎn)數(shù)相同;②度數(shù)列相同等若破壞必要條件，則兩圖不同構(gòu)判斷兩個(gè)圖同構(gòu)是個(gè)難題，至今沒有找到簡(jiǎn)便的方法13圖的同構(gòu)定義14.5設(shè)G1=<V1,E1>,G2=<V圖同構(gòu)的實(shí)例圖中(1)與(2)的度數(shù)列相同，它們同構(gòu)嗎？為什么？(1)(2)(3)(4)圖中，(1)與(2)不同構(gòu)（度數(shù)列不同），(3)與(4)也不同構(gòu).

(1)(2)

14圖同構(gòu)的實(shí)例圖中(1)與(2)的度數(shù)列相同，它們同構(gòu)嗎？為什圖同構(gòu)的實(shí)例-彼得松圖15圖同構(gòu)的實(shí)例-彼得松圖15n階完全圖與競(jìng)賽圖定義14.6(1)n階無向完全圖——每個(gè)頂點(diǎn)與其余頂點(diǎn)均相鄰的n階無向簡(jiǎn)單圖，記作Kn(n1)

.簡(jiǎn)單性質(zhì)：邊數(shù)(2)n階有向完全圖——每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的n階有向簡(jiǎn)單圖.簡(jiǎn)單性質(zhì)：(3)n階競(jìng)賽圖——基圖為無向完全圖Kn的n階有向簡(jiǎn)單圖.簡(jiǎn)單性質(zhì)：邊數(shù)

16n階完全圖與競(jìng)賽圖定義14.616n階k正則圖(1)為K5，(2)為3階有向完全圖，(3)為4階競(jìng)賽圖.

(1)(2)(3)定義14.7

k-正則圖——所有頂點(diǎn)度數(shù)都為k的n階無向簡(jiǎn)單圖簡(jiǎn)單性質(zhì)：邊數(shù)（由握手定理得）==k

Kn是n1-正則圖，彼得松圖是3-正則圖17n階k正則圖(1)為K5，(2)為3階有向完全子圖定義14.8

G=<V,E>,G=<V,E>（同為無向圖或有向圖）(1)若VV且EE，則稱G為G的子圖,GG，G為G的母圖(2)若VV或EE，則稱G為G的真子圖(3)若V=V且EE，則稱G為G的生成子圖(4)V的導(dǎo)出子圖——以V（VV且V）為頂點(diǎn)集，V在母圖G中所有出現(xiàn)過的邊作為邊集E的子圖，記作G[V](5)E的導(dǎo)出子圖——以E（EE且E）為邊集，E在母圖G中所有關(guān)聯(lián)的頂點(diǎn)作為頂點(diǎn)集V的子圖，記作G[E]18子圖定義14.8G=<V,E>,G=<V,E>（實(shí)例例2畫出K4的所有非同構(gòu)的生成子圖19實(shí)例例2畫出K4的所有非同構(gòu)的生成子圖19補(bǔ)圖定義14.9設(shè)G=<V,E>為n階無向簡(jiǎn)單圖，以V為頂點(diǎn)集，以使G成為完全圖Kn的所有添加邊組成的集合為邊集的圖，稱為G的補(bǔ)圖，記作.若G,則稱G是自補(bǔ)圖.相對(duì)于K4,求上面圖中所有圖的補(bǔ)圖，并指出哪些是自補(bǔ)圖.問：互為自補(bǔ)圖的兩個(gè)圖的邊數(shù)有何關(guān)系？20補(bǔ)圖定義14.9設(shè)G=<V,E>為n階無向簡(jiǎn)單圖，以V為14.2通路與回路定義14.11給定圖G=<V,E>（無向或有向的標(biāo)定圖），G中頂點(diǎn)與邊的交替序列

=v0e1v1e2…elvl，vi1,vi是ei的端點(diǎn).（ei=(vi1,vi)或ei=<vi1,vi>）(1)通路與回路：就稱為v0到vl的通路，v0和vl為始點(diǎn)和終點(diǎn)，中邊的條數(shù)l稱為長度；若v0=vl，則稱為回路.(2)簡(jiǎn)單通路與回路：若中所有邊各異，稱為簡(jiǎn)單通路，又若v0=vl，稱為簡(jiǎn)單回路(3)初級(jí)通路(路徑)與初級(jí)回路(圈)：中所有頂點(diǎn)各異，則稱為初級(jí)通路(路徑)，又若v0=vl，除v0外所有的頂點(diǎn)各不相同，則稱為初級(jí)回路(圈)。奇圈，偶圈。(4)復(fù)雜通路與回路：中有邊重復(fù)出現(xiàn)2114.2通路與回路定義14.11給定圖G=<V,E>（幾點(diǎn)說明初級(jí)通路(回路)一定是簡(jiǎn)單通路(回路)，簡(jiǎn)單通路(回路)一定是通路(回路)；反之不對(duì)長為1的圈(初級(jí)回路)只能由環(huán)生成；無向圖中兩條平行邊構(gòu)成的圈長度為2；無向簡(jiǎn)單圖中，圈長3；有向簡(jiǎn)單圖中圈的長度2.

不同意義下圈的計(jì)數(shù)①在同構(gòu)意義下，長度相同的圈只有1個(gè)，因?yàn)樗虚L度相同的圈都是同構(gòu)的。②在定義意義下，只要兩個(gè)標(biāo)記序列不同，就認(rèn)為兩個(gè)圈不同。對(duì)于一個(gè)給定的長度為l的圈，在定義意義下，在無向圖中，可以衍生出2l個(gè)不同的圈，在有向圖中則可以衍生出l個(gè)不同的圈。22幾點(diǎn)說明初級(jí)通路(回路)一定是簡(jiǎn)單通路(回路)，簡(jiǎn)單通路(通路與回路的性質(zhì)定理14.5在n階圖G中，若從頂點(diǎn)vi到vj（vivj）存在通路，則從vi到vj存在長度小于或等于n1的通路.推論在n階圖G中，若從頂點(diǎn)vi

到vj（vivj）存在通路，則從vi

到vj存在長度小于或等于n1的初級(jí)通路（路徑）.定理14.6在一個(gè)n階圖G中，若存在vi到自身的回路，則一定存在vi到自身長度小于或等于n的回路.推論在一個(gè)n階圖G中，若存在vi到自身的回路，則一定存在長度小于或等于n的初級(jí)回路.23通路與回路的性質(zhì)定理14.5在n階圖G中，若從頂點(diǎn)vi14.3圖的連通性無向圖的連通性(1)頂點(diǎn)之間的連通關(guān)系：G=<V,E>為無向圖①若vi與vj之間有通路，則稱vi,vj是連通的，記作vivj規(guī)定：vV，vv

②是V上的等價(jià)關(guān)系R={<u,v>|u,v

V且uv}(2)G的連通性與連通分支①若u,vV，uv，則稱G為連通圖，否則稱G非連通圖②V/R={V1,V2,…,Vk}，稱導(dǎo)出子圖G[V1],G[V2],…,G[Vk]為連通分支，圖G的連通分支數(shù)記為p(G)=k(k1)；若G連通，則p(G)=1，若G非連通，則p(G)≥2，n階零圖的連通分支最多，p(Nn)=n2414.3圖的連通性無向圖的連通性24短程線與距離(3)短程線與距離①u與v之間的短程線：uv，u與v之間長度最短的通路②u與v之間的距離：短程線的長度，記為d(u,v)③d(u,v)的性質(zhì)：d(u,v)0,u,v不連通時(shí)d(u,v)=∞d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)（三角不等式）25短程線與距離(3)短程線與距離25圖操作與割集1.圖操作

Gv——從G中將v及關(guān)聯(lián)的邊去掉

GV——從G中刪除V中所有的頂點(diǎn)

Ge——將e從G中去掉

GE——?jiǎng)h除E中所有邊2.點(diǎn)割集與邊割集定義14.15

G=<V,E>,VVV為點(diǎn)割集——p(GV)>p(G)且V有極小性(兩個(gè)條件)v為割點(diǎn)——特殊的點(diǎn)割集V={v}定義14.16

G=<V,E>,EEE是邊割集——p(GE)>p(G)且E有極小性(兩個(gè)條件)e是割邊(橋)——特殊的邊割集E={e}26圖操作與割集1.圖操作26例題例3{v1,v4},{v5},{v6}是點(diǎn)割集，v5,v6是割點(diǎn)。{v2,v5}和{v1,v3,v4}是點(diǎn)割集嗎？{e1,e2},{e1,e3,e5,e6},{e8}等是邊割集，e8是橋。{e7,e9,e5,e6}是邊割集嗎？幾點(diǎn)說明：Kn中無點(diǎn)割集，Nn中既無點(diǎn)割集，也無邊割集，其中Nn為n階零圖。圖G的點(diǎn)(邊)割集可能有多個(gè)，不具有惟一性。若G連通，E為邊割集，則p(GE)=2，V為點(diǎn)割集，則p(GV)227例題例3{v1,v4},{v5},{v6}是點(diǎn)幾點(diǎn)說明點(diǎn)連通度與邊連通度定義14.17設(shè)G為無向連通非完全圖

點(diǎn)連通度—(G)=min{|V|V為點(diǎn)割集}，簡(jiǎn)稱連通度規(guī)定：(Kn)=n1，非連通圖G的(G)=0若(G)k，則稱G為k-連通圖

定義14.18設(shè)G為無向連通圖

邊連通度—(G)=min{|E|E為邊割集}規(guī)定：若G非連通，則(G)=0若(G)r，則稱G是r邊-連通圖圖中，==1，它是1-連通圖和1邊-連通圖28點(diǎn)連通度與邊連通度定義14.17設(shè)G為無向連通非完全圖28幾點(diǎn)說明(Kn)=(Kn)=n1G非連通，則==0若G中有割點(diǎn)，則=1，若有橋，則=1若(G)=k,則G是1-連通圖，2-連通圖，…，k-連通圖，但不是(k+s)-連通圖，s1若(G)=r,則G是1邊-連通圖，2邊-連通圖，…，r邊-連通圖，但不是(r+s)邊-連通圖，s1,,之間的關(guān)系.定理14.7

(G)(G)(G)29幾點(diǎn)說明(Kn)=(Kn)=n129有向圖的連通性定義14.19

D=<V,E>為有向圖vi

可達(dá)vj（vivj）—從vi到vj存在通路。規(guī)定：vivivi與vj相互可達(dá)（vivj）—vivj且vjvi性質(zhì)

具有自反性、傳遞性

具有自反性、對(duì)稱性、傳遞性定義14.20

D=<V,E>為有向圖 vi到vj的短程線—vivj，從vi到vj長度最短的通路 vi到vj的距離—短程線的長度，記為d<vi,vj>定義與無向圖類似，只需注意距離表示法的不同。無向圖中d(vi,vj)，有向圖中d<vi,vj>，因?yàn)閐<vi,vj>無對(duì)稱性30有向圖的連通性定義14.19D=<V,E>為有向圖30有向圖的連通性及分類定義14.21

D=<V,E>為有向圖

D弱連通圖(連通圖)——基圖為連通圖

D單向連通圖——vi,vjV，vivj

或vjvi

至少其一成立

D強(qiáng)連通圖——vi,vjV，vivj易知，強(qiáng)連通單向連通弱連通判別法定理14.8

D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路定理14.9

D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路。31有向圖的連通性及分類定義14.21D=<V,E>為有向圖極大路徑與擴(kuò)大路徑法無向圖中在n階無向圖G=<V,E>中，設(shè)為G中一條路徑，若的始點(diǎn)和終點(diǎn)與外的頂點(diǎn)都不相鄰，就稱是一條極大路徑。對(duì)于G中的任意一條路徑l，若此路徑的始點(diǎn)或終點(diǎn)與l外的頂點(diǎn)相鄰，就把這個(gè)路徑延伸到新的頂點(diǎn)，繼續(xù)這一過程，直到最后不能向外延伸為止。最后總能得到一條極大路徑l+k（長度為l的路徑擴(kuò)大成了長度為l+k的路徑），稱這種構(gòu)造極大路徑的方法為“擴(kuò)大路徑法”.有向圖中類似討論，只需注意，在每步擴(kuò)大中保證有向邊方向與通路方向的一致性。32極大路徑與擴(kuò)大路徑法無向圖中32實(shí)例上圖中，(1)中實(shí)線邊所示的長為2的初始路徑，(2),(3),(4)中實(shí)線邊所示的都是它擴(kuò)展成的極大路徑.還能找到另外的極大路徑嗎？由某條路徑擴(kuò)大出的極大路徑不惟一，極大路徑不一定是圖中最長的路徑

(1)

(2)

(4)

(3)33實(shí)例上圖中，(1)中實(shí)線邊所示的長為2的初始路徑，(2),擴(kuò)大路徑法的應(yīng)用例4設(shè)G為n（n4）階無向簡(jiǎn)單圖，

2，證明G中存在長度

+1的圈.證不妨假設(shè)G為連通圖。任取兩個(gè)頂點(diǎn)，它們之間一定存在路徑0。設(shè)=v0v1…vl是由初始路徑0用擴(kuò)大路徑法的得到的極大路徑，則l（為什么？）.因?yàn)関0不與

外頂點(diǎn)相鄰，又d(v0)

，因而在上除v1外，至少還存在1個(gè)頂點(diǎn)與v0相鄰.設(shè)vt是極大路徑上離

v0最遠(yuǎn)的頂點(diǎn)，于是v0v1…vtv0為G中長度

+1的圈.34擴(kuò)大路徑法的應(yīng)用例4設(shè)G為n（n4）階無向簡(jiǎn)單圖二部圖定義14.23設(shè)G=<V,E>為一個(gè)無向圖，若能將V分成V1和V2(V1V2=V，V1V2=)，使得G中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于V1，另一個(gè)屬于V2，則稱G為二部圖(或稱二分圖、偶圖等)，稱V1和V2為互補(bǔ)頂點(diǎn)子集，常將二部圖G記為<V1,V2,E>.又若G是簡(jiǎn)單二部圖，V1中每個(gè)頂點(diǎn)均與V2中所有的頂點(diǎn)相鄰，則稱G為完全二部圖，記為Kr,s，其中r=|V1|，s=|V2|.注意，n階零圖為二部圖.35二部圖定義14.23設(shè)G=<V,E>為一個(gè)無向圖，若能二部圖的判別法定理14.10無向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中無奇圈。例：由定理14.10可知下圖中各圖都是二部圖，哪些是完全二部圖？哪些圖是同構(gòu)的？36二部圖的判別法定理14.10無向圖G=<V,E>是二部圖14.4圖的矩陣表示無向圖的關(guān)聯(lián)矩陣（對(duì)圖無限制）定義14.23無向圖G=<V,E>，|V|=n，|E|=m，令mij為vi與ej的關(guān)聯(lián)次數(shù)，稱(mij)nm為G的關(guān)聯(lián)矩陣，記為M(G).性質(zhì)3714.4圖的矩陣表示無向圖的關(guān)聯(lián)矩陣（對(duì)圖無限制）37有向圖的關(guān)聯(lián)矩陣（無環(huán)有向圖）定義14.24

有向圖D=<V,E>，令則稱(mij)nm為D的關(guān)聯(lián)矩陣，記為M(D).性質(zhì)

有向圖的關(guān)聯(lián)矩陣38有向圖的關(guān)聯(lián)矩陣（無環(huán)有向圖）有向圖的關(guān)聯(lián)矩陣38有向圖的鄰接矩陣定義14.25設(shè)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令為頂點(diǎn)vi

鄰接到頂點(diǎn)vj邊的條數(shù)，稱為D的鄰接矩陣，記作A(D)，或簡(jiǎn)記為A.(nn)性質(zhì)

39有向圖的鄰接矩陣定義14.25設(shè)有向圖D=<V,E>,推論設(shè)Bl=A+A2+…+Al（l1），則

Bl中元素之和為D中長度小于或等于l的通路數(shù).為D中長度為l的通路總數(shù)，定理14.11設(shè)A為有向圖D的鄰接矩陣，V={v1,v2,…,vn}為頂點(diǎn)集，則A的l次冪Al（l1）中元素為D中vi到vj長度為

l的通路數(shù)，其中為vi到自身長度為

l的回路數(shù)，而為D中長度小于或等于l的回路數(shù)為D中長度為l的回路總數(shù).

鄰接矩陣的應(yīng)用40推論設(shè)Bl=A+A2+…+Al（l1），則為D中長度例5有向圖D如圖所示，求A,A2,A3,A4，并回答諸問題：(1)D中長度為1,2,3,4的通路各有多少條？其中回路分別為多少條？(2)D中長度小于或等于4的通路為多少條？其中有多少條回路？實(shí)例41例5有向圖D如圖所示，求A,A2,A3,A4，并(1)D中長度為1的通路為8條，其中有1條是回路.

D中長度為2的通路為11條，其中有3條是回路.D中長度為3和4的通路分別為14和17條，回路分別為1與3條.(2)D中長度小于等于4的通路為50條，其中有8條是回路.實(shí)例求解42(1)D中長度為1的通路為8條，其中有1條是回路.實(shí)例求解定義14.26設(shè)D=<V,E>為有向圖.V={v1,v2,…,vn},令

稱(pij)nn為D的可達(dá)矩陣，記作P(D)，簡(jiǎn)記為P.(nn)由于viV，vivi，所以P(D)主對(duì)角線上的元素全為1.由定義不難看出,D強(qiáng)連通當(dāng)且僅當(dāng)P(D)為全1矩陣.下圖所示有向圖D的可達(dá)矩陣為有向圖的可達(dá)矩陣43定義14.26設(shè)D=<V,E>為有向圖.V={v1,第十四章

習(xí)題課主要內(nèi)容無向圖、有向圖、關(guān)聯(lián)與相鄰、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖；握手定理與推論；圖的同構(gòu)通路與回路及其分類無向圖的連通性與連通度有向圖的連通性及其分類圖的矩陣表示44第十四章習(xí)題課主要內(nèi)容44基本要求深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們深刻理解圖同構(gòu)、簡(jiǎn)單圖、完全圖、正則圖、子圖、補(bǔ)圖、二部圖的概念以及它們的性質(zhì)及相互之間的關(guān)系記住通路與回路的定義、分類及表示法深刻理解與無向圖連通性、連通度有關(guān)的諸多概念會(huì)判別有向圖連通性的類型熟練掌握用鄰接矩陣及其冪求有向圖中通路與回路數(shù)的方法，會(huì)求可達(dá)矩陣45基本要求深刻理解握手定理及推論的內(nèi)容并能靈活地應(yīng)用它們451．9階無向圖G中，每個(gè)頂點(diǎn)的度數(shù)不是5就是6.證明G中至少有5個(gè)6度頂點(diǎn)或至少有6個(gè)5度頂點(diǎn).練習(xí)1證關(guān)鍵是利用握手定理的推論.方法一：窮舉法設(shè)G中有x個(gè)5度頂點(diǎn)，則必有(9x)個(gè)6度頂點(diǎn)，由握手定理推論可知，(x,9x)只有5種可能：(0,9),(2,7),(4,5),(6,3),(8,1）它們都滿足要求.方法二：反證法否則，由握手定理推論可知，“G至多有4個(gè)5度頂點(diǎn)并且至多有4個(gè)6度頂點(diǎn)”，這與G是9階圖矛盾.461．9階無向圖G中，每個(gè)頂點(diǎn)的度數(shù)不是5就是6.證明G中至2．?dāng)?shù)組2,2,2,2,3,3能簡(jiǎn)單圖化嗎？若能，畫出盡可能多的非同構(gòu)的圖來.練習(xí)2只要能畫出6階無向簡(jiǎn)單圖，就說明它可簡(jiǎn)單圖化.下圖的4個(gè)圖都以此數(shù)列為度數(shù)列，請(qǐng)證明它們彼此不同構(gòu)，都是K6的子圖.472．?dāng)?shù)組2,2,2,2,3,3能簡(jiǎn)單圖化嗎？若能，用擴(kuò)大路徑法證明.情況一：

+.證明D中存在長度

+1的圈.設(shè)

=v0v1…vl為極大路徑，則l

(為什么?).由于d(v0)

，所以在上存在PLAY鄰接到v0，于是情況二：+

，只需注意d+(vl)

+

.3．設(shè)D=<V,E>為有向簡(jiǎn)單圖，已知(D)2，+(D)>0，(D)>0，證明D中存在長度max{+,}+1的圈.為D中長度

+1的有向圈練習(xí)348用擴(kuò)大路徑法證明.PLAY鄰接到v0，于是情況二：+(1)D中有幾種非同構(gòu)的圈？(2)D中有幾種非圈非同構(gòu)的簡(jiǎn)單回路？(3)D是哪類連通圖?(4)D中v1到v4長度為1,2,3,4的通路各多少條？其中幾條是非初級(jí)的簡(jiǎn)單通路？(5)D中v1到v1長度為1,2,3,4的回路各多少條？討論它們的類型.(6)D中長度為4的通路（不含回路）有多少條？(7)D中長度為4的回路有多少條？(8)D中長度4的通路有多少條？其中有幾條是回路？(9)寫出D的可達(dá)矩陣.

4．有向圖D如圖所示，回答下列諸問：練習(xí)449(1)D中有幾種非同構(gòu)的圈？4．有向圖D如圖所示，回答下列解答(1)D中有3種非同構(gòu)的圈，長度分別為1,2,3，請(qǐng)畫出它們的圖形.(2)D中有3種非圈的非同構(gòu)的簡(jiǎn)單回路，它們的長度分別為4,5,6.請(qǐng)畫出它們的圖形來.(3)D是強(qiáng)連通的（為什么？）為解(4)—(8)，只需先求D的鄰接矩陣的前4次冪.

50解答(1)D中有3種非同構(gòu)的圈，長度分別為1,2,3，請(qǐng)畫(4)v1到v4長度為1,2,3,4的通路數(shù)分別為0,0,2,2.其中只有長度為4的兩條是非初級(jí)的簡(jiǎn)單通路（定義意義下），見下圖所示.解答51(4)v1到v4長度為1,2,3,4的通路數(shù)分別為0,0,解答(5)v1到v1長度為1,2,3,4的回路數(shù)分別為1,1,3,5.其中長度為1的是初級(jí)的(環(huán))；長度為2的是復(fù)雜的；長度為3的中有1條是復(fù)雜的，2條是初級(jí)的；長度為4的有1條是復(fù)雜的，有4條是非初級(jí)的簡(jiǎn)單回路.請(qǐng)?jiān)趫D中行遍以上各回路.(6)長度為4的通路(不含回路)為33條.(7)長度為4的回路為11條.(8)長度4的通路88條，其中22條為回路.(9)44的全1矩陣.52解答(5)v1到v1長度為1,2,3,4的回路數(shù)分別為1,極大路徑與擴(kuò)大路徑法無向圖中設(shè)G=<V,E>為n階無向圖，E.設(shè)l為G中一條路徑，若此路徑的始點(diǎn)或終點(diǎn)與通路外的頂點(diǎn)相鄰，就將它們擴(kuò)到通路中來，繼續(xù)這一過程，直到最后得到的通路的兩個(gè)端點(diǎn)不與通路外的頂點(diǎn)相鄰為止.設(shè)最后得到的路徑為l+k（長度為l的路徑擴(kuò)大成了長度為l+k的路徑），稱l+k為“極大路徑”，稱這種構(gòu)造極大路徑的方法為“擴(kuò)大路徑法”.有向圖中類似討論，只需注意，在每步擴(kuò)大中保證有向邊方向與通路方向的一致性.53極大路徑與擴(kuò)大路徑法無向圖中53第五部分

圖論圖論(GraphTheory)是數(shù)學(xué)的一個(gè)分支。它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線所構(gòu)成的圖形，這種圖形通常用來描述事物之間的某種關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線表示相應(yīng)兩個(gè)事物間具有這種關(guān)系。圖論起源于著名的哥尼斯堡七橋問題。歐拉在1736年用圖的形式解決了這個(gè)問題，證明了這個(gè)問題沒有解，這項(xiàng)工作使歐拉成為圖論的創(chuàng)始人。作為描述事務(wù)之間關(guān)系的手段和工具，目前，圖論在許多領(lǐng)域，諸如，計(jì)算機(jī)科學(xué)、物理學(xué)、化學(xué)、運(yùn)籌學(xué)、信息論、控制論、網(wǎng)絡(luò)通訊、社會(huì)科學(xué)以及經(jīng)濟(jì)管理、軍事、國防、工農(nóng)業(yè)生產(chǎn)等方面都得到廣泛的應(yīng)用，也正是因?yàn)樵诒姸喾矫娴膽?yīng)用中，圖論自身才得到了非常迅速的發(fā)展。

54第五部分圖論圖論(GraphTheory第十四章

圖的基本概念主要內(nèi)容圖通路與回路圖的連通性圖的矩陣表示圖的運(yùn)算預(yù)備知識(shí)無序積——AB={{a,b}|aAbB}，(與笛卡爾積區(qū)別)無序?qū)a,b}記作(a,b)，并且(a,b)=(b,a)多重集合——元素可以重復(fù)出現(xiàn)的集合55第十四章圖的基本概念主要內(nèi)容214.1圖定義14.1

無向圖G是一個(gè)有序二元組G=<V,E>,其中(1)V是非空有窮集，稱為頂點(diǎn)集，其中的元素稱為頂點(diǎn)(2)E是無序積VV的有窮多重子集，稱為邊集，其元素稱為無向邊，簡(jiǎn)稱邊實(shí)例設(shè)V={v1,v2,…,v5},E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}則G=<V,E>是無向圖，如右圖所示5614.1圖定義14.1無向圖G是一個(gè)有序二元組G=有向圖定義14.2有向圖D=<V,E>,只需注意E是笛卡爾積VV的有窮多重子集。下圖表示的是一個(gè)有向圖，試寫出它的V和E

V={a,b,c,d}E={<a,a>,<a,b>,<a,b>,<a,d>,<c,b>,<d,c>,<c,d>}注意：圖的數(shù)學(xué)定義（D=<V,E>）與圖形表示（上圖）都要熟練掌握，要能夠把兩者互相對(duì)應(yīng)起來57有向圖定義14.2有向圖D=<V,E>,只需注意E是笛相關(guān)概念1.圖①無向圖G，有向圖D（有時(shí)也用G泛指圖）②V(G),E(G),V(D),E(D)，用ek表示無向邊或有向邊2.n階圖3.零圖，n階零圖Nn與平凡圖N14.規(guī)定：空?qǐng)D——5.標(biāo)定圖與非標(biāo)定圖，基圖6.頂點(diǎn)與邊的關(guān)聯(lián)關(guān)系①關(guān)聯(lián)、關(guān)聯(lián)次數(shù)②環(huán)③孤立點(diǎn)7.頂點(diǎn)之間的相鄰與邊相鄰58相關(guān)概念1.圖58.鄰域與關(guān)聯(lián)集①vV(G)(G為無向圖)

v的關(guān)聯(lián)集②vV(D)(D為有向圖)相關(guān)概念598.鄰域與關(guān)聯(lián)集v的關(guān)聯(lián)集②vV(D)(D為有向圖)多重圖與簡(jiǎn)單圖定義14.3(1)無向圖中的平行邊及重?cái)?shù)(2)有向圖中的平行邊及重?cái)?shù)（注意方向性）(3)多重圖——含平行邊的圖(4)簡(jiǎn)單圖——不含平行邊，也不含環(huán)的圖在定義14.3中定義的簡(jiǎn)單圖是極其重要的概念60多重圖與簡(jiǎn)單圖定義14.37頂點(diǎn)的度數(shù)定義14.4(1)設(shè)G=<V,E>為無向圖,vV,d(v)——v的度數(shù),簡(jiǎn)稱度(2)設(shè)D=<V,E>為有向圖,vV,

d(v)——v的出度

d+(v)——v的入度

d(v)——v的度或度數(shù)(3)(G)——最大度,(G)——最小度(4)+(D),+(D),(D),(D),(D),(D)(5)懸掛頂點(diǎn)，懸掛邊，奇度頂點(diǎn)與偶度頂點(diǎn)注意：環(huán)在無向圖和有向圖中的度。61頂點(diǎn)的度數(shù)定義14.48定理14.1設(shè)G=<V,E>為任意無向圖，V={v1,v2,…,vn},|E|=m,則證G中每條邊(包括環(huán))均有兩個(gè)端點(diǎn)，所以在計(jì)算G中各頂點(diǎn)度數(shù)之和時(shí)，每條邊均提供2度，m條邊共提供2m度.

本定理的證明類似于定理14.1定理14.2設(shè)D=<V,E>為任意有向圖，V={v1,v2,…,vn},|E|=m,則握手定理62定理14.1設(shè)G=<V,E>為任意無向圖，V={v1,v握手定理推論推論任何圖(無向或有向)中，奇度頂點(diǎn)的個(gè)數(shù)是偶數(shù).證設(shè)G=<V,E>為任意圖，令

V1={v|vVd(v)為奇數(shù)}

V2={v|vVd(v)為偶數(shù)}則V1V2=V,V1V2=，由握手定理可知由于2m,均為偶數(shù)，所以為偶數(shù)，但因?yàn)閂1中頂點(diǎn)度數(shù)為奇數(shù)，所以|V1|必為偶數(shù).63握手定理推論推論任何圖(無向或有向)中，奇度頂點(diǎn)的個(gè)例1無向圖G有16條邊，3個(gè)4度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其余頂點(diǎn)度數(shù)均小于3，問G的階數(shù)n為幾？解本題的關(guān)鍵是應(yīng)用握手定理.設(shè)除3度與4度頂點(diǎn)外，還有x個(gè)頂點(diǎn)v1,v2,…,vx，則

d(vi)2，i=1,2,…,x，于是得不等式3224+2x得x4,階數(shù)n4+4+3=11.握手定理應(yīng)用64例1無向圖G有16條邊，3個(gè)4度頂點(diǎn)，4個(gè)3度頂點(diǎn)，其圖的度數(shù)列1.V={v1,v2,…,vn}為無向圖G的頂點(diǎn)集，稱d(v1),d(v2),…,d(vn)為G的度數(shù)列

2.V={v1,v2,…,vn}為有向圖D的頂點(diǎn)集，D的度數(shù)列：d(v1),d(v2),…,d(vn)D的入度列：d+(v1),d+(v2),…,d+(vn)D的出度列：d(v1),d(v2),…,d(vn)3.非負(fù)整數(shù)列d=(d1,d2,…,dn)的可圖化，可簡(jiǎn)單圖化.定理14.3：非負(fù)整數(shù)列d可圖化的充要條件為偶數(shù)。易知：(2,4,6,8,10)是可圖化的（不一定是惟一的圖），而(3,3,3,4)是不可圖化的，定理14.4：n階無向簡(jiǎn)單圖G，(G)≤n-1.65圖的度數(shù)列1.V={v1,v2,…,vn}為無向圖圖的同構(gòu)定義14.5設(shè)G1=<V1,E1>,G2=<V2,E2>為兩個(gè)無向圖(兩個(gè)有向圖)，若存在雙射函數(shù)f:V1V2,對(duì)于vi,vjV1,(vi,vj)E1當(dāng)且僅當(dāng)(f(vi),f(vj))E2

（<vi,vj>E1當(dāng)且僅當(dāng)<f(vi),f(vj)>E2在有向圖中)并且,(vi,vj)（<vi,vj>）與(f(vi),f(vj))（<f(vi),f(vj)>）的重?cái)?shù)相同，則稱G1與G2是同構(gòu)的，記作G1G2.圖之間的同構(gòu)關(guān)系具有自反性、對(duì)稱性和傳遞性.能找到多條同構(gòu)的必要條件，但它們都不是充分條件：①邊數(shù)相同，頂點(diǎn)數(shù)相同;②度數(shù)列相同等若破壞必要條件，則兩圖不同構(gòu)判斷兩個(gè)圖同構(gòu)是個(gè)難題，至今沒有找到簡(jiǎn)便的方法66圖的同構(gòu)定義14.5設(shè)G1=<V1,E1>,G2=<V圖同構(gòu)的實(shí)例圖中(1)與(2)的度數(shù)列相同，它們同構(gòu)嗎？為什么？(1)(2)(3)(4)圖中，(1)與(2)不同構(gòu)（度數(shù)列不同），(3)與(4)也不同構(gòu).

(1)(2)

67圖同構(gòu)的實(shí)例圖中(1)與(2)的度數(shù)列相同，它們同構(gòu)嗎？為什圖同構(gòu)的實(shí)例-彼得松圖68圖同構(gòu)的實(shí)例-彼得松圖15n階完全圖與競(jìng)賽圖定義14.6(1)n階無向完全圖——每個(gè)頂點(diǎn)與其余頂點(diǎn)均相鄰的n階無向簡(jiǎn)單圖，記作Kn(n1)

.簡(jiǎn)單性質(zhì)：邊數(shù)(2)n階有向完全圖——每對(duì)頂點(diǎn)之間均有兩條方向相反的有向邊的n階有向簡(jiǎn)單圖.簡(jiǎn)單性質(zhì)：(3)n階競(jìng)賽圖——基圖為無向完全圖Kn的n階有向簡(jiǎn)單圖.簡(jiǎn)單性質(zhì)：邊數(shù)

69n階完全圖與競(jìng)賽圖定義14.616n階k正則圖(1)為K5，(2)為3階有向完全圖，(3)為4階競(jìng)賽圖.

(1)(2)(3)定義14.7

k-正則圖——所有頂點(diǎn)度數(shù)都為k的n階無向簡(jiǎn)單圖簡(jiǎn)單性質(zhì)：邊數(shù)（由握手定理得）==k

Kn是n1-正則圖，彼得松圖是3-正則圖70n階k正則圖(1)為K5，(2)為3階有向完全子圖定義14.8

G=<V,E>,G=<V,E>（同為無向圖或有向圖）(1)若VV且EE，則稱G為G的子圖,GG，G為G的母圖(2)若VV或EE，則稱G為G的真子圖(3)若V=V且EE，則稱G為G的生成子圖(4)V的導(dǎo)出子圖——以V（VV且V）為頂點(diǎn)集，V在母圖G中所有出現(xiàn)過的邊作為邊集E的子圖，記作G[V](5)E的導(dǎo)出子圖——以E（EE且E）為邊集，E在母圖G中所有關(guān)聯(lián)的頂點(diǎn)作為頂點(diǎn)集V的子圖，記作G[E]71子圖定義14.8G=<V,E>,G=<V,E>（實(shí)例例2畫出K4的所有非同構(gòu)的生成子圖72實(shí)例例2畫出K4的所有非同構(gòu)的生成子圖19補(bǔ)圖定義14.9設(shè)G=<V,E>為n階無向簡(jiǎn)單圖，以V為頂點(diǎn)集，以使G成為完全圖Kn的所有添加邊組成的集合為邊集的圖，稱為G的補(bǔ)圖，記作.若G,則稱G是自補(bǔ)圖.相對(duì)于K4,求上面圖中所有圖的補(bǔ)圖，并指出哪些是自補(bǔ)圖.問：互為自補(bǔ)圖的兩個(gè)圖的邊數(shù)有何關(guān)系？73補(bǔ)圖定義14.9設(shè)G=<V,E>為n階無向簡(jiǎn)單圖，以V為14.2通路與回路定義14.11給定圖G=<V,E>（無向或有向的標(biāo)定圖），G中頂點(diǎn)與邊的交替序列

=v0e1v1e2…elvl，vi1,vi是ei的端點(diǎn).（ei=(vi1,vi)或ei=<vi1,vi>）(1)通路與回路：就稱為v0到vl的通路，v0和vl為始點(diǎn)和終點(diǎn)，中邊的條數(shù)l稱為長度；若v0=vl，則稱為回路.(2)簡(jiǎn)單通路與回路：若中所有邊各異，稱為簡(jiǎn)單通路，又若v0=vl，稱為簡(jiǎn)單回路(3)初級(jí)通路(路徑)與初級(jí)回路(圈)：中所有頂點(diǎn)各異，則稱為初級(jí)通路(路徑)，又若v0=vl，除v0外所有的頂點(diǎn)各不相同，則稱為初級(jí)回路(圈)。奇圈，偶圈。(4)復(fù)雜通路與回路：中有邊重復(fù)出現(xiàn)7414.2通路與回路定義14.11給定圖G=<V,E>（幾點(diǎn)說明初級(jí)通路(回路)一定是簡(jiǎn)單通路(回路)，簡(jiǎn)單通路(回路)一定是通路(回路)；反之不對(duì)長為1的圈(初級(jí)回路)只能由環(huán)生成；無向圖中兩條平行邊構(gòu)成的圈長度為2；無向簡(jiǎn)單圖中，圈長3；有向簡(jiǎn)單圖中圈的長度2.

不同意義下圈的計(jì)數(shù)①在同構(gòu)意義下，長度相同的圈只有1個(gè)，因?yàn)樗虚L度相同的圈都是同構(gòu)的。②在定義意義下，只要兩個(gè)標(biāo)記序列不同，就認(rèn)為兩個(gè)圈不同。對(duì)于一個(gè)給定的長度為l的圈，在定義意義下，在無向圖中，可以衍生出2l個(gè)不同的圈，在有向圖中則可以衍生出l個(gè)不同的圈。75幾點(diǎn)說明初級(jí)通路(回路)一定是簡(jiǎn)單通路(回路)，簡(jiǎn)單通路(通路與回路的性質(zhì)定理14.5在n階圖G中，若從頂點(diǎn)vi到vj（vivj）存在通路，則從vi到vj存在長度小于或等于n1的通路.推論在n階圖G中，若從頂點(diǎn)vi

到vj（vivj）存在通路，則從vi

到vj存在長度小于或等于n1的初級(jí)通路（路徑）.定理14.6在一個(gè)n階圖G中，若存在vi到自身的回路，則一定存在vi到自身長度小于或等于n的回路.推論在一個(gè)n階圖G中，若存在vi到自身的回路，則一定存在長度小于或等于n的初級(jí)回路.76通路與回路的性質(zhì)定理14.5在n階圖G中，若從頂點(diǎn)vi14.3圖的連通性無向圖的連通性(1)頂點(diǎn)之間的連通關(guān)系：G=<V,E>為無向圖①若vi與vj之間有通路，則稱vi,vj是連通的，記作vivj規(guī)定：vV，vv

②是V上的等價(jià)關(guān)系R={<u,v>|u,v

V且uv}(2)G的連通性與連通分支①若u,vV，uv，則稱G為連通圖，否則稱G非連通圖②V/R={V1,V2,…,Vk}，稱導(dǎo)出子圖G[V1],G[V2],…,G[Vk]為連通分支，圖G的連通分支數(shù)記為p(G)=k(k1)；若G連通，則p(G)=1，若G非連通，則p(G)≥2，n階零圖的連通分支最多，p(Nn)=n7714.3圖的連通性無向圖的連通性24短程線與距離(3)短程線與距離①u與v之間的短程線：uv，u與v之間長度最短的通路②u與v之間的距離：短程線的長度，記為d(u,v)③d(u,v)的性質(zhì)：d(u,v)0,u,v不連通時(shí)d(u,v)=∞d(u,v)=d(v,u)d(u,v)+d(v,w)d(u,w)（三角不等式）78短程線與距離(3)短程線與距離25圖操作與割集1.圖操作

Gv——從G中將v及關(guān)聯(lián)的邊去掉

GV——從G中刪除V中所有的頂點(diǎn)

Ge——將e從G中去掉

GE——?jiǎng)h除E中所有邊2.點(diǎn)割集與邊割集定義14.15

G=<V,E>,VVV為點(diǎn)割集——p(GV)>p(G)且V有極小性(兩個(gè)條件)v為割點(diǎn)——特殊的點(diǎn)割集V={v}定義14.16

G=<V,E>,EEE是邊割集——p(GE)>p(G)且E有極小性(兩個(gè)條件)e是割邊(橋)——特殊的邊割集E={e}79圖操作與割集1.圖操作26例題例3{v1,v4},{v5},{v6}是點(diǎn)割集，v5,v6是割點(diǎn)。{v2,v5}和{v1,v3,v4}是點(diǎn)割集嗎？{e1,e2},{e1,e3,e5,e6},{e8}等是邊割集，e8是橋。{e7,e9,e5,e6}是邊割集嗎？幾點(diǎn)說明：Kn中無點(diǎn)割集，Nn中既無點(diǎn)割集，也無邊割集，其中Nn為n階零圖。圖G的點(diǎn)(邊)割集可能有多個(gè)，不具有惟一性。若G連通，E為邊割集，則p(GE)=2，V為點(diǎn)割集，則p(GV)280例題例3{v1,v4},{v5},{v6}是點(diǎn)幾點(diǎn)說明點(diǎn)連通度與邊連通度定義14.17設(shè)G為無向連通非完全圖

點(diǎn)連通度—(G)=min{|V|V為點(diǎn)割集}，簡(jiǎn)稱連通度規(guī)定：(Kn)=n1，非連通圖G的(G)=0若(G)k，則稱G為k-連通圖

定義14.18設(shè)G為無向連通圖

邊連通度—(G)=min{|E|E為邊割集}規(guī)定：若G非連通，則(G)=0若(G)r，則稱G是r邊-連通圖圖中，==1，它是1-連通圖和1邊-連通圖81點(diǎn)連通度與邊連通度定義14.17設(shè)G為無向連通非完全圖28幾點(diǎn)說明(Kn)=(Kn)=n1G非連通，則==0若G中有割點(diǎn)，則=1，若有橋，則=1若(G)=k,則G是1-連通圖，2-連通圖，…，k-連通圖，但不是(k+s)-連通圖，s1若(G)=r,則G是1邊-連通圖，2邊-連通圖，…，r邊-連通圖，但不是(r+s)邊-連通圖，s1,,之間的關(guān)系.定理14.7

(G)(G)(G)82幾點(diǎn)說明(Kn)=(Kn)=n129有向圖的連通性定義14.19

D=<V,E>為有向圖vi

可達(dá)vj（vivj）—從vi到vj存在通路。規(guī)定：vivivi與vj相互可達(dá)（vivj）—vivj且vjvi性質(zhì)

具有自反性、傳遞性

具有自反性、對(duì)稱性、傳遞性定義14.20

D=<V,E>為有向圖 vi到vj的短程線—vivj，從vi到vj長度最短的通路 vi到vj的距離—短程線的長度，記為d<vi,vj>定義與無向圖類似，只需注意距離表示法的不同。無向圖中d(vi,vj)，有向圖中d<vi,vj>，因?yàn)閐<vi,vj>無對(duì)稱性83有向圖的連通性定義14.19D=<V,E>為有向圖30有向圖的連通性及分類定義14.21

D=<V,E>為有向圖

D弱連通圖(連通圖)——基圖為連通圖

D單向連通圖——vi,vjV，vivj

或vjvi

至少其一成立

D強(qiáng)連通圖——vi,vjV，vivj易知，強(qiáng)連通單向連通弱連通判別法定理14.8

D強(qiáng)連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的回路定理14.9

D單向連通當(dāng)且僅當(dāng)D中存在經(jīng)過每個(gè)頂點(diǎn)至少一次的通路。84有向圖的連通性及分類定義14.21D=<V,E>為有向圖極大路徑與擴(kuò)大路徑法無向圖中在n階無向圖G=<V,E>中，設(shè)為G中一條路徑，若的始點(diǎn)和終點(diǎn)與外的頂點(diǎn)都不相鄰，就稱是一條極大路徑。對(duì)于G中的任意一條路徑l，若此路徑的始點(diǎn)或終點(diǎn)與l外的頂點(diǎn)相鄰，就把這個(gè)路徑延伸到新的頂點(diǎn)，繼續(xù)這一過程，直到最后不能向外延伸為止。最后總能得到一條極大路徑l+k（長度為l的路徑擴(kuò)大成了長度為l+k的路徑），稱這種構(gòu)造極大路徑的方法為“擴(kuò)大路徑法”.有向圖中類似討論，只需注意，在每步擴(kuò)大中保證有向邊方向與通路方向的一致性。85極大路徑與擴(kuò)大路徑法無向圖中32實(shí)例上圖中，(1)中實(shí)線邊所示的長為2的初始路徑，(2),(3),(4)中實(shí)線邊所示的都是它擴(kuò)展成的極大路徑.還能找到另外的極大路徑嗎？由某條路徑擴(kuò)大出的極大路徑不惟一，極大路徑不一定是圖中最長的路徑

(1)

(2)

(4)

(3)86實(shí)例上圖中，(1)中實(shí)線邊所示的長為2的初始路徑，(2),擴(kuò)大路徑法的應(yīng)用例4設(shè)G為n（n4）階無向簡(jiǎn)單圖，

2，證明G中存在長度

+1的圈.證不妨假設(shè)G為連通圖。任取兩個(gè)頂點(diǎn)，它們之間一定存在路徑0。設(shè)=v0v1…vl是由初始路徑0用擴(kuò)大路徑法的得到的極大路徑，則l（為什么？）.因?yàn)関0不與

外頂點(diǎn)相鄰，又d(v0)

，因而在上除v1外，至少還存在1個(gè)頂點(diǎn)與v0相鄰.設(shè)vt是極大路徑上離

v0最遠(yuǎn)的頂點(diǎn)，于是v0v1…vtv0為G中長度

+1的圈.87擴(kuò)大路徑法的應(yīng)用例4設(shè)G為n（n4）階無向簡(jiǎn)單圖二部圖定義14.23設(shè)G=<V,E>為一個(gè)無向圖，若能將V分成V1和V2(V1V2=V，V1V2=)，使得G中的每條邊的兩個(gè)端點(diǎn)都是一個(gè)屬于V1，另一個(gè)屬于V2，則稱G為二部圖(或稱二分圖、偶圖等)，稱V1和V2為互補(bǔ)頂點(diǎn)子集，常將二部圖G記為<V1,V2,E>.又若G是簡(jiǎn)單二部圖，V1中每個(gè)頂點(diǎn)均與V2中所有的頂點(diǎn)相鄰，則稱G為完全二部圖，記為Kr,s，其中r=|V1|，s=|V2|.注意，n階零圖為二部圖.88二部圖定義14.23設(shè)G=<V,E>為一個(gè)無向圖，若能二部圖的判別法定理14.10無向圖G=<V,E>是二部圖當(dāng)且僅當(dāng)G中無奇圈。例：由定理14.10可知下圖中各圖都是二部圖，哪些是完全二部圖？哪些圖是同構(gòu)的？89二部圖的判別法定理14.10無向圖G=<V,E>是二部圖14.4圖的矩陣表示無向圖的關(guān)聯(lián)矩陣（對(duì)圖無限制）定義14.23無向圖G=<V,E>，|V|=n，|E|=m，令mij為vi與ej的關(guān)聯(lián)次數(shù)，稱(mij)nm為G的關(guān)聯(lián)矩陣，記為M(G).性質(zhì)9014.4圖的矩陣表示無向圖的關(guān)聯(lián)矩陣（對(duì)圖無限制）37有向圖的關(guān)聯(lián)矩陣（無環(huán)有向圖）定義14.24

有向圖D=<V,E>，令則稱(mij)nm為D的關(guān)聯(lián)矩陣，記為M(D).性質(zhì)

有向圖的關(guān)聯(lián)矩陣91有向圖的關(guān)聯(lián)矩陣（無環(huán)有向圖）有向圖的關(guān)聯(lián)矩陣38有向圖的鄰接矩陣定義14.25設(shè)有向圖D=<V,E>,V={v1,v2,…,vn},E={e1,e2,…,em},令為頂點(diǎn)vi

鄰接到頂點(diǎn)vj邊的條數(shù)，稱為D的鄰接矩陣，記作A(D)，或簡(jiǎn)記為A.(nn)性質(zhì)

92有向圖的鄰接矩陣定義14.25設(shè)有向圖D=<V,E>,推論設(shè)Bl=A+A2+…+Al（l1），則

Bl中元素之和為D中長度小于或等于l的通路數(shù).為D中長度為l的通路總數(shù)，定理14.11設(shè)A為有向圖D的鄰接矩陣，V={v1,v2,…,vn}為頂點(diǎn)集，則A的l次冪Al（l1）中元素為D中vi到vj長度為

l的通路數(shù)，其中為vi到自身長度為

l的回路數(shù)，而為D中長