Re: [理工] 中央資工-離散 圖論

[liataian (T-PANY FOREVER)]

※ 引述《showyoulovex (NONO)》之銘言：
: 題目:
: T or F
: A hamiltonian graph contains no proper cycles
: 答案  F
: 若漢米頓內有其他cycle 不就不存在hamiltonian cycle了嗎?
: 還是我對 hamiltonian graph 有誤解呢?
: 還請各位高手幫我解答

  以下只是我的見解 有錯還請大家幫忙糾正

  我想hamiltonian graph是代表一個graph具有Hamiltonian cycle

  http://en.wikipedia.org/wiki/Hamiltonian_path  參考wiki

  然後proper cycle我記得是指"剛好具有三個邊"的cycle

  以下圖為例

                              A
                            / | \
                          C - B - E
                            \   /
                              D

  此圖具有Hamiltonian cycle : ABCDEA

  可是此圖也具有proper cycles : ABC 或 ABE

  所以A hamiltonian graph contains no proper cycles是錯的


--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.135.112.134
推 AIdrifter:不好意思 我覺得另一句話也是錯的 如果是3點的情況
→ AIdrifter:K3具有HC 他也有proper cycles阿
→ AIdrifter:說他沒proper cycle那他HC就不見了@@
→ liataian:對吼 我沒考慮到 歹勢XD 我修改一下~
※ 編輯: liataian        來自: 140.135.112.134      (11/21 00:30)
※ 編輯: liataian        來自: 140.135.112.134      (11/21 00:42)