定向圖弧連通度的下界

王曉麗，張國志

（晉中學(xué)院數(shù)學(xué)學(xué)院，山西晉中030619）

（編輯 郭繼榮）

0 引言

本文討論有限無環(huán)無重弧的有向圖.用V＝V（D）和A＝A（D）分別表示有向圖D的頂點集和弧集，且n用分別表示D的頂點數(shù)（或階）和弧數(shù).如果xy∈A（D ），稱x控制y，并稱x為這條弧的尾，y為這條弧的頭.設(shè)X和Y是V（D）的兩個不相交的頂點子集，用（X，Y）表示尾在X中，頭在Y中的所有弧組成的集合.由x控制的所有頂點組成的集合稱為頂點x的外鄰域，記為N+（x）；由控制x的所有頂點組成的集合稱為x的內(nèi)鄰域，記為分別是x的外度和內(nèi)度.頂點x的度d.用 δ+和 δ-分別表示D的最小外度和最小內(nèi)度，D的最小度 δ＝min.D的度序列定義為頂點度的不增序列

如果D的任意兩個不同的頂點u、ν，在D中都存在（u，ν ）-路，則稱D為強連通的.對于強連通有向圖D，若弧集S?A（D），D-S不是強連通的，則稱S是D的一個弧割．弧數(shù)最少的弧割稱為最小弧割.D的最小弧割中弧的條數(shù)稱為D的弧連通度，記為 λ（D）.由定義顯然 λ（D）≤δ（D）.當(dāng) λ（D）＜δ（D ）時，稱有向圖D是非極大弧連通的.本文未給出的術(shù)語和記號請參見文[1]．

1 主要結(jié)論

定義1 設(shè)D是一個有t個強連通分支的有向圖.令D1，D2，…，Dt是D的t個強連通分支排成的序列.若對于任意的uν∈A（D），u∈A（ Di），ν∈A（ Dj），總有i＜j，則稱上面的序列為D的一個強連通分支無圈序.

定義2 對于有向圖D，去掉D中弧的方向，再去掉產(chǎn)生的重邊得到的簡單圖稱為有向圖的基礎(chǔ)圖，記為UG（D）．

定義3 如果有向圖D的基礎(chǔ)圖不含p+1階的完全子圖，稱D的團(tuán)數(shù)ω（D ）≤p．

定義4 沒有2-圈的有向圖稱為定向圖．

引理1[2]設(shè)（X，Y）為定向圖D中任意一個滿足的弧割，則

定理1 設(shè)D是一個n階強連通定向圖，D的度序列為d1≥d2≥…dn．若λ＜δ，則λ

將X中的頂點按度的不增序進(jìn)行排列，取前2δ+1個頂點組成的集合記為U.將Y中的頂點也按度的不增序排列，取前2δ+1個頂點組成的集合記為W.則有

即

引理2[2]設(shè)（X，Y ）是定向二部圖D＝ （V ′∪ V″，A）中的任意一個滿足的弧割，則，其中X′＝X∩V′，Y′＝Y(jié)∩V′，X″＝X∩V″，Y″＝Y(jié)∩V″．

定理2 設(shè)D＝ （V ′∪ V″，A ）是強連通定向二部圖，D的度序列為d1≥d2≥…dn.若 λ＜δ，則

將X′中的頂點按度的不增序進(jìn)行排列，取前δ+1個頂點組成的集合記為U′．將X″中的頂點按度的不增序排列，取前δ+1個頂點組成的集合記為U″．將Y′中的頂點按度的不增序排列，取前δ+1個頂點組成的集合記為W′．將Y″中的頂點按度的不增序排列，取前δ+1個頂點組成的集合記為W″．則有

引理3[3]若圖G的團(tuán)數(shù) ω（G ）≤p，則2m（G

引理4 設(shè)D是一個團(tuán)數(shù)ω（D）≤p的定向圖，若D[X]是由D的頂點子集X導(dǎo)出的子圖，則2m（ D [ X ]）

引理5[2]設(shè)定向圖D的團(tuán)數(shù)ω（D）≤p，則對D中任意一個滿足的弧割（X，Y），有[X]

定理3 設(shè)D是一個團(tuán)數(shù)ω（）D ≤p的n階強連通定向圖，D的度序列為d1≥d2≥…dn.記a＝max．若 λ＜δ，則

證明 設(shè)S是定向圖D的最小弧割，則[S]＝λ.由弧割的定義知D-S至少包含兩個強連通分支.設(shè)DS的強連通分支無圈序為D1，D2，…，Dk（ k≥2）.令X＝V（ Dk），Y＝V（D） V（ Dk），則（X，Y ）＝S．

因為 λ＜δ，所以由引理1可知[X ]≥2δ++1≥2δ-+1 故≥2δ+1.由引理

將X中的頂點按度的不增序進(jìn)行排列，取前a個頂點組成的集合記為U.將Y中的頂點也按度的不增序排列，取前a個頂點組成的集合記為W．因為由引理4可得

所以

故

［1］Bang-Jensen J? Jrgen，Gutin Gregory.Digraphs:theory,algorithmsand applications［M］.London：Springer-Verlag，2001.

［2］高敬振.有向圖的邊割（X，Y）中和的下界與有向圖的極大性和超級性［J］.系統(tǒng)科學(xué)與數(shù)學(xué)，2011，12（5）：1603~1611.

［3］Turán P.An extremal problemin graph theory［J］.Matematikaiés Fizikai Lapok，1941，48：436~452.