1Chapter6圖論圖論是一個(gè)古老的數(shù)學(xué)分支,它以圖為研究對(duì)象。圖論中的圖是由若干給定的點(diǎn)及連接兩點(diǎn)的線(xiàn)所構(gòu)成的圖形，這種圖形通常用來(lái)描述某些事物之間的某種特定關(guān)系，用點(diǎn)代表事物，用連接兩點(diǎn)的線(xiàn)表示相應(yīng)兩個(gè)事物間具有這種關(guān)系.圖論近年來(lái)發(fā)展十分迅速,應(yīng)用相當(dāng)廣泛,滲透到許多學(xué)科,諸如運(yùn)籌學(xué)、信息論、控制論、網(wǎng)絡(luò)理論、博弈論、化學(xué)、生物學(xué)、物理學(xué)、社會(huì)科學(xué)、語(yǔ)言學(xué),特別是計(jì)算機(jī)科學(xué)等,圖論得到廣泛的應(yīng)用,同時(shí)圖論本身也得到了充分的發(fā)展.例：有7個(gè)人圍桌而坐，如果要求每次相鄰的人都與以前完全不同，試問(wèn)不同的就座方案共有多少種？用頂點(diǎn)表示人，用邊表示兩者相鄰，因?yàn)樽畛跞魏蝺蓚€(gè)人都允許相鄰，所以任何兩點(diǎn)都可以有邊相連。212376453假定第一次就座方案是（1，2，3，4，5，6，7，1），那么第二次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰，只能從圖中刪去這些邊。41237645512376456123764571237645812376459123764510123764511123764512假定第二次就座方案是（1，3，5，7，2，4，6，1），那么第三次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰，只能從圖中刪去這些邊。13123764514123764515123764516123764517123764518123764519123764520123764521123764522123764523123764524123764525123764526123764527123764528123764529假定第三次就座方案是（1，4，7，3，6，2，5，1），那么第四次就座方案就不允許這些頂點(diǎn)之間繼續(xù)相鄰，只能從圖中刪去這些邊，只留下7點(diǎn)孤立點(diǎn)，所以該問(wèn)題只有三個(gè)就座方案。30例：一個(gè)班級(jí)的學(xué)生共計(jì)選修A、B、C、D、E、F六門(mén)課程，其中一部分人同時(shí)選修D(zhuǎn)、C、A，一部分人同時(shí)選修B、C、F，一部分人同時(shí)選修B、E，還有一部分人同時(shí)選修A、B，期終考試要求每天考一門(mén)課，六天內(nèi)考完，為了減輕學(xué)生負(fù)擔(dān)，要求每人都不會(huì)連續(xù)參加考試，試設(shè)計(jì)一個(gè)考試日程表。31解：以每門(mén)課程為一個(gè)頂點(diǎn)，共同被選修的課程之間用邊相連，得圖，按題意，相鄰頂點(diǎn)對(duì)應(yīng)課程不能連續(xù)考試，不相鄰頂點(diǎn)對(duì)應(yīng)課程允許連續(xù)考試，因此，作圖的補(bǔ)圖，問(wèn)題是在圖中尋找一條哈密頓道路，如C—E—A—F—D—B，就是一個(gè)符合要求的考試課程表。32AFEDCB33AFEDCB34AFEDCB35AFEDCB36AFEDCB37AFEDCB38AFEDCB39AFEDCB40

圖論最早處理的問(wèn)題是哥尼斯堡城Pregel河上的七橋問(wèn)題：河中有兩個(gè)島嶼,人們架設(shè)了七座橋把河岸和兩個(gè)小島連接起來(lái),有人打算在每座橋上通過(guò)一次然后返回出發(fā)點(diǎn),但沒(méi)有獲得成功.后來(lái)有人請(qǐng)教當(dāng)時(shí)的大數(shù)學(xué)家歐拉,歐拉用圖論的方法證明這個(gè)問(wèn)題無(wú)解,同時(shí)他提出并解決了更為一般的問(wèn)題,從而奠定了圖論的基礎(chǔ),歐拉也被譽(yù)為“圖論之父”.

ABCD41

后來(lái),英國(guó)數(shù)學(xué)家哈密爾頓在1856年提出“周游世界”的問(wèn)題：一個(gè)正十二面體,20個(gè)頂點(diǎn)分別表示世界上20個(gè)大城市,要求從某個(gè)城市出發(fā),經(jīng)過(guò)所有城市一次而不重復(fù),最后回到出發(fā)地.這也是圖論中一個(gè)著名的問(wèn)題.

