连通图G的一个割集是G的一个支路集合，则（）。
A: 一个割集包含了G的全部支路。
B: 一个割集包含了G的部分支路。
C: 一个割集是将G分为两个分离部分的最少支路集合。
D: 一个割集将G分为三个部分。
A: 一个割集包含了G的全部支路。
B: 一个割集包含了G的部分支路。
C: 一个割集是将G分为两个分离部分的最少支路集合。
D: 一个割集将G分为三个部分。
C
举一反三
- 若连通无向图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的最大割。
内容
- 0
若T是图G的一个树，则下面G中关于T的基本割集的论断是否正确：只包含T的一个树支，其他为连支的割集( )。
- 1
若T是图G的一个树，则下面G中关于T的基本割集的论断是否正确：至少包含T的一个树支，其他为连支的割集( )。
- 2
对任一容量网络G，去掉其任何一个割集，该图便不再连通；但是去掉某个割集的任意一个真子集，该图仍然连通。（ ）
- 3
若联通图G1是图G的一个子图，则图 G1可以是一个（） A: 回路 B: 树 C: 割集 D: 孤立节点
- 4
对于一个具有n个节点的图 ，其基本割集的个数为（n-1）（）