第一節(jié)圖的基本概念_第1頁
第一節(jié)圖的基本概念_第2頁
第一節(jié)圖的基本概念_第3頁
第一節(jié)圖的基本概念_第4頁
第一節(jié)圖的基本概念_第5頁
已閱讀5頁,還剩36頁未讀 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)

文檔簡介

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

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

一、

問題提出

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

如:

鐵路交通圖,球隊比賽圖等等。

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

點:表示研究對象.

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

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

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

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

有向圖:由點和弧組成。一般表示為:

D=(V,A)

V--點集合A--弧集合

點數(shù):p(G)或p(D);

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

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

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

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

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

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

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

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

子圖,生成子圖(支撐子圖)圖G1={V1、E1}和圖G2={V2,E2}如果有稱G1是G2的一個子圖。若有,則稱G1是G2的一個生成子圖(支撐子圖)。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)可以代表距離、費用、通過能力(容量)等等。端點無序的賦權(quán)圖稱為無向網(wǎng)絡(luò),端點有序的賦權(quán)圖稱為有向網(wǎng)絡(luò)。①②③④⑤⑥910201571419256

鏈,圈,連通圖

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

鏈,圈,連通圖

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

連通圖

一個圖中任意兩點間至少有一條鏈相連,則稱此圖為連通圖。任何一個不連通圖總可以分為若干個連通子圖,每一個稱為原圖的一個分圖(連通分支)。連通圖非連通圖三、圖的基本性質(zhì)及矩陣表示:定理8.1任何圖中,頂點次數(shù)之和等于所有邊數(shù)的2倍。定理8.2任何圖中,次為奇數(shù)的頂點必為偶數(shù)個。證明:由于每條邊必與兩個頂點關(guān)聯(lián),在計算點的次時,每條邊均被計算了兩次,所以頂點次數(shù)的總和等于邊數(shù)的2倍。證明:設(shè)V1和V2分別為圖G中奇點與偶點的集合。由定理1可得:2q為偶數(shù),且偶點的次之和也為偶數(shù),所以必為偶數(shù),即奇數(shù)點的個數(shù)必為偶數(shù)。圖的矩陣表示:如何在計算機中存儲一個圖呢?現(xiàn)在已有很多存儲的方法,但最基本的方法就是采用矩陣來表示一個圖,圖的矩陣表示也根據(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中無奇點現(xiàn)在我們可以來回答本節(jié)一開始提出的哥尼斯堡七橋問題了!推論1無向連通圖G為歐拉圖,當(dāng)且僅當(dāng)G的邊集可以劃分為若干個初等回路。推論2無向連通圖G中有歐拉道路,當(dāng)且僅當(dāng)G中恰好有兩個奇點。這樣,解決了一筆畫問題:(1)經(jīng)每邊一次且僅一次到另一點停止;

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

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論