结构推理
在无向图G中，从结点u到v有一条长为偶数的通路，并有一条长为奇数的通路，则G中必有一条长为奇数的回路．
【正确答案】
证明 设从u到v长为偶数的通路是ue
1
u
1
r
2
…e
2k
v，长为奇数的通路是ue'
1
u'
1
e'
2
…e
2n+1
'v，由于G为无向图，那么ue
1
u
1
e
2
…e
2k
ve
2n+1
…e'
2
u
1
'e'
1
u就是一条长为奇数的回路．
【答案解析】
上述提及的两条通路其首尾均连接u和v，但两条通路是不一样的，故可以构成回路(奇数条边加偶数条边还为奇数条边)．
提交答案
关闭