王曉麗，張國志

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

（編輯 郭繼榮）

0 引言

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

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

1 主要結(jié)論

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

定義2 對(duì)于有向圖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中任意一個(gè)滿足的弧割，則

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

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

即

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

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

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

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

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

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

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

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

因?yàn)?λ＜δ，所以由引理1可知[X ]≥2δ++1≥2δ-+1 故≥2δ+1.由引理

將X中的頂點(diǎn)按度的不增序進(jìn)行排列，取前a個(gè)頂點(diǎn)組成的集合記為U.將Y中的頂點(diǎn)也按度的不增序排列，取前a個(gè)頂點(diǎn)組成的集合記為W．因?yàn)橛梢?可得

所以

故

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

［2］高敬振.有向圖的邊割（X，Y）中和的下界與有向圖的極大性和超級(jí)性［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.