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

第八章圖論與網(wǎng)絡(luò)分析

（GraphTheoryandNetworkAnalysis）圖與網(wǎng)絡(luò)的基本知識中國郵路問題最短路問題最大流問題本章主要內(nèi)容：§8.1圖與網(wǎng)絡(luò)分析

一、

問題提出

1.哥尼斯堡七橋問題問題：一個(gè)散步者能否從任一塊陸地出發(fā)，走過七座橋，且每座橋只走過一次，最后回到出發(fā)點(diǎn)？BDACABCD????結(jié)論：不能。每個(gè)結(jié)點(diǎn)關(guān)聯(lián)的邊數(shù)要均為偶數(shù)。一筆畫問題2.環(huán)球旅行問題：3.中國郵路問題（解）二.圖與網(wǎng)絡(luò)的基本概念

如：

鐵路交通圖，球隊(duì)比賽圖等等。

圖論中圖是由點(diǎn)和邊構(gòu)成，反映對象之間的關(guān)系。

點(diǎn):表示研究對象.

連線（邊）：表示兩個(gè)對象之間的某種特定關(guān)系。

一般情況下圖中點(diǎn)的相對位置如何、點(diǎn)與點(diǎn)之間聯(lián)線的長短曲直，對于反映對象之間的關(guān)系并不是重要的。(v1)趙(v2)錢孫(v3)李(v4)周(v5)吳(v6)陳(v7)e2e1e3e4e5(v1)趙(v2)錢(v3)孫(v4)李(v5)周(v6)吳(v7)陳e2e1e3e4e5可見圖論中的圖與幾何圖、工程圖是不一樣的。例如：在一個(gè)人群中，對相互認(rèn)識這個(gè)關(guān)系我們可以用圖來表示?！鶊DG區(qū)別于幾何學(xué)中的圖。這里只關(guān)心圖中有多少個(gè)點(diǎn)以及哪些點(diǎn)之間有連線。 若用點(diǎn)表示研究的對象，用邊表示這些對象之間的聯(lián)系，則圖G可以定義為點(diǎn)(頂點(diǎn))和邊的集合，記作：其中:V——點(diǎn)集E——邊集圖中的點(diǎn)用v表示，邊用e表示。對每條邊可用它所連接的點(diǎn)表示，

記作：e=[v1,v2]··v1v2ev3e7e4e8e5e6e1e2e3v1v2v4v5

端點(diǎn),關(guān)聯(lián)邊,相鄰若有邊e可表示為e=[vi,vj]，稱vi和vj是邊e的端點(diǎn)，反之稱邊e為點(diǎn)vi或vj的關(guān)聯(lián)邊。若點(diǎn)vi、vj與同一條邊關(guān)聯(lián)，稱點(diǎn)vi和vj相鄰；若邊ei和ej具有公共的端點(diǎn)，稱邊ei和ej相鄰。如圖：V={v1,v2,v3,v4,v5}，E={e1,e2,e3,e4,e5,e6,e7,e8}，邊數(shù)：m(G)=|E|=m頂點(diǎn)數(shù)：n(G)=|V|=ne1=[v1,v1];e2=[v1,v2];無向邊與無向圖：若圖中任一條邊的端點(diǎn)無序，即(vi,vj)與(vj,vi)是同一條邊，則稱它為無向邊，此時(shí)圖稱為無向圖。有向圖：若圖中邊(vi,vj)的端點(diǎn)是有序的，則稱它是有向邊（或?。?，vi與vj分別稱為這條有向邊的始點(diǎn)和終點(diǎn)，相應(yīng)的圖稱為有向圖。有向圖無向圖無向圖,有向圖邊：不帶箭頭的聯(lián)線，表示對稱關(guān)系?；。簬Ъ^的聯(lián)線，表示不對稱關(guān)系。

有向圖：由點(diǎn)和弧組成。一般表示為：

D=（V，A）

V--點(diǎn)集合A--弧集合

點(diǎn)數(shù):p(G)或p(D)；

邊數(shù):q(G)；弧數(shù):q(D)

環(huán),多重邊,簡單圖如果邊e的兩個(gè)端點(diǎn)相重，稱該邊為環(huán)。如右圖中邊e1為環(huán)。如果兩個(gè)點(diǎn)之間多于一條，稱為多重邊，如右圖中的e4和e5，對無環(huán)、無多重邊的圖稱作簡單圖。無環(huán)但含多重邊的圖稱為多重圖。v3e7e4e8e5e6e1e2e3v1v2v4v5簡單圖多重圖環(huán)多重邊

