用轉換成多級圖的方法判定圖的Ｈ性質
2004-04-29 00:00:00姜新文
計算技術與自動化 2004年2期
摘 要：給出了哈密頓圖判定問題的一個算法。思想是先將簡單無向圖轉換成多級圖，然后證明簡單無向圖中哈密頓回路存在性與多級圖中簡單路徑(定義見正文)存在性的等價性，最后通過多級圖中簡單路徑存在性的判定實現簡單無向圖H性質判定。
關鍵詞：算法；HC問題；NP完全問題
中圖分類號：TP301．6
文獻標識碼：A
摘 要：給出了哈密頓圖判定問題的一個算法。思想是先將簡單無向圖轉換成多級圖，然后證明簡單無向圖中哈密頓回路存在性與多級圖中簡單路徑(定義見正文)存在性的等價性，最后通過多級圖中簡單路徑存在性的判定實現簡單無向圖H性質判定。
關鍵詞：算法；HC問題；NP完全問題
中圖分類號：TP301．6
文獻標識碼：A
