问答题
在无向图G中，从结点u到结点v有一条长度为偶数的通路，从结点u到结点v又有一条长度为奇数的通路，证明：在G中必有一条长度为奇数的回路．
【正确答案】
设从结点u到结点v长度为偶数的通路是ue
1
u
1
e
2
u
2
…e
2k
v，长度为奇数的通路是ue'
1
u'
1
e'
2
u'
2
…e'
2h-1
v，那么，通路ue
1
u
1
e
2
u
2
…e
2k
ve'
2h-1
…u'
2
e'
2
u'
1
e'
1
u就是一条回路，它的边数=2k+(2h-1)=2(h+k)-1，是奇数，故这条回路的长度是奇数．
【答案解析】
提交答案
关闭