第五章圖與網絡規劃1ppt課件CH5

圖與網絡規劃圖的基本知識最小權支撐樹問題最大流問題最短有向路問題學習目的§5.1

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

圖Def.

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

:

n階完全圖有條邊.

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

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

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

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

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

.

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

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

如果且構成一路經.31542631526簡單路(125346)初級路(12356)長為偶數的圈稱為偶圈,長為奇數的圈稱為奇圈.Th.4

:

一個圖是一條路經當且僅當它中有兩個頂點的度為

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

:

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

:

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

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

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

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

:

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

表示集合A中的元素數目

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

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

:

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

有.

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

:

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

,有.2）對任意的.

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

ω

).賦以權ω的圖G稱為無向網絡或賦權圖,記為G=(V,E,

ω

).對于網絡D=(V,A,

ω

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

V,S

T=,{S,T}表示一個端點在S中,而另一個端點在T中的邊集合.邊割:指G的邊集E的形如的一個子集,其中S是V的非空真子集,,且若從G中刪去這些邊,則G的連通分支數嚴格增加.割集: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對于規模較大的圖,則用一個矩陣來記錄.有下列兩種方式:頂點—邊關聯矩陣設G=(V,E)是一個非空無環圖,定義例如,圖1中所示的圖G的關聯矩陣為則所得到的階矩陣M(G)＝稱為圖G的關聯矩陣.圖的關聯矩陣有下列明顯的性質:1.每一列恰好有兩個非零元素1.2.每一行的元素之和等于對應頂點的度.3.將一個關聯矩陣中的兩行或兩列互換,相當于在同一個圖中將兩個對應的頂點或邊的標號互換.5.n階圖G是連通的當且僅當G的關聯矩陣是n-1.4.若G有個連通分支,則通過適當的排列

G的頂點和邊所對應的行和列,G的關聯矩陣可以寫成塊對角形式,其中是的關聯矩陣.鄰接矩陣例如,圖1中所示圖的鄰接矩陣為:設圖G=(V,E),令

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

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

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

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

樹32ppt課件Def.

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

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

:

樹的性質:1)

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

2)

圖G是樹

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

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

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