完全圖每一對頂點(diǎn)間都有邊相連的無向簡單圖稱為無向完全圖；有向完全圖是指每一對頂點(diǎn)間有且僅有一條有向邊的簡單圖。完全圖頂點(diǎn)數(shù)n與邊數(shù)m間成立如下關(guān)系:m=n(n-1)/2

二部圖（偶圖）圖G=(V,E)的點(diǎn)集V可以分為兩各非空子集X，Y，集X∪Y=V,X∩Y=?,使得同一集合中任意兩個(gè)頂點(diǎn)均不相鄰，稱這樣的圖為二部圖（偶圖）。v1v3v5v2v4v6v1v2v3v4v1v4v2v3(a)(b)(c)(a)明顯為二部圖，(b)也是二部圖，但不明顯，改畫為(c)時(shí)可以清楚看出。

次，奇點(diǎn)，偶點(diǎn)，孤立點(diǎn)與某一個(gè)點(diǎn)vi相關(guān)聯(lián)的邊的數(shù)目稱為點(diǎn)vi的次（也叫做度），記作d(vi)。右圖中d(v1)＝４,d(v3)=5,d(v5)=1。次為奇數(shù)的點(diǎn)稱作奇點(diǎn)，次為偶數(shù)的點(diǎn)稱作偶點(diǎn)，次為1的點(diǎn)稱為懸掛點(diǎn)，次為0的點(diǎn)稱作孤立點(diǎn)。v3e7e4e8e5e6e1e2e3v1v2v4v5圖的次:

一個(gè)圖的次等于各點(diǎn)的次之和。v2v1v5v3v4e2e1e3e4e5e6d(v1)=4d(v2)=3懸掛點(diǎn)孤立點(diǎn)懸掛邊偶點(diǎn)奇點(diǎn)

在有向圖中，以頂點(diǎn)v為始點(diǎn)的邊數(shù)稱為頂點(diǎn)v的出次，記為d+(v)；以v為終點(diǎn)的邊數(shù)稱為v的入次，記為d-(v)。頂點(diǎn)v的出次與入次的和稱為點(diǎn)v的次。

圖G=(V,E),若E'是E的子集，若V'是V的子集，且E'中的邊僅與V'中的頂點(diǎn)相關(guān)聯(lián)，則稱G'=(V',E')為圖G的一個(gè)子圖，特別地，若V'=V,則稱G'為G的一個(gè)生成子圖（支撐子圖）。

子圖，生成子圖(支撐子圖)圖G1={V1、E1}和圖G2={V2，E2}如果有稱G1是G2的一個(gè)子圖。若有，則稱G1是G2的一個(gè)生成子圖(支撐子圖)。v3e7e4e8e5e6e1e2e3v1v2v4v5v3e4e8e5e6v2v4v5v3e7e4e8e6e2e3v1v2v4v5(a)(b)（G圖）

