promotion image of download ymail app
Promoted

圖論 cycle path circuit trail

請問

Eular circuit 等同 Eular trail

--------------------------------

Hamilton cycle 等同 Hamilton path

請問是這樣嗎? 請幫我定義

1 Answer

Rating
  • sponge
    Lv 6
    6 years ago
    Favorite Answer

    您所列的二組名詞:

    Eular circuit <-> Eular trail

    Hamilton cycle <-> Hamilton path

    第一組的確是等價關係,但第二組有些微差別

    從 walk 開始定義:

    walk 是 V_0, E_1, V_1, ..., E_k, V_k

    其中 V_0~V_k 是圖上的點,E_k 是前後兩點間的邊

    點與邊都可以任意重複

    (1)

    trail 是 walk 中邊不重複者,若開始結束於同一點稱 circuit

    Eular circuit 指這 circuit 包含圖上所有邊

    因為 trail 只要求邊不重複,點可以重複,包括頭尾

    所以它是 trail 的一種,用 Eular trail 稱呼而不混淆

    (2)

    path 是 walk 中點與邊都不重複

    但如果頭尾共點以外其他都不重複,稱為 cycle

    Hamilton path/cycle 指這 path/cycle 包含圖上所有點

    但二者還是有插在「頭尾重複」,或可理解成 cycle 多一個邊

    cycle 並不是 "path" 的一種

    所以第二組名詞差異在這邊

    不過找出 Hamilton path/cycle 的問題都稱 Hamiltonian path problem

    希望如上回答對您有幫助!

    • Commenter avatarLogin to reply the answers
Still have questions? Get your answers by asking now.