推 louis719:用矛盾證法 假設A和B vertex差2以上，然後根據hamilton 01/05 20:10
→ louis719:path的定義，可以證明不可能找到一條path經過所有頂點 01/05 20:11
→ Demonic221:阿~ 原來這題是在考你雙分圖定義熟不熟XD 謝謝>"< 01/05 23:05
let G be a bipartite graph whose vertices are divided into two sets A and B,
where no two vertices in the same set are connected. Prove that if G contains
a Hamiltonian path, then the number of vertives in A and the number of
vertices in B differ by at most 1. (Hint:What is a Hamiltonian path?)
雖然這題有個提示不過還是不知道從哪裡開始證起@@"
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.34.232.57