卢鹏丽, 薛玉龙

(兰州理工大学 计算机与通信学院, 甘肃 兰州 730050)

设H=(V(H ),E(H ))是一个顶点数为n，超边数为m的超图.其中顶点集V(H )={1,2,…,n}，超边集E(H )={e1,e2,…,em}(不包括空集).和图相比较，超图的每条超边上可以有多个顶点.若超图的所有超边都有相同的顶点个数k，则称之为k-均匀超图.显而易见，通常意义上的图就是2-均匀超图.因此，图是一种特殊的超图，超图也可以看成是一般图的推广.因此，超图的一些性质与图的性质相似，但是又有所不同.通常情况下为了叙述简便，一般也将超边简称为边.没有重边的k-均匀超图被称为简单k-均匀超图.在超图中长度为r的途径W用一个顶点和边交替的序列v0e1v1e2…ervr来表示，其中{vi-1,vi}⊆ei，i=1,…,r.若回路中除v0=vr外，没有其他顶点或者边重复，则这个回路被称为圈.若v0=vr，则称途径W为一个回路.若途径W中没有顶点或者边重复，则称这条途径W为超路Pn.若超图中任意两个顶点之间有途径连接，则该超图被称为是连通的.本文中，只考虑简单连通的k-均匀(k≥3)超图.

在超图中，若顶点v∈e，则称顶点v和边e相关联.若存在一条边包含顶点vi和vj，则称顶点vi和vj相邻接.若两条边的交集ei∩ej≠∅，则表示这两条边vi和vj相邻.对于k-均匀超图H，包含顶点v∈V(H )的边的个数定义为顶点v的度，即dv=|ej:v∈ej∈E(H )|.度d=1的顶点称为悬挂点，否则被称为非悬挂点.若边e∈E(H)正好包含k-1个悬挂点，则称e为悬挂边，否则被称为非悬挂边.

定义1[1]设H是一个顶点数为n，边数为m，连通分支数为l的k-均匀超图.则H的圈数为c(H )=m(k-1)-n+l.因此，超图H可以称为c(H )圈超图.

由于本文中只考虑简单连通超……