“四色問(wèn)題”也是圖論中的著名問(wèn)題：地圖著色時(shí),國(guó)境線(xiàn)相鄰的國(guó)家需要著上不同的顏色,最少需要幾種顏色？1976年,美國(guó)人阿佩爾和哈肯用計(jì)算機(jī)運(yùn)行1200個(gè)小時(shí),證明4種顏色就夠了.但至今尚有爭(zhēng)議.42436.1圖的基本概念哥尼斯堡(K?ningsberg)七橋問(wèn)題:問(wèn)題是:是否可從某一個(gè)地方出發(fā)，經(jīng)過(guò)七座橋，每座橋只經(jīng)過(guò)一次，然后又回到原出發(fā)點(diǎn).ABCDABCD44程序調(diào)用的圖論模型:e8:v3可調(diào)用v2;e1:v2可調(diào)用v1;e4:v5可調(diào)用v5自身.45圖的定義定義

圖G主要由2部分組成:(1)節(jié)點(diǎn)集合V,其中的元素稱(chēng)為節(jié)點(diǎn)(2)邊集合E,其中的元素稱(chēng)為邊通常將圖G記為G=(V,E).46幾點(diǎn)說(shuō)明:(a)節(jié)點(diǎn)又可以稱(chēng)為點(diǎn)、頂點(diǎn)或結(jié)點(diǎn),常用一個(gè)實(shí)心點(diǎn)或空心點(diǎn)表示,為了方便可以在這些符號(hào)的旁邊或內(nèi)部寫(xiě)上表意名稱(chēng).(b)邊及其表示.無(wú)向邊?b3=AB=BA={A,B}(可重).有向邊(弧)?所有邊都是無(wú)向邊的圖稱(chēng)為無(wú)向圖,所有邊都是有向邊的圖稱(chēng)為有向圖.ABv2v3b3e8A和B稱(chēng)為端點(diǎn)47(c)我們討論的圖不但與節(jié)點(diǎn)位置無(wú)關(guān),而且與邊的形狀和長(zhǎng)短也無(wú)關(guān).有n個(gè)節(jié)點(diǎn)的圖稱(chēng)為n階圖,

有n個(gè)節(jié)點(diǎn)m條邊的圖稱(chēng)為(n,m)圖.在圖G=(V,E)中,稱(chēng)V=的圖為空?qǐng)D,記為,若V

但E=的圖稱(chēng)為零圖,n階零圖可記為Nn,僅一個(gè)節(jié)點(diǎn)的零圖稱(chēng)為平凡圖.47482.鄰接定義設(shè)G=(V,E)是圖,對(duì)于任意u,v

V,若從節(jié)點(diǎn)u到節(jié)點(diǎn)v有邊,則稱(chēng)u鄰接到

v或稱(chēng)u和v是鄰接的.無(wú)向圖?有向圖?無(wú)向圖的兩條邊鄰接是指它們有公共端點(diǎn).先驅(qū)元素后繼元素493.關(guān)聯(lián)定義設(shè)G=(V,E)是圖,e

E,e的兩個(gè)端點(diǎn)分別為u和v,則稱(chēng)邊e與節(jié)點(diǎn)u以及邊e與節(jié)點(diǎn)v是關(guān)聯(lián)的.顯然,圖的任意一條邊都關(guān)聯(lián)兩個(gè)節(jié)點(diǎn).關(guān)聯(lián)相同兩個(gè)節(jié)點(diǎn)的邊稱(chēng)為吊環(huán),可簡(jiǎn)稱(chēng)環(huán)(loop).關(guān)聯(lián)的起點(diǎn)與終點(diǎn)都相同的邊稱(chēng)為多重邊或平行邊,其邊數(shù)稱(chēng)為邊的重?cái)?shù).uuvuv504.簡(jiǎn)單圖(1)簡(jiǎn)單圖定義設(shè)G=(V,E)是圖,若G中既無(wú)吊環(huán)又無(wú)多重邊,則稱(chēng)G是簡(jiǎn)單圖.SanFranciscoDenverLosAngelesNewYorkChicagoWashingtonDetroit51(2)完全無(wú)向圖定義設(shè)G=(V,E)是n階簡(jiǎn)單無(wú)向圖,若G中任意節(jié)點(diǎn)都與其余n-1個(gè)節(jié)點(diǎn)鄰接,則稱(chēng)G為n階完全無(wú)向圖,記為Kn.

