论文部分内容阅读
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称为与所给划分和正整数序列相对应的最优分级边连通图.在给出顶点子集的