設G=(V,E)是有向圖,對於任意u,v∈V,從u可達v或者從v可達u,則稱G為單向連通圖(unilateral connected digraph)。
基本介紹
- 中文名:單向連通圖
- 外文名:unilateral connected digraph
- 所屬學科:離散數學
- 相關概念:有向圖、強連通圖等
定義,單向連通圖的判定,
定義
定義1設D是一個有向圖,如果D中任意兩個結點都彼此可達,則稱D為強連通圖。如果D中任意兩點
之間,有
到
可達或
到
可達(稱為單向可達),則稱D為單向連通圖。如果有向圖的底圖是無向連通圖,則稱D為弱連通圖。





注意:強連通圖必是單向連通圖,單向連通圖必是弱連通圖。但反之未必。
例1 圖1(a)是強連通圖,圖1(b)是單向連通圖,圖1(c)是弱連通圖,圖1(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是強連通圖。
必要性:若有向圖G是強連通的,則圖中任何兩個頂點都是相互可達的,故可作出一迴路它經過圖中的所有頂點。否則,必有一迴路不通過某個頂點v,因此v與迴路上的個結點均互不可達,這與G是強連通圖矛盾。
例2 判斷圖3中兩有向圖的連通性。

解:圖3(a)中存在著經過所有點的迴路
,故圖3(a)是強連通圖,圖3(b)沒有a到其他頂點的通路,故圖3(b)是單向連通圖。