網(wǎng)絡(luò)（賦權(quán)圖）設(shè)圖G＝（V，E），對G的每一條邊(vi,vj)相應(yīng)賦予數(shù)量指標(biāo)wij，wij稱為邊(vi,vj)的權(quán),賦予權(quán)的圖G稱為網(wǎng)絡(luò)(或賦權(quán)圖）。權(quán)可以代表距離、費(fèi)用、通過能力(容量)等等。端點(diǎn)無序的賦權(quán)圖稱為無向網(wǎng)絡(luò)，端點(diǎn)有序的賦權(quán)圖稱為有向網(wǎng)絡(luò)。①②③④⑤⑥910201571419256

鏈，圈，連通圖

無向圖中一個(gè)點(diǎn)、邊交錯(cuò)的序列，序列中的第一個(gè)和最后一個(gè)元素都是點(diǎn)，若其中每條邊以序列中位于它之前和之后的點(diǎn)為端點(diǎn)，則稱這個(gè)點(diǎn)邊序列為圖中連接其第一個(gè)點(diǎn)與最后一個(gè)點(diǎn)的稱為鏈。鏈中所含的邊數(shù)稱為鏈長。鏈，但只是簡單鏈而非初等鏈簡單鏈：沒有重復(fù)邊；初等鏈：既無重復(fù)邊也無重復(fù)點(diǎn)。對有向圖可類似定義鏈，如果各邊方向一致，則稱為道路。

鏈，圈，連通圖

若在無向圖中，一條鏈的第一個(gè)點(diǎn)與最后一個(gè)點(diǎn)重合，則稱這條鏈為圈。只有重復(fù)點(diǎn)而無重復(fù)邊的圈為簡單圈，既無重復(fù)點(diǎn)又無重復(fù)邊的圈為初等圈。初等圈非簡單的圈有向圖無向圖道路鏈（或道路）回路圈（或回路）道路(邊的方向一致)

連通圖

一個(gè)圖中任意兩點(diǎn)間至少有一條鏈相連，則稱此圖為連通圖。任何一個(gè)不連通圖總可以分為若干個(gè)連通子圖，每一個(gè)稱為原圖的一個(gè)分圖（連通分支）。連通圖非連通圖三、圖的基本性質(zhì)及矩陣表示：定理8.1任何圖中，頂點(diǎn)次數(shù)之和等于所有邊數(shù)的2倍。定理8.2任何圖中，次為奇數(shù)的頂點(diǎn)必為偶數(shù)個(gè)。證明：由于每條邊必與兩個(gè)頂點(diǎn)關(guān)聯(lián)，在計(jì)算點(diǎn)的次時(shí)，每條邊均被計(jì)算了兩次，所以頂點(diǎn)次數(shù)的總和等于邊數(shù)的2倍。證明：設(shè)V1和V2分別為圖G中奇點(diǎn)與偶點(diǎn)的集合。由定理1可得：2q為偶數(shù)，且偶點(diǎn)的次之和也為偶數(shù)，所以必為偶數(shù)，即奇數(shù)點(diǎn)的個(gè)數(shù)必為偶數(shù)。圖的矩陣表示：如何在計(jì)算機(jī)中存儲一個(gè)圖呢？現(xiàn)在已有很多存儲的方法，但最基本的方法就是采用矩陣來表示一個(gè)圖，圖的矩陣表示也根據(jù)所關(guān)心的問題不同而有：鄰接矩陣、關(guān)聯(lián)矩陣、權(quán)矩陣等。1.鄰接矩陣 對于圖G=（V，E），|V|=n，|E|=m，有nn階方矩陣A=(aij)nn，其中v5v1v2v3v4v64332256437例8.1下圖所表示的圖可以構(gòu)造鄰接矩陣A如下對于賦權(quán)圖G=(V,E),其中邊有權(quán),構(gòu)造矩陣B=(bij)nn(權(quán)矩陣）其中：2.關(guān)聯(lián)矩陣對于圖G=(V,E),|V|=n,|E|=m,有mn階矩陣M=(mij)mn，其中:3.權(quán)矩陣101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000v1v2v3v4v5v6v7v8e1e2e3e4e5e6e7e8e9e10e11e12v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4例8.2下圖所表示的圖可以構(gòu)造關(guān)聯(lián)矩陣M如下:M=（mij）=v5v1v2v3v4v64332256437例8.3下圖所表示的圖可以構(gòu)造權(quán)矩陣B如下:四、歐拉回路、歐拉圖

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

（即圖中有無歐拉道路問題）（2）經(jīng)每邊一次且僅一次又回到原出發(fā)點(diǎn)。

（即圖中有無歐拉回路問題）五、中國郵路問題一個(gè)郵遞員，負(fù)責(zé)某一地區(qū)的信件投遞，他每天要走郵局出發(fā)，走遍該地區(qū)所有街道，再返回郵局，問應(yīng)如何安排送信的路線可以使所走的總路程最短？用圖論的語言描述就是：給定一個(gè)連通圖G，每邊有非負(fù)權(quán)l(xiāng)(e)，要求一條回路過每邊至少一次，且滿足總權(quán)最小。中國郵路問題解法(1)若G是歐拉圖，則按歐拉回路走，就是滿足要求的經(jīng)過每邊至少一次且總權(quán)最小的走法。abcdef(2)若G中有奇點(diǎn)，則G不是歐拉圖，因此要連續(xù)地走過每邊至少一次，則必然有某些邊不止一次走過。這相當(dāng)于在G中添加一些重復(fù)的邊，使得到的新圖G*沒有奇點(diǎn)且滿足總路程最短。abcdefabcdef對增加了重復(fù)邊后得到的新圖G*，很明顯其總權(quán)的大小取決于增加的重復(fù)邊權(quán)的大小。因此中國郵路問題轉(zhuǎn)化為如下問題：在連通圖G=(V,E)中，求一個(gè)邊的集合E1E，將E1中所有邊都變成重復(fù)邊得到新圖G*，使得G*中無奇點(diǎn)，且最小上述問題的解決依賴于以下結(jié)果：定理8.4已知圖G*=G+E1無奇點(diǎn)，則最小的充分必要條件為：（1）每條邊最多重復(fù)一次；（2）對圖G中的每個(gè)初等圈來說，重復(fù)邊的長度不超過圈長的一半。下面直觀地說明，若定理5的條件不成立，則可以得到總權(quán)比E1的更小的重復(fù)邊集。122254122254重復(fù)兩次或以上的去掉其中兩條將原來