-
單向連通圖
鎖定
設G=(V,E)是有向圖,對於任意u,v∈V,從u可達v或者從v可達u,則稱G為單向連通圖(unilateral connected digraph)。
[1]
- 中文名
- 單向連通圖
- 外文名
- unilateral connected digraph
- 所屬學科
- 離散數學
- 相關概念
- 有向圖、強連通圖等
單向連通圖定義
定義1設D是一個有向圖,如果D中任意兩個結點都彼此可達,則稱D為強連通圖。如果D中任意兩點
之間,有
到
可達或
到
可達(稱為單向可達),則稱D為單向連通圖。如果有向圖的底圖是無向連通圖,則稱D為弱連通圖。
注意:強連通圖必是單向連通圖,單向連通圖必是弱連通圖。但反之未必。
定義2設
是有向圖,G的極大的單向連通子圖稱為G的單向連通分支(unilateral connected component)。
由定義知,如圖2所示有兩個單向連通分支,分別是G[1,2,3,4,5],G[5,6]。
注意:有向圖G的節點
可以位於G的不同的單向連通分支中。
單向連通圖單向連通圖的判定
關於單向連通圖的判定,有如下定理。
證法一: (
)若能證明命題“對於任意
均存在一個W中節點在G中到W中其餘節點都有路”,則定理結論成立,因為先取W=V,存在
到其餘V中節點有路,再取
,存在
到其餘
節點有路.這樣一直下去,就可以得到一條從
到
,
到
,
到
的一條路,其中
(但這條路不一定是軌跡)。
假定上述命題不成立,令
是使其不成立的元素個數最少的,這時k≥3,根據假設
使命題成立,於是必存在
中一個節點,不妨設為
到其餘節點
有路,而假設
到
是沒有路的,否則與W的假設矛盾。另一方面,由於
到其餘節點
有路,所以
到
沒有路,否則
到
都有路,由於
到
沒有路,而
到
也沒有路,與已知G是單向連通圖矛盾。
(
)顯然。
證法二:充分性:若G中有一回路,它至少經過每個頂點一次。則圖中任何兩個頂點都是相互可達的,可見圖G是強連通圖。
例2 判斷圖3中兩有向圖的連通性。
解:圖3(a)中存在着經過所有點的迴路
,故圖3(a)是強連通圖,圖3(b)沒有a到其他頂點的通路,故圖3(b)是單向連通圖。