路和回路

• 1.路與通路
• 2.連通與可達
• 3.無向圖的連通性
• 4.有向圖的連通性

1.路與通路

①給定圖G=<V,E>中結點和邊相繼交錯出現的序列Γ=v0e1v1e2v2…ekvk。
若Γ中邊ei的兩端點是vi-1和vi（G是有向圖時要求vi-1與vi分別是ei的始點和終點），i=1,2,…,k，則稱Γ為結點v0到結點vk的路。
v0和vk分別稱為此路的始點和終點。路中邊的數目k稱為路的長度。
當v0=vK時，這條路稱為回路。
②若路中的所有邊互不相同，則稱為跡；
若回路中的所有邊互不相同，則稱此回路為閉跡。
③若路中的所有結點互不相同，則稱此路為通路；
若回路中除v0=vk外的所有結點互不相同，則稱此回路為圈 。

2.連通與可達

在圖G = <V, E>中，vi, vj∈V。
①如果從vi到vj存在路，則稱vi到vj是可達的，否則稱vi到vj不可達。規定：任何結點到自己都是可達的。
②如果vi到vj可達，則稱從vi到vj長度最短的路的長度為從vi到vj的距離，記為d(vi, vj)。如果vi到vj不可達，則通常記為d(vi, vj) = ∞。
對于無向圖，一定有若vi到vj可達，則vj到vi可達；也有d(vi, vj) = d(vj, vi)。
對于有向圖，vi到vj可達，不一定有vj到vi可達；也不一定有d(vi, vj) = d(vj, vi)。

3.無向圖的連通性

①若無向圖G中的任何兩個結點都是可達的，則稱G是連通圖，否則稱G是非連通圖。
通俗的講：圖G的一個連通分支是圖G的一個極大連通子圖，一個圖被分成幾個小塊,每個小塊是連通的,但小塊之間不連通,那么每個小塊稱為連通分支。一個孤立點也是一個連通分支
連通分支數用W(G)表示。
②設無向圖G=<V,E>為連通的，若有結點集V1? V，使得圖G刪除了V1所有結點后，所得的子圖是不連通的，而刪除了V1的任意真子集后，所得的子圖仍然是連通圖。則稱集合V1為圖G 的點割集。若某一結點就構成點割集，則稱該結點為割點。
③設無向圖 G=<V,E>為連通的，若有邊集E1? E，使得圖G 刪除了E1所有邊后，所得的子圖是不連通的，而刪除了E1的任意真子集后，所得的子圖仍然是連通圖。則稱集合E1為圖G的邊割集。若某一邊構成邊割集，則稱該邊為割邊(或橋)。
④若G不是完全圖，定義G的點連通度(或連通度)為：
k(G)=min{|V1| V1是G的點割集} 。
注：一個不連通圖的點連通度等于0，
存在割點的連通圖的點連通度為1。

類似地，定義非平凡圖G的邊連通度為：λ(G)=min{|E1|E1是G的邊割集}

4.有向圖的連通性

設G = <V, E>是一個有向圖，
①略去G中所有有向邊的方向得無向圖G’，如果無向圖G’是連通圖，則稱有向圖G是連通圖或稱為弱連通圖。否則稱G是非連通圖；
②若G中任何一對結點之間至少有一個結點到另一個結點是可達的，則稱G是單向連通圖；
③若G中任何一對結點之間都是相互可達的，則稱G是強連通圖。
若有向圖G是強連通圖，則它必是單向連通圖；若有向圖G是單向連通圖，則它必是（弱）連通圖。但是上述二命題的逆均不成立。
定理：有向圖G是強連通圖的充分必要條件是G中存在一條經過所有結點的回路。
定理：在有向圖G=<V,E>中,它的每個結點位于且僅位于一個強分圖中.
在有向圖G = <V, E>中，設G’是G的子圖，如果
G’是最大強連通的子圖；
那么稱G’為G的強連通分支，或稱為強分圖。
在有向圖G = <V, E>中，設G’是G的子圖，如果
G’是最大單向連通的子圖；
那么稱G’為G的單向連通分支,或稱為單向分圖。
在有向圖G = <V, E>中，設G’是G的子圖，如果
G’是最大弱連通的子圖；
那么稱G’為G的弱連通分支，或稱為弱分圖。

總結

以上是生活随笔為你收集整理的路和回路的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。