第一節(jié)圖的基本概念

1、（Graph Theory and Network Analysis ） 圖與網(wǎng)絡(luò)的基本知識 中國郵路問題 最短路問題 最大流問題問題：一個散步者能否從任一塊陸地出發(fā)，走過七座橋，且每座橋只走過一次，最后回到出發(fā)點？BDACABCD結(jié)論：結(jié)論：不能。不能。每個結(jié)點關(guān)聯(lián)的邊數(shù)每個結(jié)點關(guān)聯(lián)的邊數(shù)要均為偶數(shù)。要均為偶數(shù)。一筆畫問題2.環(huán)球旅行問題：環(huán)球旅行問題：3.中國郵路問題中國郵路問題（解）（解）二二. .圖與網(wǎng)絡(luò)的基本概念圖與網(wǎng)絡(luò)的基本概念 如： 鐵路交通圖 ，球隊比賽圖等等。 (v1)趙趙(v2)錢錢孫孫(v3) 李李(v4)周周(v5)吳吳(v6)陳陳(v7)e2e1e3e4e5(v1)趙

2、趙(v2)錢錢(v3)孫孫(v4)李李(v5)周周(v6)吳吳(v7)陳陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的?？梢妶D論中的圖與幾何圖、工程圖是不一樣的。例如：在一個人群中，對相互認(rèn)識這個關(guān)系我們可以用圖來例如：在一個人群中，對相互認(rèn)識這個關(guān)系我們可以用圖來表示。表示。 圖圖G區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個點以區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個點以及哪些點之間有連線。及哪些點之間有連線。若用若用點點表示研究的對象，用表示研究的對象，用邊邊表示這些對象之間表示這些對象之間的聯(lián)系，則圖的聯(lián)系，則圖G可以定義為點可以定義為點(頂點頂點)和邊的集合，記和邊的

3、集合，記作：作：,EVG 其中其中: V點集點集 E邊集邊集v3e7e4e8e5e6e1e2e3v1v2v4v5 端點端點,關(guān)聯(lián)邊關(guān)聯(lián)邊,相鄰相鄰若有邊若有邊e可表示為可表示為e=vi,vj，稱，稱vi和和vj是邊是邊e的的端點端點，反之稱邊，反之稱邊e為點為點vi或或vj的的關(guān)聯(lián)邊關(guān)聯(lián)邊。若點。若點vi、vj與同一條邊關(guān)與同一條邊關(guān)聯(lián)，稱點聯(lián)，稱點vi和和vj相鄰；若邊相鄰；若邊ei和和ej具具有公共的端點，稱邊有公共的端點，稱邊ei和和ej相鄰相鄰。如圖：V = v1 , v2 , v3 , v4 , v5，E = e1 , e2 , e3 , e4 , e5 , e6 , e7, e8，

4、邊數(shù)：m(G)=|E|=m頂點數(shù)：n(G)=|V|=ne1=v1,v1; e2=v1,v2; 無向邊與無向圖無向邊與無向圖：若圖中任一條邊的端點無序，即：若圖中任一條邊的端點無序，即(v(vii, v, vj j) )與與(v(vj j, v, vii) )是同一條邊，則稱它為無向邊，此時圖稱為是同一條邊，則稱它為無向邊，此時圖稱為無向無向圖。圖。有向圖有向圖：若圖中邊：若圖中邊(v(vii, v, vj j) )的端點是有序的，則稱它是有向的端點是有序的，則稱它是有向邊（或?。叄ɑ蚧。?，v vii與與v vj j分別稱為這條有向邊的始點和終點，分別稱為這條有向邊的始點和終點，相應(yīng)的圖稱為

