格林菲尔德图

格林菲尔德图是本文中对格林菲尔德 (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.net.cn/GreenfieldGraph.html