主題
Search

可追蹤圖

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook
TraceableGraphs

可追蹤圖是具有圖，它擁有哈密頓路徑。哈密頓圖因此是可追蹤的，但反之不一定成立。不可追蹤的圖被稱為不可追蹤。

當 n=1, 2, ... 時，可追蹤圖的數量為 1, 1, 2, 5, 18, 91, 734, ... (OEIS A057864)，其中，按照慣例，單點圖 K_1 被認為是可追蹤的。上面展示了前幾個圖，每個圖的哈密頓路徑都用橙色標出。

每個自補圖都是可追蹤的 (Clapham 1974; Camion 1975; Farrugia 1999, p. 52)。

洛瓦茲猜想指出，毫無例外，每個連通頂點傳遞圖都是可追蹤的。

d維網格圖，具有任意形狀和維度，似乎都是可追蹤的，儘管在文獻中似乎沒有完全證明這一論斷（參見 Simmons 1978, Hedetniemi et al. 1980, Itai et al. 1982, Zamfirescu and Zamfirescu 1992）。

下表列出了一些可追蹤但不是哈密頓圖的著名圖。

圖 G|V(G)|
theta-0 圖7
彼得森圖10
赫舍爾圖11
Blanuša snarks18
flower snark J_520
考克斯特圖28
double star snark30
Tutte 圖46
Szekeres snark50
McLaughlin 圖276

另請參閱

歐拉回路, 哈密頓連通圖, 哈密頓圖, 次可追蹤圖, 柯尼斯堡七橋問題, 洛瓦茲猜想, 單筆畫迴路, 不可追蹤圖

使用 探索

參考文獻

Camion, P. "自補圖中的哈密頓鏈。" 收錄於 圖論研討會（巴黎，1974 年） (Ed. P. P. Gillis and S. Huyberechts). 布魯塞爾運籌學研究中心學報 17, pp. 173-183, 1975.Clapham, C. R. J. "自補圖中的哈密頓弧。" Disc. Math. 8, 251-255, 1974.Farrugia, A. "自補圖及其推廣：綜合參考手冊。" 8 月 1999. http://www.alastairfarrugia.net/sc-graph/sc-graph-survey.pdf.Godsil, C. 和 Royle, G. "哈密頓路徑和環。" C§3.6 收錄於 代數圖論。 紐約: 施普林格出版社, pp. 45-47, 2001.Gould, R. J. "哈密頓問題更新——綜述。" J. Graph Th. 15, 121-157, 1991.Hedetniemi, S. M.; Hedetniemi, S. T.; 和 Slater, P. S. "哪些網格是哈密頓圖？" Congr. Numer. 29, 511-524, 1980.Itai, A.; Papadimitriou, C. H.; 和 Szwarcfiter, J. L. "網格圖中的哈密頓路徑。" SIAM J. Comput. 11, 676-686, 1982.Mütze, T. "關於由相交集系統定義的圖中的哈密頓環。" Not. Amer. Soc. 74, 583-592, 2024.Simmons, G. J. "幾乎所有 n 維矩形格子都是哈密頓可編織的。" 收錄於 第九屆東南組合數學、圖論和計算會議論文集（佛羅里達大西洋大學，博卡拉頓，佛羅里達州，1978 年） (Ed. F. Hoffman, D. McCarthy, R. C. Mullin, and R. G. Stanton). 溫尼伯，馬尼托巴: Utilitas Mathematica Publishing, pp. 649-661, 1978.Sloane, N. J. A. “整數序列線上百科全書”中的序列 A057864。Thomassen, C. "次哈密頓圖和次可追蹤圖。" Disc. Math. 9, 91-96, 1974.Zamfirescu, C. 和 Zamfirescu, T. "網格圖的哈密頓性質。" SIAM J. Disc. Math. 5, 564-570, 1992.

在 中被引用

可追蹤圖

請引用為

Weisstein, Eric W. "可追蹤圖。" 來自 Web 資源。 https://mathworld.tw/TraceableGraph.html

學科分類