5、相應(yīng)的圖稱為有向圖有向圖。有向圖無向圖無向圖無向圖,有向圖有向圖邊：不帶箭頭的聯(lián)線，表示對稱關(guān)系。邊：不帶箭頭的聯(lián)線，表示對稱關(guān)系。 ?。簬Ъ^的聯(lián)線，表示不對稱關(guān)系?；。簬Ъ^的聯(lián)線，表示不對稱關(guān)系。 有向圖：由點和弧組成。一般表示為：有向圖：由點和弧組成。一般表示為： D=（V，A） V-點集合點集合 A-弧集合弧集合 點數(shù)點數(shù): p(G) 或或 p(D) ； 邊數(shù)邊數(shù): q(G)；弧數(shù)；弧數(shù):q(D) 環(huán)環(huán), 多重邊多重邊, 簡單圖簡單圖如果邊如果邊e的兩個端點相重，稱該邊為的兩個端點相重，稱該邊為環(huán)環(huán)。如右圖中邊。如右圖中邊e1為環(huán)。如果兩個點為環(huán)。如果兩個點之間多于一條，稱為之間多于

6、一條，稱為多重邊多重邊，如右圖，如右圖中的中的e4和和e5，對無環(huán)、無多重邊的圖，對無環(huán)、無多重邊的圖稱作稱作簡單圖簡單圖。無環(huán)但含多重邊的圖稱。無環(huán)但含多重邊的圖稱為為多重圖多重圖。v3e7e4e8e5e6e1e2e3v1v2v4v5簡單圖多重圖環(huán)多重邊 完全圖完全圖 每一對頂點間都有邊相連的無向簡單圖稱為每一對頂點間都有邊相連的無向簡單圖稱為無向完全圖無向完全圖；有向完全圖有向完全圖是指每一對頂點間有且是指每一對頂點間有且僅有一條有向邊的簡單圖。僅有一條有向邊的簡單圖。 完全圖頂點數(shù)完全圖頂點數(shù)n n與邊數(shù)與邊數(shù)mm間成立如下關(guān)系間成立如下關(guān)系: : m=n(n-1)/2 二部圖（偶圖）二

7、部圖（偶圖）圖圖G=(V,E)的點集的點集V可以分為兩各非空子集可以分為兩各非空子集X，Y，集，集XY=V,XY=,使得同一集合中任意兩個頂點均不使得同一集合中任意兩個頂點均不相鄰，稱這樣的圖為相鄰，稱這樣的圖為二部圖（偶圖）。二部圖（偶圖）。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明顯為二部圖，明顯為二部圖，(b)也是二部圖，但不明顯，改畫為也是二部圖，但不明顯，改畫為(c)時可以清楚看出。時可以清楚看出。 次，奇點，偶點，孤立點次，奇點，偶點，孤立點與某一個點與某一個點vi相關(guān)聯(lián)的邊的數(shù)目稱為相關(guān)聯(lián)的邊的數(shù)目稱為點點vi的的次次（也叫做度），記作（也

8、叫做度），記作d(vi)。右圖中右圖中d(v1),d(v3)=5,d(v5)=1。次。次為奇數(shù)的點稱作為奇數(shù)的點稱作奇點奇點，次為偶數(shù)的，次為偶數(shù)的點稱作點稱作偶點偶點，次為，次為1的點稱為的點稱為懸掛點懸掛點，次為次為0的點稱作的點稱作孤立點孤立點。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次圖的次: 一個圖的次等于各點的次之和。一個圖的次等于各點的次之和。v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3懸掛點孤立點懸掛邊偶點奇點 在有向圖中，以頂點在有向圖中，以頂點v v為始點的邊數(shù)稱為頂點為始點的邊數(shù)稱為頂點v v的的出次出次，記為，記為d d+ +

9、(v)(v)；以；以v v為終點的邊數(shù)稱為為終點的邊數(shù)稱為v v的的入次入次，記為，記為d d- -(v)(v)。頂點。頂點v v的出次與入次的和稱為的出次與入次的和稱為點點v v的次。的次。 圖圖G=(V, E), G=(V, E), 若若E E是是E E的子集，若的子集，若VV是是V V的子集，的子集，且且E E中的邊僅與中的邊僅與VV中的頂點相關(guān)聯(lián)，則稱中的頂點相關(guān)聯(lián)，則稱G = (V, G = (V, E)E)為圖為圖GG的一個子圖，特別地，若的一個子圖，特別地，若V =V, V =V, 則稱則稱GG為為GG的一個的一個生成子圖（支撐子圖）生成子圖（支撐子圖）。 子圖，生成子圖子圖，生

