图中顶点子集的边连通度与最优分级边连通图的构造问题

• 作者: 吴海银 张静 李乔
• 来源期刊: 华中师范大学学报(自然科学版)
• 学科: 数学
• 关键词: 图 边连通度 顶点子集的边连通度 最优分级边连通图的构造
• 年，卷（期）: 2002,（1）
• 页码范围: 20-24
• 页数: 5页
• 分类号: O157.5
• 字数: 5843字
• 语种: 中文
• DOI: 10.3321/j.issn:1000-1190.2002.01.005

摘要

G=(V,E)是无向连通图,无环允许有重边.S是V的至少包含两个顶点的子集,S的边连通度λG(S)被定义为使S中的顶点不属于同一连通分支所需去掉的最少边数.给定集合V和V的一个划分V= V1∪ V2∪…∪ Vr(|r|≥1,|V1|≥2)以及正整数序列k1>k2>…>kr≥2.记Si= V1∪ V2∪…∪ Vi,1≤i≤r.构造一个连通图G=(V,E)满足: λG(Si) ≥ki (1≤i≤r)且边数|E|最小.这种图G称为与所给划分和正整数序列相对应的最优分级边连通图.在给出顶点子集的边连通度概念的基础上,本文提出并讨论了有关最优分级边连通图的构造问题.