K1K4K3K2K552(3)補(bǔ)圖定義設(shè)G=(V,E)是n階簡(jiǎn)單無(wú)向圖,由G的所有節(jié)點(diǎn)以及由能使G成為Kn需要添加的邊構(gòu)成的圖稱(chēng)為G的補(bǔ)圖,記為(u和v在G中不鄰接u和v在中鄰接)53作業(yè)P162習(xí)題6.1953546.2節(jié)點(diǎn)的度數(shù)邊與節(jié)點(diǎn)的關(guān)聯(lián)次數(shù)定義設(shè)G=(V,E)是無(wú)向圖,v

V,稱(chēng)與節(jié)點(diǎn)v關(guān)聯(lián)的所有邊的關(guān)聯(lián)次數(shù)之和為節(jié)點(diǎn)v的度數(shù),記為deg(v).在任意圖中,度數(shù)為0的節(jié)點(diǎn)稱(chēng)為孤立點(diǎn),度數(shù)為1的節(jié)點(diǎn)稱(chēng)為懸掛點(diǎn).一個(gè)環(huán)算2度deg(a

)=2deg(b

)=6deg(c

)=4deg(d)=1deg(e)=0deg(f)=3deg(g)=4

a

b

g

e

c

d

f所有節(jié)點(diǎn)度數(shù)之和=2+4+3+4+6+1+0=20邊數(shù)

=10e為孤立點(diǎn).d為懸掛點(diǎn).55握手定理在任何(n,m)圖G=(V,E)中,其所有節(jié)點(diǎn)度數(shù)之和等于邊數(shù)m的2倍,即Corollary在任意圖G=(V,E)中,度數(shù)為奇數(shù)的節(jié)點(diǎn)個(gè)數(shù)必為偶數(shù).Proof偶數(shù)偶數(shù)偶數(shù)5657定義設(shè)G=(V,E)是有向圖,v

V,以v為起點(diǎn)的邊的數(shù)目為節(jié)點(diǎn)的出度,記為deg+(v),以v為終點(diǎn)的邊的數(shù)目為節(jié)點(diǎn)的入度,記為deg-(v),deg+(v)+deg-(v)為節(jié)點(diǎn)v的度數(shù),記為deg

(v).一個(gè)環(huán)算2度acbedfdeg(a)=2deg(b)=2deg(c)=3deg(d)=2deg(e)=3deg(f)=0Total=12deg+(a)=4deg+(b)=1deg+(c)=2deg+(d)=2deg+(e)=3deg+(f)=0Total=12邊數(shù):12Theorem在任意有向圖中,所有節(jié)點(diǎn)的出度之和等于入度之和.5859定義若一個(gè)無(wú)向圖G的每節(jié)點(diǎn)度數(shù)均為k,則稱(chēng)G為k-正則圖.例例

設(shè)無(wú)向圖G是一個(gè)3-正則(n,m)圖,且2n–3=m,求n和m各是多少?解根據(jù)握手定理有,3n=2m，

n=6，m=9。60定義對(duì)于無(wú)向圖G=(V,E),V={v1,v2,…,vn},稱(chēng)deg(v1),deg(v2),…,deg(vn)為G的度數(shù)序列.對(duì)于有向圖,還可以定義其出度序列和入度序列.例是否存在一個(gè)無(wú)向圖G,其度數(shù)序列分別為(1)7,5,4,2,2,1.(2)4,4,3,3,2,2.解(1)由于序列7,5,4,2,2,1中,奇數(shù)個(gè)數(shù)為奇數(shù),根據(jù)握手定理的推論知,不可能存在一個(gè)圖其度數(shù)序列為7,5,4,2,2,1.(2)因?yàn)樾蛄?,4,3,3,2,2中,奇數(shù)個(gè)數(shù)為偶數(shù),可以得到一個(gè)無(wú)向圖,其度數(shù)序列為4,4,3,3,2,2.作業(yè)

P165習(xí)題6.22,7616.3子圖、圖的運(yùn)算和圖同構(gòu)1.子圖可以通過(guò)一個(gè)圖的子圖去考察原圖的有關(guān)性質(zhì)以及原圖的局部結(jié)構(gòu).定義設(shè)G=(V,E)和H=(W,F)是圖,若W

V且F

E,則稱(chēng)H=(W,F)是G=(V,E)的子圖;若H=(W,F)是G=(V,E)的子圖且W

=V,則稱(chēng)H=(W,F)是G=(V,E)的生成子圖.62例

(一個(gè)圖的子圖較多)常見(jiàn)的4種產(chǎn)生G=(V,E)的子圖的方式如下:(1)G[W]設(shè)W

