有向圖的單向連通與擬強連通性關系的探究

彭麗曼

摘 要：本文通過對有向圖單向連通性與擬強連通性關系的探究，得出單向連通圖D，如果單向連通圖D中任意頂點ν，有向圖D-ν不是單向連通的，則有向圖D擬強連通的結論，進而證明了單向連通圖D一定是擬強連通的。但是，存在擬強連通的有向圖D不是單向連通的，從而探明有向圖中單向連通性與擬強連通性之間的關系。本文最后討論了幾種可降階單向連通圖，以及可去點的性質。

關鍵詞：有向圖；單向連通；擬強連通

1 引言

本文所述定義及符號大部分出自[1]。

本文所論述的圖都是有向圖。所述道路、圈指的是有向道路、有向圈。用v的入度表示以頂點v為終點的弧的數目；用v的出度表示以頂點v為起點的弧的數目。并且，本文第三部分定義了可降階單向連通圖與可降階單向連通圖的可去點。

定義 如果在有向圖D中，有一條有向道路，則v稱為是從u可達的，或者說，從u可達v。

設D是一個有向圖，r是D中一個頂點，如果由r可到達D的任一頂點，則稱r為D的根。

如果有向圖D的任何兩頂點至少有一個頂點由另一頂點可達，則稱D是單向連通的。

如果有向圖D的每一對頂點u，v都存在一頂點w，使w可達u和v，則稱D是擬強連通的。

定理* 有向圖D有根當且僅當對D的每一對頂點u，v都存在一個頂點w，使w可達u和v。

2 有向圖的單向連通和擬強連通性的關系

定理1 單向連通圖D，如果D中任意頂點ν，D-ν不單向連通，則D擬強連通。

證明：任意有n個頂點的單向連通圖D，取圖D中一點ω1，由于D-ω1不單向連通，則存在圖D-ω1中兩個頂點μ1，ν1，對于μ1，ν1在圖D-ω1中不存在從一個頂點到另一個頂點的有向道路。又由于圖D單向連通，故對于上述μ1，ν1在圖D中存在從一頂點到另一頂點的有向道路，不妨設μ1可達ν1，令P1=<μ1，ν1>，則P1一定過頂點ω1，從而μ1可達ω1，且ω1可達ν1。令ω2=μ1，則ω2可達ω1，且ω2可達ν1。又由于圖D-ω2不單向連通，則存在圖D-ω2中兩個頂點μ2，ν2，對于μ2，ν2在圖D-ω2中不存在從一個頂點到另一個頂點的有向道路。又由于圖D單向連通，故對于上述μ2，ν2在圖D中存在從一頂點到另一頂點的有向道路，不妨設μ2可達ν2，令P2=<μ2，ν2>，則P2一定過頂點ω2，從而μ2可ω2，且ω2可達ν2。令ω3=μ2，則ω3可達ω2，且ω2可達ν2。重復上述過程可窮盡圖D的所有頂點，得：ωnl1可達ωnl2，，…ω1，ν1，從而ωnl1是D的根，由定理*與擬強連通的定義知，有向圖D擬強連通。

定理2 單向連通圖D擬強連通。

證明：對單向連通圖D的頂點個數施加歸納。

（i）當n=2時，圖D單向連通，顯然圖D擬強連通；

（ii）假設當n=k時，結論成立；

（iii）當n=k+1時，若不存在D中頂點r使得D-r單向連通，則由定理1得圖D擬強連通；若存在D中頂點u，使得D-u單向連通，則由歸納假設，D-u擬強連通，由定理*與擬強連通的定義，D-u有根，設其根為v，若存在D-u中一個頂點w使得屬于圖D中的邊，則w可達u，由ν可達w，從而v可達u，故v是圖D的根；否則，任意D-u中的頂點w，不存在屬于D-u的邊，從而u的出度為0，則在D中，v不可達u，由于圖D單向連通，從而u可達v，由此u可達D中任意頂點，故u是D中的根。綜上所述，圖D中有根，由定理*與擬強連通的定義知圖D擬強連通。

定理3 擬強連通的有向圖不一定是單向連通的。

定理是顯然的，此處不給予證明。

3 可降階單向連通圖

定義 若單向連通圖D可以通過去掉圖中某一頂點ν使得圖D-v保持單向連通性，則稱圖D為可降階單向連通圖，稱頂點v為可去點。

在討論可降階單向連通圖之前先給出有向圈與有向圈相連接的三種方式以及給出兩個定理。

（a）有向圈與有向圈有公共邊；

（b）有向圈與有向圈有一個公共點。

（c）有向圈與有向圈既無公共點又無公共邊。

定理4 若有向連通圖D的生成子圖B是單向連通的，則圖D是單向連通的。

證明：任意的有向連通圖D中的頂點p，q，由于圖D的生成子圖B單向連通，從而在圖B中有一條有向道路P連接p，q，由于道路P也是圖D中的道路，從而道路P為圖D中連接點p，q的有向道路，由于p，q的任意性，圖D單向連通。

定理5 若有向連通圖D每一個頂點的出度與入度都大于0，則圖D存在由若干有向圈以（a）方式或（b）方式或（c）方式連接的生成子圖。

證明：若有向連通圖D的所有頂點的出度與入度都大于0，則從圖D的任意頂點出發可得一有向鏈，從而存在有向圈C。若此時圈C為圖D的生成子圖，則定理得證，否則由于圖D是連通的，必有圈C中一個頂點p與其他頂點之一相連，從p出發可得另一有向鏈，從而可得另一有向圈，重復上述過程，可得有向圖D的生成子圖B，圖B為若干有向圈組成，其中任意兩個有向圈由（a）方式或（b）方式或（c）方式連接。

以下討論幾種可降階單向連通圖以及可降階單向連通圖的可去點的性質。

（i）若單向連通圖D中存在某個頂點ν，使得ν出度或者入度為0，則圖D為可降階單向連通圖，且ν為可去點。

證明：在單向連通圖D中存在頂點ν，使得v出度或者入度為0，則D- v任意兩個頂點p，q，由于圖D單向連通，所以有連接p，q的有向道路，且所有連接p，q的有向道路P均不經過頂點ν，否則v的出度與入度都大于0。從而道路P為圖D- v的道路。所以圖D-ν也單向連通，由可降階的單向連通圖定義知圖D-v為可降階的單向連通圖，ν為圖D的可去點。

（ii）若有向圖D由兩個有向圈以（a）或（b）方式連接，則D為可降階單向連通圖。

證明：若有向圖D由兩個有向圈以（a）方式連接，則去掉一個度為3的頂點得到一有向道路，有向道路為單向連通的，故圖D為可降階的單向連通圖；若有向圖由兩個有向圈以（b）方式連接，則去掉任意度為2的頂點，得到的圖均為單向連通圖，從而圖A為可降階單向連通圖。

參考文獻

[1]王朝瑞，圖論，北京理工大學出版社，2001。