问答题 (清华大学2006年考研试题)一有向图G的关联矩阵为:
【正确答案】正确答案:画出图G如图15—4所示,由图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)是割集。
【答案解析】