運籌學(xué)-Ch5-圖與網(wǎng)絡(luò)規(guī)劃

第五章圖與網(wǎng)絡(luò)規(guī)劃1ppt課件CH5

圖與網(wǎng)絡(luò)規(guī)劃圖的基本知識最小權(quán)支撐樹問題最大流問題最短有向路問題學(xué)習(xí)目的§5.1

圖的基本知識4ppt課件一.

圖Def.

一個圖G是指由一集合V(G)和V(G)中某些元素的無序?qū)Φ募螮(G)所構(gòu)成的二元組(V(G),E(G)).V(G)稱為G的頂點集,其中的元素稱為G的頂點(node).E(G)稱為G的邊集,其中的元素稱為G的邊(edge).簡計V=V(G),E=E(G).如果V和E均為有限集合,則稱G為有限圖,否則稱為無限圖.若邊集是空集,則稱該圖為空圖,記為;否則稱其為非空圖.只有一個頂點的圖稱為平凡圖.圖中頂點的個數(shù)叫做圖的階.連接同一對頂點的邊的條數(shù)叫做邊的重數(shù)(multiplicity),若圖G中存在重數(shù)大于1的邊,則稱G為一多重圖(multigraph).對于圖G,設(shè)V=,E=.若,則稱頂點與是相鄰的(adjacent),并稱,為邊e的端點,也稱e與,相關(guān)聯(lián)(incident).如果,且和有公共的端點,則稱與是相鄰的(鄰接).若V中的某頂點和E中任何邊均不關(guān)聯(lián),則稱該頂點為孤立點.兩個端點重合的邊稱為環(huán)(loop).沒有環(huán)及沒有重數(shù)大于1的邊的圖稱為簡單圖(simplegraph).設(shè)有兩個圖,,它們的頂點集間有一一對應(yīng)的關(guān)系,且使得邊之間有如下的關(guān)系:設(shè),,,如果,則,而且的重數(shù)與的重數(shù)相同,這種對應(yīng)關(guān)系叫作同構(gòu)(isomorphism).同構(gòu)關(guān)系是圖之間的一個等價關(guān)系,故通常將同構(gòu)的圖看作是相同的.每一對不同的頂點之間均有一條邊相連的簡單圖稱為完全圖(completegraph).Th.1

:

n階完全圖有條邊.

圖的每條邊有一個端點在中,另一個端點在中.如果圖的頂點能分成二個集合與,使得同一集合中的任何兩個頂點都不相鄰,則稱此圖為二部(分)圖(bipartitegraph).可寫成.分劃稱為圖的一個二分劃(bipartition).一個完全二分圖,是一個具有二分劃的簡單二分圖,其中的每個頂點與的每個頂點都相連.設(shè)圖G=(V,E),集合.令,則圖稱為G的補圖(complement).圖H稱為G的子圖(subgraph),記作,若,,且H中的邊的重數(shù)不超過G中對應(yīng)邊的重數(shù).設(shè),且下列三個條件中至少有一個成立:(1)(2)(3)H中至少有一個邊的重數(shù)小于G中對應(yīng)邊的重數(shù),則說H是G的真子圖(propersubgraph).設(shè)圖G=(V,E),一個滿足,的真子圖,叫做G的生成或支撐子圖(spanningsubgraph).4531245312G的支撐子圖設(shè)

是圖G=(V,E)的頂點集合V的一個非空子集,以作為頂點集,以兩端點均在中的邊的全體為邊集的子圖,稱為由導(dǎo)出的G的子圖,記為,并稱是G的點導(dǎo)出子圖.若,以中邊的所有端點作為點集的子圖稱為由導(dǎo)出的子圖,記為,并稱是G的邊導(dǎo)出子圖.45312G43124312:以和的點集的交為點集,邊集的交為邊集.:以和的點集的并為點集,邊集的并為邊集;若和沒有公共邊,則稱它們的邊是不重的.設(shè)和是G的子圖,若和沒有公共頂點,則稱它們是不相交的;3154263154264263154兩個不相交的子圖兩個邊不重的子圖Th.2:

設(shè)G是沒有孤立點的圖,其邊數(shù)為,若包括圖G本身和空集在內(nèi),則G的所有不同子圖的個數(shù)為.設(shè),G中與頂點v關(guān)聯(lián)的邊的個數(shù)(與v關(guān)聯(lián)的每個環(huán)算作兩條邊)稱為v(在G中)的度(degree),

記作,或簡記為d(v).如果d(v)是奇數(shù),則稱頂點v是奇的或奇頂點(奇點);如果d(v)是偶數(shù),則稱頂點v是偶的或偶頂點(偶點).顯然,若v為孤立點,則d(v)=0,且有:Th.3:

圖G中所有頂點的度的和等于邊數(shù)的2倍,且任意一個圖一定有偶數(shù)個奇頂點.q—邊數(shù)圖G=(V,E)中的一個頂點序列稱為是一條途徑(walk)W,若對i=1,‥‥,k,有

