超图的限制边连通度与最优限制边连通

作者：童林肯; 单而芳^*

来源：运筹学学报, 2020, 24(04): 145-152.

DOI：10.15960/j.cnki.issn.1007-6093.2020.04.013

• 超图
• 限制边连通度
• 最优限制边连通性

设H=(V,F)是顶点集为V,超边集为E的连通超图。对H的边子集S,若H\S不连通而且不含孤立点,则称S是H的一个限制边割。把H中最小限制边割的基数称为H的限制边连通度,记为λ’(H)。对边e,其边度是指在H中与e相交的超边的数目,H中最小边度记为ξ(H)。如果λ’(H)=ξ(H),那么称超图H是最优限制边连通的,简记为λ’-最优。研究超图H的限制边连通度和λ’-最优,推广了图上关于限制边连通度和λ’-最优的一些结论。

• 单位
  上海大学