主題
Search

格林菲爾德圖

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
GreenfieldGraph

格林菲爾德圖是本文中對格林菲爾德 (2011) 提出的上述 12 頂點圖的命名。這個圖提供了第一個已知的反例，否定了 Gibbons 和 Laison (2009) 提出的關於計算貪婪演算法對於固定數是否定義明確的問題。對於格林菲爾德圖的情況，此演算法可能返回 3 或 4，而實際的固定數是 3。

格林菲爾德 (2011, p. 44) 提出，這個圖是一個最小的反例。E. Weisstein（2023 年 6 月 6 日）在使用特定的平局選擇策略搜尋到 10 個節點時，沒有發現更小的反例，但確實發現了一些更大的反例。

格林菲爾德圖在 Wolfram 語言中實現為GraphData["GreenfieldGraph"].

另請參閱

固定數, 貪婪演算法

使用 探索

參考文獻

Gibbons, C. R. 和 Laison, J. D. "Fixing Numbers of Graphs and Groups." Electron. J. Combin. 16, No. R39, 2009.Greenfield, K. B. "The Fixing Number of a Graph." 學士學位論文。Worcester, MA: Worcester Polytechnic Institute, 2011.

請引用為

Weisstein, Eric W. "Greenfield Graph." 來自 Web 資源。 https://mathworld.tw/GreenfieldGraph.html

主題分類