【正确答案】：
证明:必要性 设e是割边,反证,若e包含在G的某一个回路p中。
对于∀u,v∈V,u到v之间必定有通路P1(图的连通性保证)。
(1)若p1不包含边e,则删除e后仍能保证u到v之间有通路,即图仍是连通的。与e是割边矛盾。
(2)若P1包含边e,P1中的顶点序列为u,...,
,v,因p是回路,p中任意两顶点之间的通路至少有两条,删除e后,
和
之间仍是连通的,
证明:e是割边,当且仅当e不包含在G的任一回路中。
- 2024-08-04 00:04:59
- 离散数学(02324)
证明:e是割边,当且仅当e不包含在G的任一回路中。
【正确答案】：
【正确答案】：