圖中含有控制圈的一個充分條件

摘 要:本文證明了:設是階且圍長的連通圖，是2-連通的。如果對任意邊，，有，則中含有一個控制圈。

關鍵詞:控制圈邊度圍長控制邊

中圖分類號:O157文獻標識碼:A文章編號:1674-098X(2011)05(b)-0254-01

1 引言

設表示圖中所有圈構成的集合。如果而且，則稱是的一個控制圈。

設，端點分別在和中的最短路的長度稱為和的距離，記為。

如果且，，則稱和是鄰近的。若且和鄰近，則稱和分離的。對于，定義的度。對于，設至少有一個端點在中}，記。

設是的確定了一個方向的圈或道路，對于，在上沿著的方向，的前繼點記為，的后繼點記為。對于，，

記。對于圖，用表示圖的圍長，即最短圈的長度。

定義且。

Veldman在文獻[3]中給出了如下結論:

定理1[3] 設是階非樹圖，如果對中任意一對分離的邊，

有，則中含有一個控制圈。

劉春峰在[4]和[5]中得到:

定理2[4]

設是階連通圖，且是2-連通的，如果對任意邊，，有，則G中含有一個控制圈。

定理3[5]

設是階連通圖，且是2-連通的，如果對中任意一對分離的邊，有，則中含有一個控制圈。

本文在適當增加圖的圍長的情況下，改進了原有的一些結果。

2 主要結論和證明

定理:設圖是階且圍長的連通圖，是2-連通的。如果對任意邊，

，有，則中含有一個控制圈。

證明用反證法，假設圖中不含有控制圈。

因為是2-連通的，所以。

因此，我們可選取，使得最大。

設且規定下標次序的方向為正向。

因為中不含控制圈而且是連通圖，所以必存在且與上某點鄰近。

不妨設，設，，，

因為，所以，否則中含有長度比9小的圈。

又由邊的選擇知，。

令，

。

因為映射:是到自身的一一對應，所以()。……