连通图G的一个割集是G的一个支路集合，则（）。
A: 一个割集包含了G的全部支路。
B: 一个割集包含了G的部分支路。
C: 一个割集是将G分为两个分离部分的最少支路集合。
D: 一个割集将G分为三个部分。
A: 一个割集包含了G的全部支路。
B: 一个割集包含了G的部分支路。
C: 一个割集是将G分为两个分离部分的最少支路集合。
D: 一个割集将G分为三个部分。
举一反三
- 若连通无向图G是(n,m)图,T是G的生成树,则基本割集有个,基本圈有个。
- 若图 G1是连通图 G 的一个割集 ，则图 G1必须满足的条件是（） A: 图 G1是图 G 的一部分支路的集合 B: 移走图 G 1中的所有支路，图 G 会分成两个或多个孤立的部分 C: 移走图 G 1中的所有支路，图 G 会分成两个孤立的部分 D: 如果少移一条图 G 1的支路，图 G 依然联通
- 设T 是n 阶连通图G 的一棵生成树，G 对应于T 的基本割集有 （ ）个。
- 关于连通图的割集，下面的论断是否正确：割集是移去后可使图分为两部分的最少支路集合( )。
- 无向图的最大割问题。给定一个无向图G=(V，E)，设UVUV是G的顶点集。对任意(u，v)∈E，若有u∈U且v∈V-U，就称(u，v)为关于顶点集U的一条割边。顶点集U的所有割边构成图G的一个割。G的最大割是指G中所含边数最多的割。对于给定的无向图G，设计一个优先队列式分支限界法，计算G的最大割。