.

稱為W的起點,稱為W的終點,稱為W的內(nèi)部頂點(中間點)

.途徑W的長度定義為它所含的邊的數(shù)目,即為k.也可以用其相應(yīng)邊的序列來表示途徑W,這里.315426315264路(12342356)若在W中的頂點互不相同,則稱W為一路徑(初等鏈,初級路)(path).315426由到的一條路,若路中的邊不重復(fù),則稱為簡單路.簡單圖中的任一條路必為簡單路,記為.若,則稱途徑W是閉的.稱閉途徑W為一個回路或圈(cycle),

如果且構(gòu)成一路經(jīng).31542631526簡單路(125346)初級路(12356)長為偶數(shù)的圈稱為偶圈,長為奇數(shù)的圈稱為奇圈.Th.4

:

一個圖是一條路經(jīng)當(dāng)且僅當(dāng)它中有兩個頂點的度為

1,而其余頂點的度均為2.Th.5

:

存在圖G的頂點的一個唯一劃分,使得這些子集滿足:頂點i和j位于同一子集中當(dāng)且僅當(dāng)G含有一條i-j路徑.Th.6

:

當(dāng)且僅當(dāng)一個圖無奇圈時,它才是二分圖.設(shè)u,v為圖G中的兩個頂點,若在G中存在一條u-v路徑,則常稱頂點u和v是連通的.如果圖G中每對不同的頂點u,v間都有一條路經(jīng),則稱G為連通圖(connectedgraph),否則稱為非連通圖.頂點之間的連通性是一個等價關(guān)系.一個圖G,如果能把它畫在平面上,且除端點外任意兩條邊均不相交,則稱G可嵌入平面.若圖G可以嵌入平面,則稱G為可平面圖(planargraph).可平面圖在平面上的一個嵌入稱為一個平面圖(planegraph).設(shè)為Th5中之劃分中的一個子集,則稱子圖為G的一個連通分支或簡稱為分支(component),這里表示兩個端點均在中的邊的集合.顯然,當(dāng)且僅當(dāng)G只有一個分支時,G是連通圖.若圖G是不連通的,則其補圖連通.二.有向圖

有向圖D是指由一非空有限集合V(D)和V(D)中某些元素的有序?qū)Φ募螦(D)所構(gòu)成的二元組(V(D),A(D)),V(D)稱為D的頂點集,其中的元素稱為D的頂點.A(D)稱為D的弧(arc)集,其中的元素稱為D的弧,在不至混淆時,記V=V(D),A=A(D).起點與終點重合的弧稱為環(huán).若兩條弧有相同的起點和相同的終點,則稱這兩條弧為重弧.既沒有環(huán)也沒有重弧的有向圖稱為簡單有向圖.若u,vV,則弧a=(u,v)A是頂點u和v的有序?qū)?常稱u為弧a的起點(尾),v為a的終點(頭).

a稱為u的出弧,也稱為v的入弧.對于有向圖D的任一頂點v,以v為起點的弧的數(shù)目叫做v的出度(outdegree),記為;以v為終點的弧的數(shù)目叫做v的入度(indegree),記為.顯然,.u

va對一個有向圖D,可以在其頂點集合上作一個圖G,使得對應(yīng)于D的各條弧,G有一條相同端點的邊,這個無向圖G稱為D的基礎(chǔ)圖(underlyinggraph).一般說來,對應(yīng)于一個基礎(chǔ)圖可以有多個有向圖.Th.7

:

設(shè)D=(V,A)是一有向圖，則.這里

表示集合A中的元素數(shù)目

.頂點序列稱為有向圖D=(V,A)中的一條

有向途經(jīng)(directedwalk),若對有.若該有向途經(jīng)中的頂點互不相同,則稱其為一條有向路徑;而如果,且唯一重復(fù)的頂點是,則稱其為一有向回路或有向圈.Th.8

:

設(shè)P是有向圖D的一個子圖,若1）.2）對任意的

有.

則P是一條有向i-j路徑.這里V(P)表示圖P的頂點集.Th.9

:

設(shè)C是有向圖D的一個子圖，若1）對任意的

,有.2）對任意的.

則C是一條有向回路.給定有向圖D=(V,A),對D中的每條弧a賦予一個實數(shù)ω(a),稱為弧a的權(quán).ω是A上的一實值函數(shù),稱為D的權(quán)函數(shù).賦權(quán)的有向圖D稱為網(wǎng)絡(luò)或賦權(quán)有向圖,記為D=(V,A,

ω

).賦以權(quán)ω的圖G稱為無向網(wǎng)絡(luò)或賦權(quán)圖,記為G=(V,E,

ω

).對于網(wǎng)絡(luò)D=(V,A,

ω

),若是D的一個子圖,則稱為D的子網(wǎng)絡(luò),并定義為子網(wǎng)絡(luò)的權(quán).若對有向圖D的每一對頂點,均有一條有向路徑連接它們,則稱D是強連通的(stronglyconnected).若D是強連通的,則它亦是連通的.割邊:一條邊稱為G的割邊,如果從G中刪去它,則使圖的連通分支數(shù)嚴(yán)格增加.該條邊不包含在G的任何簡單回路中.132456G=(V,E),S,T

