版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認(rèn)領(lǐng)
文檔簡介
[有向圖]
設(shè)V是一個非空有限集,A是V上的二元關(guān)系。二元組G=(V,A)稱為(有向)圖,V中元素稱為頂點,A中元素稱為?。ㄓ邢蜻叄?。關(guān)系A(chǔ)的關(guān)系圖就是圖G的圖解。[自環(huán)]
A中的自反性圖解為環(huán)形,稱為自環(huán)。[多重邊]
在表達實際問題的圖解中可能出現(xiàn)重復(fù)的關(guān)系定義,稱為多重邊。2.1圖的概念[簡單圖]不出現(xiàn)自環(huán)或多重邊圖解形狀的圖稱為簡單圖。未加特別聲明時,只討論簡單圖。[完全圖]任何兩個頂點之間都有弧相連的圖稱為完全圖。頂點集為V的完全圖GV=(V,VV)。[零圖]
A=或|A|=0時,稱G為零圖。[平凡圖]
|V|=1時,稱G為平凡圖。[圖的階]
|V|稱為圖的階。2.1圖的概念[子圖]
G=(V,A)是G=(V,A)的一個子圖當(dāng)且僅當(dāng):⑴V
V⑵A
是V
上的二元關(guān)系⑶A
A上述定義中,若對u,vV,<u,v>A必有<u,v>A,則稱G是G的一個極大子圖。G是G的子圖;若G
是G的子圖,則G
的任何子圖也是G的子圖;平凡圖是任何圖的子圖2.1圖的概念[生成子圖]
G=(V,A)是G=(V,A)的一個子圖且V=V,則稱G
是G的一個生成子圖或支撐子圖。[導(dǎo)出子圖]
G=(V,A),SV且S,則G中以S為頂點集的極大子圖稱為G中由S導(dǎo)出的子圖。
[補圖]
設(shè)圖G=(V,A),則~G=(V,VVA)稱為G=(V,A)的補圖。
2.1圖的概念[無向圖]
圖G=(V,A),當(dāng)A為對稱關(guān)系時,在圖解上用線段替換成對出現(xiàn)的弧,在集合上用E={(u,v)|u
V,vV,<u,v>A,
<v,u>
A}
替換A,得到無向圖的形式,記為G=(V,E)。無向圖的各種概念完全類似于有向圖的相關(guān)定義。n階無向完全圖記作Kn,其邊數(shù)=n(n1)/2。圖解中既有無向邊,又有有向邊的圖,稱為混合圖?;旌蠄D可以化為有向圖求解。2.1圖的概念[定義]
對G=(V,A),vi
V,分別定義其正關(guān)聯(lián)集、負(fù)關(guān)聯(lián)集、正鄰接集、負(fù)鄰接集如下:
Inc+(vi)={ak|(vj)(vjV
ak=<vi,vj>A)}
●以為vi起點的所有邊構(gòu)成的集合
Inc(vi)={ak|(vj)(vjV
ak=<vj,vi>A)}
●以為vi終點的所有邊構(gòu)成的集合
Adj+(vi)={vj|
vjV(ak)(ak=<vi,
vj>A)} Adj(vi)={vj|
vjV(ak)(ak=<vj,vi>A)}
●與vi相鄰的頂點構(gòu)成的集合2.2點和邊的關(guān)聯(lián)關(guān)系[關(guān)聯(lián)集與鄰接集]
對無向圖G=(V,E),viV,分別定義其關(guān)聯(lián)集、鄰接集如下:
Inc(vi)={ek
|(vj)(vjV
ek=(vi,vj)E)}
Adj(vi)={vj|
vjV(ek)(ek=(vi,
vj)E)}[正負(fù)度]
對G=(V,A),vi
V,分別定義其正度、負(fù)度、度如下:Deg+(vi)=|Inc+(vi)|Deg(vi)=|Inc(vi)|Deg(vi)=Deg+(vi)+Deg(vi)2.2點和邊的關(guān)聯(lián)關(guān)系[無向圖的度]
對G=(V,E),vi
V,定義其度如下:
Deg(vi)=|Inc(vi)|
對簡單圖顯然有:
Deg(vi)<|V|。[定理2-1]
對G=(V,E),有:
對G=(V,A)有同樣的結(jié)論;[推論1]
圖中度為奇數(shù)的頂點必為偶數(shù)個。2.2點和邊的關(guān)聯(lián)關(guān)系[定義]
對無向圖G=(V,E),若其任一頂點的度都為r,則稱G為一個r度正則圖。[例]
n階完全圖是n1度正則圖。[推論2]
3度正則圖中有偶數(shù)個頂點。2.2點和邊的關(guān)聯(lián)關(guān)系圖解法具有不唯一性。例:一一對應(yīng)的兩個關(guān)系,具有相同的代數(shù)性質(zhì),在一定意義上可視為同一。2.3同構(gòu)[同構(gòu)]
圖G=(V,A)和G=(V,A),若存在一一對應(yīng)映射g:VV,使得對
v1,v2
V,v1,v2
A當(dāng)且僅當(dāng)
g(v1),g(v2)
A,則稱G和G同構(gòu)。記為:GG[例]尋求判定圖同構(gòu)的一般方法是圖論的重要課題之一。2.3同構(gòu)[自補圖]
圖G=(V,A),~G是G的補圖。若G~G,則稱圖G是自補的(或自補圖)。[例]2.3同構(gòu)[有向道路]
有向圖G=(V,A)中,一條有向道路指的是一個點與弧的有限非空交替序列
=
v0
a1
v1
a2
v2
……
akvk
(k1)
其中viV(i=0..k),ajA(j=1..k)
且aj=<vj1,vj>(j=0..k)
v0
和vk分別稱為的起點和終點,k稱為的長度。在簡單圖中,也可記作=(v0v1v2……
vp
)或
v0
v1
v2
……
vp
2.4道路與回路[跡]若對任意的ij有ai
aj
,稱之為簡單有向道路/跡。[回路]若v0=vn
,稱之為封閉的。簡單封閉有向道路(閉跡)稱為有向回路。[路]若對任意的ij有vi
vj
,稱之為有向路(路徑)/初級道路/基本道路。[圈]若對任意的ij有vi
vj
而例外地v0=vn,稱之為初級回路/圈。兩個頂點之間若有道路存在則必有路存在。無向圖具有完全類似的定義。
2.4道路與回路[定理2-2]
無向圖G=(V,E),u,v
V且uv。若u,v
之間存在兩條不同的路,則G中存在一條回路。[證明]
(構(gòu)造法)[定理2-3]
無向圖G=(V,E)中每個頂點的度均為偶數(shù),且至少有一個頂點不是孤立點,則
G中存在一條回路。
[證明]
(反證法)設(shè)v不是孤立點,從v出發(fā)的最長簡單路徑經(jīng)過的頂點是v0(=v)v1…vn-1vn,則必存在0i<n使得vn=vi,否則與vn的度是偶數(shù)矛盾。2.4道路與回路[定理2-4]
G=(V,A),|V|=n,則
G中任何初級道路的長度均不大于n1;G中任何初級回路的長度均不大于n
。
[證明](反證法)設(shè)圖中有一條道路,其長度>n1,則其中至少有n+1個頂點標(biāo)號,而圖中只有n個頂點,故其中至少有兩個相同的頂點,即該道路不會是初級道路。2.4道路與回路[可達性]
G=(V,A)中,若從
vi
到vj
存在一條路,則稱從
vi
到vj
是可達的,或稱
vi
可達vj
。對無向圖G=(V,E),結(jié)點間的可達性是對稱的。若規(guī)定任何結(jié)點到其自身可達,則①可達性構(gòu)成V上的一個等價關(guān)系,其對V的每一個劃分塊可以構(gòu)成G的一個導(dǎo)出子圖。②兩個結(jié)點可達當(dāng)且僅當(dāng)它們屬于同一個導(dǎo)出子圖。③上述導(dǎo)出子圖的個數(shù)(或劃分塊個數(shù))稱為G的連通分支數(shù),記為W(G)。2.4道路與回路[連通性]
G=(V,E)中,任意兩點之間可達時,稱G為連通的(連通圖)。
G=(V,A)中,任意兩點之間相互可達時,稱G為強連通的;若去掉弧的方向后得到的無向圖G=(V,s(A))是連通的,則稱原來的G是弱連通的。G中的一個極大連通子圖稱為G的一個連通分支。2.4道路與回路[定理2-5]
G=(V,E),n=|V|,若對任意u,v
V且
uv,都有:Deg(u)+Deg(v)n1,則G連通。[證明](反證法)設(shè)G可分為不連通的兩部分G1=(V1,E1)和G2=(V2,E2),選取
uV1,vV2
則Deg(u)<|V1|,Deg(v)<|V2|,故Deg(u)+Deg(v)<|V1|+|V2|=n,與Deg(u)+Deg(v)n1矛盾。注意:未加特別聲明時,我們討論的都是簡單圖。2.4道路與回路[Euler回路]
若連通圖G=(V,E)中存在一條簡單回路(無重復(fù)邊)經(jīng)過G的所有邊,則稱該回路為G中的一條Euler回路。存在Euler回路的圖稱為Euler圖。[定理2-6-1]
設(shè)有連通圖G=(V,E),則下述命題等價:
(1)G是一個Euler圖;
(2)G的每一個頂點的度是偶數(shù);[證明](見戴一奇教材p16定理2.3.1)2.5Euler回路注意定理中對圖的連通性的假定;Euler回路經(jīng)過圖的所有邊一次且僅僅一次。定理對非簡單圖也成立;定理的證明過程給出了為一個Euler圖構(gòu)造Euler回路的構(gòu)造算法。[定理2-7]
設(shè)連通圖G=(V,E)中恰有2k個頂點度為奇數(shù),k1。則G的邊可劃分成k條簡單道路。[證明](構(gòu)造法,見戴一奇教材p17例2.3.3)2.5Euler回路[有向圖的Euler回路]
若有向連通圖G=(V,A)中存在一條簡單有向回路經(jīng)過G的所有弧,則稱該回路為G中的一條Euler回路,稱該圖為Euler有向圖。[定理2-6-2]
設(shè)連通有向圖G=(V,A),則下述命題等價:
(1)G是一個Euler有向圖;
(2)G的每一個頂點的入度等于出度;[證明](略)2.5Euler回路[旋轉(zhuǎn)鼓的設(shè)計]
見戴一奇教材p17例2.3.42.5Euler回路[Hamilton路]
若連通圖G=(V,E)中存在一條初級道路(無重復(fù)頂點)經(jīng)過G中每個頂點一次,則稱該道路為G中的一條Hamilton路。存在Hamilton回路的圖稱為Hamilton圖。Hamilton路經(jīng)過圖的所有頂點一次且僅僅一次。引入記號:G=(V,E),SV。從G中去除S中的頂點及其關(guān)聯(lián)邊得到的G的子圖記為GS。2.6Hamilton道路[定理2-8]
若G=(V,E)是一個Hamilton圖,SV且S,則G的子圖GS的連通分支數(shù)
W(GS)|S|[證明]
記G中H-回路為C,C中包含了G中所有頂點。考察CS:每從C中去除屬于S的一個頂點,連通分支數(shù)至多增加1(第一次以及當(dāng)該頂點處于邊緣時操作不會增加連通分支數(shù)),故
W(CS)|S|
而G可視為向C中添加邊構(gòu)成,故W(GS)W(CS)
所以W(GS)|S|2.6Hamilton道路定理給出了Hamilton圖的必要條件,可用于對Hamilton圖的否定性判定,但對Hamilton圖的肯定性判定無效。2.6Hamilton道路[例]
圖G12345786令S={2,6},則W(GS)=3。而|S|=2,即W(GS)>|S|故圖G不可能是Hamilton圖。134578圖G-S2.6Hamilton道路[例]
Petersen圖。|V|=10,對任何SV,都有W(GS)S,但Petersen圖不是Hamilton圖。2.6Hamilton道路[定理2-9]
簡單圖G=(V,E),n=|V|,若對任一對不相鄰頂點u,vV,uv,有Deg(u)+Deg(v)n1,則G中存在一條Hamilton路。[證明]見戴一奇教材p18定理2.4.1[推論]
上述有Deg(u)+Deg(v)n時,G為Hamilton圖。[證明]見戴一奇教材p19推論2.4.12.6Hamilton道路定理及其推論給出了Hamilton圖成立的充分條件,可用于對Hamilton圖的肯定性判定。Hamilton圖成立的充要條件尚未得到解決,是圖論求解的課題之一。2.6Hamilton道路[鄰接矩陣]
對有向圖G=(V,R),n=|V|,構(gòu)造矩陣A=(aij)nn,其中[定理2-10]
設(shè)A1、A2分別為G1、G2的鄰接矩陣,則G1G2當(dāng)且僅當(dāng)存在置換矩陣P,使得A1=PA2PT。
aij
=1<vi,vj>R0其他稱A為圖G的鄰接矩陣。2.7圖的鄰接矩陣[定理2-11]
設(shè)Ann是G的鄰接矩陣,則連接vi與vj(ij)的長度為l的路徑的條數(shù)等于Al的第i行第j列的元素的數(shù)值。[證明](數(shù)學(xué)歸納法:對l歸納)2.7圖的鄰接矩陣[道路矩陣]
對有向圖G=(V,R),n=|V|,構(gòu)造矩陣P=(pij)nn,其中
pij
=1若vi
到vj可達0其他稱P為圖G的道路矩陣(或可達矩陣)。2.8道路矩陣及Warshall算法[算法]
求給定圖G的道路矩陣P
設(shè)A為G的鄰接矩陣,B=A+A2+A3+…+An1,由[定理2-11],bij表示由vi至vj
,長度為1或2或…或n1的路徑數(shù)目,即為由vi至vj的全部路徑總和。令
pij
=1若bij
>00其他可求得G的道路矩陣P。
算法復(fù)雜度O(n4)2.8道路矩陣及Warshall算法[定義]
二值元素的邏輯運算:
00=0,01=10=1,11=100=0,01=10=0,11=1[定義]
二值矩陣的邏輯運算。設(shè)有矩陣A=(aij),B=(bij),矩陣元素值域為{0,1},定義運算:2.8道路矩陣及Warshall算法[定義]
A(k)=A(k1)
A(k2),A(1)=A注意A(k)與Ak
的區(qū)別[定理2-12]
設(shè)Ann是圖G的鄰接矩陣,若從vi
到vj存在長度為l的路,則[A(l)]ij
=1,否則[A(l)]ij
=0。[證明]對l作歸納;或直接引用[定理2-11]。2.8道路矩陣及Warshall算法[Warshall算法]
設(shè)Ann是圖G的鄰接矩陣,求G的道路矩陣P。PAi1j1pjk
pjk(pji
pik),k=1...njj+1,若jn,轉(zhuǎn)4i
i+1,若
in,轉(zhuǎn)3Stop計算復(fù)雜度O(n3)2.8道路矩陣及Warshall算法[例]
圖G的鄰接矩陣A如右,使用Warshall算法求G的道路矩陣P。[解]PA2.8道路矩陣及Warshall算法(1)i=1j
=1,2,3,4
增量方向i
=1矩陣元素處理次序:p11,
p12,
p13,
p14,
p21,
p22,……
p31,……
p41,……,p44,2.8道路矩陣及Warshall算法如:p11
=p11(p1i
pi1)=p11(p11
p11)=0p12
=p12(p2i
pi2)=p12(p21
p12)=1p13
=p13(p3i
pi3)=p13(p31
p13)=0…………結(jié)果為2.8道路矩陣及Warshall算法考察第
i次循環(huán)。第i
列的0元對應(yīng)的行,pji=0,故pjk
=pjk(pji
pik)=pjk(0
pik)=pjk;第i
列的1元對應(yīng)的行,pji=1,故pjk
=pjk(pji
pik)=pjk(1
pik)=pjkpik
,即將該行與第i行做“或”運算。(2)i=22.8道路矩陣及Warshall算法[表上作業(yè)法]第i
次循環(huán)時,將第i
行分別“疊加”到第i列的非0元對應(yīng)的那些行,“疊加”運算是一對行向量各個對應(yīng)元素的邏輯“或”運算。(i=1..n)如上例:
i=22.8道路矩陣及Warshall算法非0元
i[例]
i=12.8道路矩陣及Warshall算法
i
i=22.8道路矩陣及Warshall算法
i
i=42.8道路矩陣及Warshall算法
i
i=52.8道路矩陣及Warshall算法
i[進一步的討論]定義運算“PQ”:(PQ)ij=pijqij,P、Q為同階矩陣。2.8道路矩陣及Warshall算法則:(PPT)ij=pij
pji
對行列重新編號得:2.8道路矩陣及Warshall算法可見,{v1},{v3}以及{v2,v4,v5}的導(dǎo)出子圖分別構(gòu)成強連通分量。v1v2v3v4v52.8道路矩陣及Warshall算法[旅行商問題]已知n個城市,任兩個城市之間都有無向路相通,求一條經(jīng)過所有城市一次且僅僅一次,并且總路
溫馨提示
- 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)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2025年度公司團建旅游專項服務(wù)合同書2篇
- 2025年度廢品處理與環(huán)保公益活動合作合同3篇
- 二零二五年度金融科技融資合同模板大全3篇
- 二零二五年度農(nóng)村堰塘周邊土地整治與開發(fā)合同2篇
- 公對公匯款合同模板(2025年度)-保險理賠支付3篇
- 2025年度挖機租賃與項目成本控制合同3篇
- 2024年中國流體設(shè)備市場調(diào)查研究報告
- 2024年中國機械式攪拌機市場調(diào)查研究報告
- 2025年度森林防火視頻監(jiān)控與無人機巡檢服務(wù)協(xié)議3篇
- 2024年后簧前吊耳襯套項目可行性研究報告
- 2024年全國《國防和兵役》理論知識競賽試題庫與答案
- 企業(yè)知識產(chǎn)權(quán)保護策略及實施方法研究報告
- 2024年07月11026經(jīng)濟學(xué)(本)期末試題答案
- 2024年中小企業(yè)股權(quán)融資合同3篇
- 2024年01月11289中國當(dāng)代文學(xué)專題期末試題答案
- 2024年秋季生物教研組工作計劃
- 2024年云南高中學(xué)業(yè)水平合格考歷史試卷真題(含答案詳解)
- 《古蘭》中文譯文版
- 工程停止點檢查管理(共17頁)
- 爬架安裝檢查驗收記錄表1529
- 2021年全國煙草工作會議上的報告
評論
0/150
提交評論