V,則以W為節(jié)點(diǎn)集合,以?xún)啥它c(diǎn)均屬于W的所有邊為邊集合構(gòu)成的子圖,稱(chēng)為由W導(dǎo)出的子圖,記為G[W].(2)G–W

設(shè)W

V,導(dǎo)出子圖G[V–W]記為G–W,是在G中去掉所有W中的節(jié)點(diǎn),同時(shí)也要去掉與W中節(jié)點(diǎn)關(guān)聯(lián)的所有邊.通常將G–{v}記為G-v.63(3)G[F]設(shè)F

E,則以F為邊集合,以F中邊的所有端點(diǎn)為節(jié)點(diǎn)集合構(gòu)成的子圖,稱(chēng)為由F導(dǎo)出的子圖,記為G[F].(4)G–F

設(shè)F

E,則從G中去掉F中的所有邊得到的生成子圖記為G–F.642.圖的運(yùn)算定義(1)并(2)交(3)差(4)環(huán)和V1∪V2E1∪E2V1∩V2E1∩E2V1∪V2E1⊕E2653.圖同構(gòu)由于圖的拓?fù)湫再|(zhì),有可能兩個(gè)表面上看起來(lái)不同的圖本質(zhì)上是同一個(gè)圖,這就是圖同構(gòu)的問(wèn)題.定義：G1=(V1,E1)和

G2=(V2,E2)，若存在雙射f：V1→V2，

使得G1

中有(a,b)當(dāng)且僅當(dāng)G2中有(f(a),f(b))且重?cái)?shù)相等,則稱(chēng)G1和

G2同構(gòu).直觀理解:G1

G2是指其中一個(gè)圖僅經(jīng)過(guò)下列兩種變換可以變?yōu)榱硪粋€(gè)圖:(a)挪動(dòng)節(jié)點(diǎn)的位置；(b)伸縮邊的長(zhǎng)短.66無(wú)向圖同構(gòu)的例子:66分子式為C4H10的同分異構(gòu)體：分子式為C2H6O的同分異構(gòu)體：應(yīng)用實(shí)例:判斷化合物是否結(jié)構(gòu)相同。

6767兩個(gè)圖同構(gòu)的必要條件：

—節(jié)點(diǎn)個(gè)數(shù)相同

—邊的個(gè)數(shù)相同

—對(duì)應(yīng)節(jié)點(diǎn)的度數(shù)相同

—一個(gè)是完全圖，另一個(gè)也是，等等….破壞這些必要條件中的任何一個(gè)，兩個(gè)圖就不會(huì)同構(gòu)。6868aedcGHbaedcbG和H是否同構(gòu)?696970有向圖:對(duì)于兩個(gè)有向圖同構(gòu)的判斷,特別要注意邊的方向的一致性.作業(yè)

P168

習(xí)題6.31,5,6716.4路與回路1.路定義對(duì)于任意圖G=(V,E),路的起點(diǎn);終點(diǎn);路的長(zhǎng)度;平凡路（一個(gè)節(jié)點(diǎn)長(zhǎng)度為0）.1u3452vu145v4323472需要注意的是,有向圖中的路須按邊的方向走,有向圖中的路可稱(chēng)為有向路.73定義兩種特殊的路:一種是節(jié)點(diǎn)不重復(fù)的路,稱(chēng)為路徑.一種是邊不重復(fù)的路,稱(chēng)為軌跡.v3e3v2e2v2是一條從v3到v2的軌跡,但不是路徑.顯然,路徑是軌跡,但軌跡不一定是路徑.v3e3v2e2v2v1e5v3e3v2742.回路定義起點(diǎn)與終點(diǎn)相同的(長(zhǎng)度1)路稱(chēng)為回路,除起點(diǎn)重復(fù)一次外,別的節(jié)點(diǎn)均不重復(fù)的回路稱(chēng)為圈或環(huán),邊不重復(fù)的回路稱(chēng)為簡(jiǎn)單回路.長(zhǎng)度為0的路不稱(chēng)為回路.顯然,節(jié)點(diǎn)v到v的邊是一個(gè)長(zhǎng)度為1的圈.1u3452v23432u14u7475Theorem在n階圖G=(V,E)中,若存在從節(jié)點(diǎn)v0到vl的一條路,則必存在一條從v0到vl的長(zhǎng)度n-1的路徑.Theorem在n階圖G=(V,E)中,若存在從節(jié)點(diǎn)v0到v0的簡(jiǎn)單回路,則存在一條從v0到v0的長(zhǎng)度n

的圈.定義u到v的距離d(u,v):最短路徑的長(zhǎng)度證明如果該路不是路徑,說(shuō)明含有回路,刪去所有回路(包括吊環(huán))即可得到路徑.