V,S

T=,{S,T}表示一個端點在S中,而另一個端點在T中的邊集合.邊割:指G的邊集E的形如的一個子集,其中S是V的非空真子集,,且若從G中刪去這些邊,則G的連通分支數(shù)嚴(yán)格增加.割集:G的極小邊割.每條割邊均為一個割集任何邊割都是不相交割集的并21435214352143521435{{2,1},{2,4},{2,3}}割集{{2,3},{2,4},{1,4},{1,5}}割集{{2,3},{4,3},{4,5}{1,5}}不是割集,但為邊割{{2,3},{2,4},{1,4}}既非割集,亦非邊割三.

圖的表示直觀：圖1對于規(guī)模較大的圖,則用一個矩陣來記錄.有下列兩種方式:頂點—邊關(guān)聯(lián)矩陣設(shè)G=(V,E)是一個非空無環(huán)圖,定義例如,圖1中所示的圖G的關(guān)聯(lián)矩陣為則所得到的階矩陣M(G)＝稱為圖G的關(guān)聯(lián)矩陣.圖的關(guān)聯(lián)矩陣有下列明顯的性質(zhì):1.每一列恰好有兩個非零元素1.2.每一行的元素之和等于對應(yīng)頂點的度.3.將一個關(guān)聯(lián)矩陣中的兩行或兩列互換,相當(dāng)于在同一個圖中將兩個對應(yīng)的頂點或邊的標(biāo)號互換.5.n階圖G是連通的當(dāng)且僅當(dāng)G的關(guān)聯(lián)矩陣是n-1.4.若G有個連通分支,則通過適當(dāng)?shù)呐帕?/p>

G的頂點和邊所對應(yīng)的行和列,G的關(guān)聯(lián)矩陣可以寫成塊對角形式,其中是的關(guān)聯(lián)矩陣.鄰接矩陣?yán)?圖1中所示圖的鄰接矩陣為:設(shè)圖G=(V,E),令

等于G中頂點與之間的邊數(shù),則階方陣A(G)=()稱作G的鄰接矩陣.顯然,1)

A是一對稱矩陣.2)當(dāng)圖G中不存在重數(shù)大于1的邊時,A的元素只取0和1兩個值.對于有向圖,亦可用類似于圖的方法來表示.例如,圖2給出了一個具有五個頂點、九條弧的有向圖D=(V,A).圖2同樣,有向圖也可用關(guān)聯(lián)矩陣或鄰接矩陣來表示.設(shè)D=(V,A)是一非空無環(huán)有向圖,定義易知,圖2中有向圖的關(guān)聯(lián)矩陣為則階矩陣M(D)＝稱為圖D的頂點—弧關(guān)聯(lián)矩陣.有向圖的關(guān)聯(lián)矩陣與圖的關(guān)聯(lián)矩陣有著類似的性質(zhì):1.

M(D)的每一列恰好有兩個非零元素,一個1和一個-1.2.

M(D)的每一行中1的個數(shù)等于對應(yīng)頂點的入度,而-1的個數(shù)等于對應(yīng)頂點的出度.3.將M(D)的兩行或兩列互換,相當(dāng)于在D中將兩個對應(yīng)的頂點或邊的標(biāo)號互換.4.若是D的所有連通分支,,則M(D)可以寫成塊對角形式,其中為的關(guān)聯(lián)矩陣,.§5.2

樹32ppt課件Def.

不含圈的圖稱為無圈圖,連通的無圈圖稱為樹.稱連通分支都是樹的非連通圖為森林.

如果T是G的一個支撐子圖,且T是樹,則稱T為G的支撐樹,也稱為生成樹.Th.

:

樹的性質(zhì):1)

樹的頂點數(shù)比其邊數(shù)多1;2)樹是無環(huán)圖且樹的任意兩個頂點之間有唯一的一條路經(jīng);3)在樹中去掉任一條邊,即變成非連通圖;4)在樹中任兩個不相鄰頂點之間加上一條邊,則構(gòu)成一個恰有一個圈的圖;5)在樹中至少存在兩個度數(shù)為1的頂點.Proof:

2)

圖G是樹

任意兩個頂點之間恰有一條鏈(路徑)必要性:G連通任兩個頂點之間至少有一條鏈若某兩個頂點之間有兩條鏈G中含有圈與樹的定義矛盾∴任兩個頂點之間恰有一條鏈充分性:設(shè)圖G中任兩個頂點之間恰有一條鏈G連通若G中含有圈,則這個圈上任兩個頂點之間有兩條鏈與假設(shè)矛盾∴G不含圈,于是G是樹.5)

設(shè)圖G=(V,E)是一個樹,

p(G)≥2,則G中至少有兩個懸掛點.令