10、成子圖(支撐子圖支撐子圖)圖圖G1=V1、E1和圖和圖G2=V2，E2如果有如果有 稱稱G1是是G2的一個的一個子圖子圖。若有若有 ，則稱，則稱G1是是G2的一的一個個生成子圖生成子圖(支撐子圖支撐子圖)。2121EEVV 和和2121EEVV ，v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G圖） 網(wǎng)絡(luò)（賦權(quán)圖）網(wǎng)絡(luò)（賦權(quán)圖）設(shè)圖設(shè)圖G（V，E），對），對G的每一條邊的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊稱為邊(vi,vj)的的權(quán)權(quán),賦予權(quán)的圖賦予權(quán)的圖G稱為

11、網(wǎng)絡(luò)稱為網(wǎng)絡(luò)(或或賦權(quán)圖）賦權(quán)圖）。權(quán)可以代表距離、費用、通過能力權(quán)可以代表距離、費用、通過能力(容量容量)等等。等等。端點無序的賦權(quán)圖稱為端點無序的賦權(quán)圖稱為無向網(wǎng)絡(luò)無向網(wǎng)絡(luò)，端點有序的賦權(quán)圖稱為，端點有序的賦權(quán)圖稱為有有向網(wǎng)絡(luò)。向網(wǎng)絡(luò)。910201571419256 鏈，圈，連通圖鏈，圈，連通圖 無向圖中一個點、邊交錯的序列，序列中的第一個和最無向圖中一個點、邊交錯的序列，序列中的第一個和最后一個元素都是點，若其中每條邊以序列中位于它之前和后一個元素都是點，若其中每條邊以序列中位于它之前和之后的點為端點，則稱這個點邊序列為圖中連接其第一個之后的點為端點，則稱這個點邊序列為圖中連接其第一個點

12、與最后一個點的稱為點與最后一個點的稱為鏈鏈。 鏈中所含的邊數(shù)稱為鏈中所含的邊數(shù)稱為鏈長鏈長。鏈，但只是簡單鏈而非初等鏈簡單鏈簡單鏈：沒有重復(fù)邊；：沒有重復(fù)邊；初等鏈初等鏈：既無重復(fù)邊也無重：既無重復(fù)邊也無重復(fù)點。對有向圖可類似定義復(fù)點。對有向圖可類似定義鏈，如果各邊方向一致，則鏈，如果各邊方向一致，則稱為稱為道路道路。kkvevev011, L L 鏈，圈，連通圖鏈，圈，連通圖 若在無向圖中，一條鏈的第一個點與最后一個點重合，若在無向圖中，一條鏈的第一個點與最后一個點重合，則稱這條鏈為則稱這條鏈為圈圈。只有重復(fù)點而無重復(fù)邊的圈為簡單圈，既。只有重復(fù)點而無重復(fù)邊的圈為簡單圈，既無重復(fù)點又無重復(fù)邊

13、的圈為無重復(fù)點又無重復(fù)邊的圈為初等圈初等圈。初等圈非簡單的圈有向圖有向圖無向圖無向圖道路道路鏈（或道路）鏈（或道路）回路回路圈（或回路）圈（或回路）道路(邊的方向一致) 連通圖連通圖 一個圖中任意兩點間至少有一條鏈相連，則稱此圖為一個圖中任意兩點間至少有一條鏈相連，則稱此圖為連通圖連通圖。任何一個不連通圖總可以分為若干個任何一個不連通圖總可以分為若干個連通子圖連通子圖，每一個稱為，每一個稱為原圖的一個分圖（原圖的一個分圖（連通分支連通分支）。）。連通圖非連通圖定理定理8.1 任何圖中，頂點次數(shù)之和等于所有邊數(shù)的任何圖中，頂點次數(shù)之和等于所有邊數(shù)的2倍。倍。定理定理8.2 任何圖中，次為奇數(shù)的頂

14、點必為偶數(shù)個。任何圖中，次為奇數(shù)的頂點必為偶數(shù)個。證明：由于每條邊必與兩個頂點關(guān)聯(lián)，在計算點的次時，每條邊證明：由于每條邊必與兩個頂點關(guān)聯(lián)，在計算點的次時，每條邊均被計算了兩次，所以頂點次數(shù)的總和等于邊數(shù)的均被計算了兩次，所以頂點次數(shù)的總和等于邊數(shù)的2倍。倍。證明：設(shè)證明：設(shè)V1和和V2分別為圖分別為圖G中奇點與偶點的集合。由定理中奇點與偶點的集合。由定理1可得：可得：qvdvdvdVvVvVv2)()()(212q 為偶數(shù)，且偶點的次之和為偶數(shù)，且偶點的次之和 也為偶數(shù)，所以也為偶數(shù)，所以 必為必為偶數(shù)，即奇數(shù)點的個數(shù)必為偶數(shù)。偶數(shù)，即奇數(shù)點的個數(shù)必為偶數(shù)。2)(Vvvd1)(Vvvdqvd

15、Vv2)(1. 鄰接矩陣鄰接矩陣對于圖G=（V，E），| V |=n， | E |=m，有nn階方矩陣A=(aij) nn，其中其他,0),(, 1Evvajiijv5v1v2v3v4v64332256437 v v v v v vvvvAvvv 1234561236 6456010111101100010101111010100101101010 例例8.1 下圖所表示的圖可以構(gòu)造鄰接矩陣下圖所表示的圖可以構(gòu)造鄰接矩陣A如下如下對于賦權(quán)圖對于賦權(quán)圖G=(V,E), 其中邊其中邊 有權(quán)有權(quán) , 構(gòu)造矩陣構(gòu)造矩陣B=(bij) n n (權(quán)矩陣）其中：權(quán)矩陣）其中： 其他其他的一個端點的一個端點

16、是邊是邊當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)?shù)膬蓚€端點的兩個端點是邊是邊當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)0ev1ev2jijiijm),(jivvjiw EvvEvvwbjijijiji),(0),(1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0v1v2v3v4v5v6v7v8e1 e2 e3 e4 e5 e6

17、e7 e8 e9 e10 e11 e12 v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例例8.2 下圖所表示的圖可以構(gòu)造關(guān)聯(lián)矩陣下圖所表示的圖可以構(gòu)造關(guān)聯(lián)矩陣M如下如下:M=（mij）=654321654321 030303302004020576305020007204346040vvvvvvvvvvvvB v5v1v2v3v4v64332256437例例8.3 下圖所表示的圖可以構(gòu)造權(quán)矩陣下圖所表示的圖可以構(gòu)造權(quán)矩陣B如下如下: 連通圖連通圖GG中，若存在一條道路，經(jīng)過每邊一次且僅中，若存在一條道路，經(jīng)過每邊一次且僅一次，則稱這條道路為一次，則稱這

18、條道路為歐拉道路歐拉道路。若存在一條回路。若存在一條回路經(jīng)過每邊一次也僅一次，則稱這條回路為經(jīng)過每邊一次也僅一次，則稱這條回路為歐拉回路歐拉回路。具有歐拉回路的圖稱為具有歐拉回路的圖稱為歐拉圖歐拉圖（E E圖）。圖）。定理定理8.3 8.3 無向連通無向連通圖圖GG是歐拉圖，當(dāng)是歐拉圖，當(dāng)且僅當(dāng)且僅當(dāng)GG中無奇點中無奇點現(xiàn)在我們可以來回答本節(jié)現(xiàn)在我們可以來回答本節(jié)一開始提出的哥尼斯堡七一開始提出的哥尼斯堡七橋問題了！橋問題了！推論推論1 1 無向連通圖無向連通圖GG為歐拉圖，當(dāng)且僅為歐拉圖，當(dāng)且僅當(dāng)當(dāng)GG的邊集可以劃分為若干個初等回路。的邊集可以劃分為若干個初等回路。推論推論2 2 無向連通圖

19、無向連通圖GG中有歐拉道路，當(dāng)中有歐拉道路，當(dāng)且僅當(dāng)且僅當(dāng)GG中恰好有兩個奇點。中恰好有兩個奇點。這樣，解決了一筆畫問題：這樣，解決了一筆畫問題：（1）經(jīng)每邊一次且僅一次到另一點停止；）經(jīng)每邊一次且僅一次到另一點停止； （即圖中有無歐拉道路問題）（即圖中有無歐拉道路問題）（2）經(jīng)每邊一次且僅一次又回到原出發(fā)點。）經(jīng)每邊一次且僅一次又回到原出發(fā)點。 （即圖中有無歐拉回路問題）（即圖中有無歐拉回路問題）一個郵遞員，負(fù)責(zé)某一地區(qū)的信件投遞，他每天一個郵遞員，負(fù)責(zé)某一地區(qū)的信件投遞，他每天要走郵局出發(fā)，走遍該地區(qū)所有街道，再返回郵要走郵局出發(fā)，走遍該地區(qū)所有街道，再返回郵局，問應(yīng)如何安排送信的路線可以

20、使所走的總路局，問應(yīng)如何安排送信的路線可以使所走的總路程最短？程最短？用圖論的語言描述就是：給定一個連通圖用圖論的語言描述就是：給定一個連通圖GG，每，每邊有非負(fù)權(quán)邊有非負(fù)權(quán)l(xiāng)(e)，要求一條回路過每邊至少一次，要求一條回路過每邊至少一次，且滿足總權(quán)最小。且滿足總權(quán)最小。(1)(1)若若GG是歐拉圖，則按歐拉回路走，就是滿足要是歐拉圖，則按歐拉回路走，就是滿足要求的經(jīng)過每邊至少一次且總權(quán)最小的走法。求的經(jīng)過每邊至少一次且總權(quán)最小的走法。abcdef(2)(2)若若GG中有奇點，則中有奇點，則GG不是不是歐拉圖，因此要連續(xù)地走過歐拉圖，因此要連續(xù)地走過每邊至少一次，則必然有某每邊至少一次，則必然

21、有某些邊不止一次走過。這相當(dāng)些邊不止一次走過。這相當(dāng)于在于在GG中添加一些重復(fù)的邊，中添加一些重復(fù)的邊，使得到的新圖使得到的新圖GG* *沒有奇點且沒有奇點且滿足總路程最短。滿足總路程最短。abcdefabcdef對增加了重復(fù)邊后得到的新圖對增加了重復(fù)邊后得到的新圖GG* *，很明顯其總權(quán)的大小取決，很明顯其總權(quán)的大小取決于增加的重復(fù)邊權(quán)的大小。因于增加的重復(fù)邊權(quán)的大小。因此中國郵路問題轉(zhuǎn)化為如下問此中國郵路問題轉(zhuǎn)化為如下問題：題：在連通圖在連通圖G=(V, E)G=(V, E)中，求一個中，求一個邊的集合邊的集合E E1 1 E E，將，將E E1 1中所有邊中所有邊都變成重復(fù)邊得到新圖都變

22、成重復(fù)邊得到新圖GG* *，使，使得得GG* *中無奇點，且中無奇點，且 最小最小1)()(1EeelEL上述問題的解決依賴于以下結(jié)果：上述問題的解決依賴于以下結(jié)果：定理定理8.4 8.4 已知圖已知圖GG* *=G+E=G+E1 1無奇點，則無奇點，則最小的充分必要條件為：最小的充分必要條件為：（1 1）每條邊最多重復(fù)一次；）每條邊最多重復(fù)一次；（2 2）對圖）對圖GG中的每個初等圈來說，重復(fù)邊的長度中的每個初等圈來說，重復(fù)邊的長度不超過圈長的一半。不超過圈長的一半。1)()(1EeelEL下面直觀地說明，若定理下面直觀地說明，若定理5 5的條件不成立，則可以的條件不成立，則可以得到總權(quán)比得到總權(quán)比E E1 1的更小的重復(fù)邊集。的更小的重復(fù)邊集。122254122254重復(fù)兩次或以上的重復(fù)兩次或以上的去掉其中兩條去掉其中兩條將原來的重復(fù)邊變成非將原來的重復(fù)邊變成非重復(fù)邊，原來的非重復(fù)重復(fù)邊，原來的非重復(fù)邊變成重復(fù)邊邊變成重復(fù)邊解法第一步解法第一步：確定初始可行方案。若圖中沒有奇點，：確定初始可行方案。若