有向圖的單向連通與擬強(qiáng)連通性關(guān)系的探究

彭麗曼

摘 要：本文通過(guò)對(duì)有向圖單向連通性與擬強(qiáng)連通性關(guān)系的探究，得出單向連通圖D，如果單向連通圖D中任意頂點(diǎn)ν，有向圖D-ν不是單向連通的，則有向圖D擬強(qiáng)連通的結(jié)論，進(jìn)而證明了單向連通圖D一定是擬強(qiáng)連通的。但是，存在擬強(qiáng)連通的有向圖D不是單向連通的，從而探明有向圖中單向連通性與擬強(qiáng)連通性之間的關(guān)系。本文最后討論了幾種可降階單向連通圖，以及可去點(diǎn)的性質(zhì)。

關(guān)鍵詞：有向圖；單向連通；擬強(qiáng)連通

1 引言

本文所述定義及符號(hào)大部分出自[1]。

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

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

設(shè)D是一個(gè)有向圖，r是D中一個(gè)頂點(diǎn)，如果由r可到達(dá)D的任一頂點(diǎn)，則稱r為D的根。

如果有向圖D的任何兩頂點(diǎn)至少有一個(gè)頂點(diǎn)由另一頂點(diǎn)可達(dá)，則稱D是單向連通的。

如果有向圖D的每一對(duì)頂點(diǎn)u，v都存在一頂點(diǎn)w，使w可達(dá)u和v，則稱D是擬強(qiáng)連通的。

定理* 有向圖D有根當(dāng)且僅當(dāng)對(duì)D的每一對(duì)頂點(diǎn)u，v都存在一個(gè)頂點(diǎn)w，使w可達(dá)u和v。

2 有向圖的單向連通和擬強(qiáng)連通性的關(guān)系

定理1 單向連通圖D，如果D中任意頂點(diǎn)ν，D-ν不單向連通，則D擬強(qiáng)連通。

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

定理2 單向連通圖D擬強(qiáng)連通。

證明：對(duì)單向連通圖D的頂點(diǎn)個(gè)數(shù)施加歸納。

（i）當(dāng)n=2時(shí)，圖D單向連通，顯然圖D擬強(qiáng)連通；

（ii）假設(shè)當(dāng)n=k時(shí)，結(jié)論成立；

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

定理3 擬強(qiáng)連通的有向圖不一定是單向連通的。

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

3 可降階單向連通圖

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

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

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

（b）有向圈與有向圈有一個(gè)公共點(diǎn)。

（c）有向圈與有向圈既無(wú)公共點(diǎn)又無(wú)公共邊。

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

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

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

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

以下討論幾種可降階單向連通圖以及可降階單向連通圖的可去點(diǎn)的性質(zhì)。

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

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

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

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

參考文獻(xiàn)

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