朱佳敏，李雙東，2

（1．安徽大學 數(shù)學科學學院，安徽 合肥 230601；2．安徽大學江淮學院，安徽 合肥 230031）

1 預備知識

引理1.1

（1）如果

v

不在

G

的任何圈上，則（2）如果

v

在

G

的一個圈上，則

c

(

G

-

v

)≤

c

(

G

)-1；（3）如果

G

中包含頂點相交的圈，則存在位于相交圈上的頂點

v

，滿足

c

(

G

-

v

)≤

c

(

G

)-2；（4）如果

G

中的圈兩兩不交，則

c

(

G

)等于

G

中圈的個數(shù)。

引理1.2

引理1.3

引理1.4

定義1.5

設

G

是含懸掛點的簡單圖，將

G

中的懸掛點及其鄰點一起刪除的操作稱為 -

δ

變換。設

G

是圈互不相交的簡單圖。對

G

連續(xù)實施

δ

-變換，直到得到的子圖不含懸掛點，稱該子圖是

G

的一個重要子圖。把

G

中的每個圈都收縮成一個新的頂點，所得不含圈的圖記作

T

，所有由圈收縮所得頂點構成的集合記作

W

。將

G

中所有的圈和與這些圈上頂點相關聯(lián)的邊刪除，所得不含圈的圖記作[

T

]。

引理1.6

引理1.7

定理1.8

定理1.9

（1）

G

中任意兩個圈均沒有公共頂點；

（3）

m

(

T

)=

m

([

T

])，即存在

T

的一個最大匹配

M

，使得

M

不覆蓋

W

中的點。

引理1.10

注：由上述引理可知，存在H-秩為2

m

(

G

)- 2

c

(

G

), 2

m

(

G

)- 2

c

(

G

)+ 2, 2

m

(

G

)+

c

(

G

)的單圈混合圖，不存在H-秩為2

m

(

G

)- 2

c

(

G

)+1的單圈混合圖。

2 主要結果

對于圖

G

的懸掛點，如果其鄰點不在

G

的圈上，則稱該懸掛點是類型1的；否則，稱該懸掛點是類型2的。

引理2.1

（1）如果

u

是類型1的，則

（2）如果

u

是類型2的，則

證明

（2）如果懸掛點

u

是類型2的，則由引理1.1（2），

由引理1.6，

（1）式與定理1.9矛盾，命題得證。

滿足()

cG

k

= 的連通簡單圖稱為k-圈圖。設

G

是-

k

圈圖，

G

不含懸掛點的k-圈子圖稱為

G

的基。習慣上，2-圈圖也稱為雙圈圖。不難發(fā)現(xiàn)，雙圈圖有兩種類型的基：

D

(

p

, ?,

q

)和

θ

(

r

,

s

,

t

)，如圖1所示。設

C

和

C

是兩個頂點不相交的圈，路

P

=

v

v

…

v

，

u

∈

V

(

C

)，

v

∈

V

(

C

)。

D

(

p

, ?,

q

)是分別將 和

v

粘合成同一個頂點，

v

和

v

粘合成同一個頂點所得的圖。

θ

(

r

,

s

,

t

)是將三條內部不相交的路

P

，

P

和

P

的起點和終點分別粘合所得的圖。同樣不難發(fā)現(xiàn)，3-圈圖有8種不同類型的基，記作

T

,...,

T

，如圖2所示。

圖1 雙圈圖的基

圖2 3-圈圖的基

例2.2

引理2.3

情形1

子情形1.2 c()≥3

如果在

G

的圈上存在一點

x

，滿足

x

?

V

(

G

[

C

,

C

])，則

G

-

x

包含兩個頂點相交的圈

C

和

C

，不滿足定理1.9的條件（1）。否則，

G

中的每個圈都是

G

[

C

,

C

]的子圖。這意味著

G

[

C

,

C

]包含3-圈圖的基

T

(

j

= 5,…, 8)（見圖2）作為子圖。因而，在

G

的圈上一定存在一個頂點

x

，使得

G

x

- 中有兩個頂點相交的圈，不滿足定理1.9的條件（1），該情形得證。

情形2

情形3

易見，

E

(

T

)≠?；否則

G

是由頂點互不相交的圈和孤立點構成，

m

(

T

=

m

([

T

])=0，矛盾。進一步地，可以斷言：

T

的每個最大匹配至少覆蓋一個懸掛點。否則，

T

的直徑路中一定包含一條

M

-增廣路，與引理1.7矛盾。注意到，

G

不含懸掛點，則

T

的懸掛點在

G

中對應一個懸掛圈，記其中一個懸掛圈為

C

，記

C

上度為3的頂點為

v

。

子情形3.1

子情形3.2

定理2.4

證明

（2）式與（3）式矛盾，因 此 - 2

c

(

G

)+1，命題得證。

圖3

定理2.5

因為

k

,

k

,

k

是非負整數(shù)，令

k

=

k

+

k

+

k

，，

l

= 3

k

+2

k

，則

l

可以取[ 0,3

k

]中除1之外的任意整數(shù)，命題得證。