问答题 一有向图G的关联矩阵为
【正确答案】
【答案解析】解 画出图G(如下图所示),由图G可以确定:支路(2,4,5,6)是构成一个树所需的树支;支路集合(3,5,6,8)是割集。
因为树支(2,4,5,6)是连通图G的一个连通子图,它包含图G的全部节点,但不含回路,所以支路(2,4,5,6)构成一个树。如果把支路集合(3,5,6,8)全部移去,图G将分离成两个分离部分,把移去支路中任一支路放回图G,则图G仍然连通,所以支路集合(3,5,6,8)是割集。