APP下载

关于混合图H-秩的一个注记

2022-01-18朱佳敏李双东

安徽建筑大学学报 2021年6期
关键词:安徽大学顶点情形

朱佳敏,李双东,2

(1.安徽大学 数学科学学院,安徽 合肥 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

中圈的个数。

引理1.2

引理1.3

引理1.4

定义1.5

G

是含悬挂点的简单图,将

G

中的悬挂点及其邻点一起删除的操作称为 -

δ

变换。设

G

是圈互不相交的简单图。对

G

连续实施

δ

-变换,直到得到的子图不含悬挂点,称该子图是

G

的一个重要子图。把

G

中的每个圈都收缩成一个新的顶点,所得不含圈的图记作

T

,所有由圈收缩所得顶点构成的集合记作

W

。将

G

中所有的圈和与这些圈上顶点相关联的边删除,所得不含圈的图记作[

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-圈图也称为双圈图。不难发现,双圈图有两种类型的基:

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

的起点和终点分别粘合所得的图。同样不难发现,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

是非负整数,令

k

=

k

+

k

+

k

,,

l

= 3

k

+2

k

,则

l

可以取[ 0,3

k

]中除1之外的任意整数,命题得证。

猜你喜欢

安徽大学顶点情形
牺牲
探究一道课本习题的一般情形
秦晓玥作品
谢春作品
陈成亮作品
郭诗奇作品
从特殊走向一般
“图形的认识”复习专题
删繁就简三秋树
爱,就是不说牺不牺牲