1u3452vd(u,3)=？76有n個(gè)節(jié)點(diǎn)的圈稱(chēng)為n階圈,記為Cn.在n-1階圈Cn-1的內(nèi)部放置一個(gè)節(jié)點(diǎn),并使之與Cn-1的每個(gè)節(jié)點(diǎn)鄰接,這樣得到的圖稱(chēng)為n階輪圖,記為Wn.C3C4C5C6W4W5W7W677Theorem在無(wú)向圖G=(V,E)中,若任意v

V有deg(v)2,則G中必存在圈.證不妨設(shè)G是簡(jiǎn)單圖.在G中選取一條最長(zhǎng)的路徑L:v0v1…vl,由于L是最長(zhǎng)路徑,與v0鄰接的所有節(jié)點(diǎn)必在L上.由于deg(v0)2,除了v1,存在vi(2il)與v0鄰接,則v0v1…viv0是G中的一個(gè)圈.作業(yè)

P170習(xí)題6.41,4(1)(2).786.5圖的連通性定義在任何圖G=(V,E)中,若從節(jié)點(diǎn)u到v存在一條路,則稱(chēng)u可達(dá)v.備注由于節(jié)點(diǎn)v到v總存在一條長(zhǎng)度為0的路,因此任意節(jié)點(diǎn)v可達(dá)v自身.791.無(wú)向圖的連通性定義設(shè)G=(V,E)是無(wú)向圖,對(duì)于G中任意兩個(gè)節(jié)點(diǎn)u和v均可達(dá),則稱(chēng)G是連通圖.Theorem去掉簡(jiǎn)單回路上的邊或度為1的節(jié)點(diǎn),圖的連通性不變.

a

b

c

e

a

c

e

f

W6d是abcdef否cabdegf是80定義設(shè)G=(V,E)是無(wú)向圖,G中極大的連通子圖稱(chēng)為G的連通分支,圖G的連通分支數(shù)記為w(G).備注圖G的連通分支滿(mǎn)足3個(gè)條件:(1)連通分支是G的子圖；(2)該子圖本身是連通圖；(3)在該子圖中再添加原圖的任意邊或節(jié)點(diǎn)都不連通.abdcefgh3個(gè)連通分支.81Theorem設(shè)G=(V,E)是無(wú)向圖,則G是連通圖當(dāng)且僅當(dāng)w(G)=1.G是非連通圖當(dāng)且僅當(dāng)w(G)2.82833.有向圖的連通性有向圖的連通性分下述3種情形分別討論.定義設(shè)G=(V,E)是有向圖,u,vV均相互可達(dá),則稱(chēng)G為強(qiáng)連通圖.定義設(shè)G=(V,E)是有向圖,對(duì)于任意u,v

V,從u可達(dá)v或者從v可達(dá)u,則稱(chēng)G為單向連通圖.定義設(shè)G=(V,E)是有向圖,若不考慮邊的方向是一個(gè)無(wú)向連通圖,則稱(chēng)有向圖G為弱連通圖,簡(jiǎn)稱(chēng)有向圖G連通.84強(qiáng)連通圖單向連通圖弱連通圖.但反過(guò)來(lái)均不成立!特別地，平凡圖是強(qiáng)連通圖。85Theorem設(shè)G=(V,E)是有向圖,則G強(qiáng)連通當(dāng)且僅當(dāng)G中存在一條回路,它通過(guò)所有節(jié)點(diǎn).Theorem設(shè)G=(V,E)是有向圖,則G單向連通當(dāng)且僅當(dāng)G中存在一條路,它通過(guò)所有節(jié)點(diǎn).作業(yè)

P175習(xí)題6.53.866.6圖的矩陣表示將一個(gè)圖畫(huà)出來(lái)是最直觀的表示圖的方式.學(xué)習(xí)圖的矩陣表示的必要性：便于使用計(jì)算機(jī)存儲(chǔ)和處理圖,借助于完善的矩陣?yán)碚?線(xiàn)性代數(shù)知識(shí)之一!)研究圖的有關(guān)性質(zhì)。87

圖的鄰接矩陣鄰接矩陣：表示的是圖中任意兩個(gè)節(jié)點(diǎn)間的鄰接關(guān)系.定義G=(V,E),對(duì)節(jié)點(diǎn)編號(hào)V={v1,v2,…,vn}.

其中aij是vi鄰接到vj的邊數(shù),i,j=1,2,…,n.abcdef

abcdefFromToW6dbacef{v1,v2}行 列0100111010010101010010111001011111