主题
Search

单位距离图


单位距离图是一个 距离图,它在欧几里得平面中有一个嵌入(单位距离嵌入),其中顶点是不同的点,所有边的长度均为 1。因此,它是 整数嵌入 的一个特例。根据定义,单位距离图的 图维度 为 2 或更小(其中 0 和 1 分别对应于 单例图 K_1路径图 P_n 的平凡连通情况)。

图成为单位距离图的最小 d 值称为其 图维度

非连通图 是单位距离图 当且仅当 其每个连通分量都是单位距离图。类似地,连通图 是单位距离图当且仅当其每个 都是单位距离图 (Chilakamarri and Mahoney 1995, Globus and Parshall 2019)。这是因为双连通分量在原始图中要么在单个点连接,在该点处它们可能被分割,要么通过 图桥 连接。由于桥梁始终可以用单位长度绘制,如果所有分量都是单位距离的,那么通过直接或用桥梁连接它们获得的图也是单位距离的。

确定一个图是否是单位距离图是 NP 困难的 (Schaefer 2013, pp. 461-482; Globus and Parshall 2019)。

任何包含 完全二部图 K_(2,3) (Erdős 1946, Chvátal 1972) 或 K_4 (Chvátal 1972) 子图 作为 顶点导出子图 的图不是单位距离图 (Horvat and Pisanski 2010)。为了理解前者,围绕两个点绘制单位圆,并注意圆不能在三个位置相交。(然而,菱形图 K_4-e (其中 e 是任意边)单位距离图。)此外,任何 色数 大于 7 的图不是单位距离图 (Horvat and Pisanski 2010)。

两个单位距离图的 图笛卡尔积 也是单位距离图 (Erdős et al. 1965, Buckley and Harary 1988, Horvat and Pisanski 2010)。这立即确定了许多图族的单位距离状态。

UnitDistanceForbidden7

将非单位距离图称为“禁用图”,并将禁用图称为最小禁用图,如果它的每个真子图都是单位距离图。Purdy 和 Purdy (1988) 试图对 7 个顶点上的最小禁用图进行分类,但他们的结果包含错误。Chilakamarri 和 Mahoney (1995) 随后证明,7 个或更少顶点上的图是单位距离图 当且仅当 它包含上述七个最小图之一作为 禁用子图。(H. Parshall 和 E. Weisstein 在 2018 年 4 月也独立获得了这一结果,尽管 Weisstein 的集合包括可以通过边删除简化为最小图的图。)Globus 和 Parshall (2019) 发现有 13 个最小禁用 8 节点图和 55 个最小禁用 9 节点图。这给出了 n=1、2、... 个节点上最小单位距离禁用图的数量,分别为 0、0、0、1、1、1、3、13、55、... (OEIS A308349)。n=1、2、... 个节点上简单连通单位距离图的相应数量为 1、1、2、5、13、51、222、1313、9639、... (OEIS A059103)。

单位距离图与 Hadwiger-Nelson 问题 密切相关,该问题询问平面的 色数(即,如果单位距离为一的两点不被赋予相同的颜色,则为平面着色所需的最小颜色数)。该值目前已知为 5、6 或 7,但发现色数等于这些值之一的单位距离图将为这些结果提供更严格的界限。

作为子图 刚性 且包含 正多边形 的单位距离图称为 支撑多边形

单位距离图的类别包括以下内容

1. 3×n 主教图黑主教图白主教图

2. 书图 S_(n+1) square P_2,

3. 仙人掌图 (Erdős et al. 1965),

4. 骆驼图

5. 超立方体连接环图

6. 环图 C_n,

7. 空图 K^__n (平凡地),

8. 齿轮图

9. 广义 Petersen 图 (Žitnik et al. 2012),

10. 长颈鹿图

11. 网格图 P_m square P_n (Horvat and Pisanski 2010),

12. 汉明图 H(d,2)H(d,3)

13. 超立方体图 Q_n (Erdős et al. 1965),

14. I 图 (Žitnik et al. 2012),

15. Jahangir 图 J_(n,m),其中 n>1,

16. 梯形图 P_m square P_2,

17. 梯子阶图 nP_2,

18. Menger 海绵图

19. 蒙古包图

20. 平底锅图

21. 路径图 P_n,

22. 多六边形

23. 多边形

24. 多米诺骨牌

25. 棱柱图 C_m square P_2 (Horvat and Pisanski 2010),

26. Sierpiński 地毯图

27. Sierpiński 垫片图

28. 堆叠书图 S_(m+1) square P_n,

29. 堆叠棱柱图 C_m square P_n (Horvat and Pisanski 2010),

30. 星图 S_n,

31. 太阳花图 C_n circledot K_1,

32. 环面网格图 C_4 square C_n,

33. (Erdős et al. 1965),以及

34. 三角蜂窝锐角骑士图,

35. 三角蜂窝钝角骑士图,

36. Web 图,以及

37. 斑马图

唯一的单位距离 轮图W_7 (Buckley and Harary 1988)。

单位距离连通 循环图 族包括

1. 环图 C_n=Ci_n(1),

2. 棱柱图 C_n square P_2P_2笛卡尔积,产生 环面网格图 C_n square P_2 square P_2=C_4 square C_n=Ci_(n(n+1))(n,n+1)

UnitDistanceGraphs

上面说明了许多单位距离图。

下表总结了一些命名的单位距离图(或更一般地,所有边都具有相同长度的图)。

UnitDistanceCubicSymmetric

许多三次对称图(除了 四面体图效用图,以及可能还有其他图)具有单位距离嵌入,如上图所示,这些嵌入主要归功于 Gerbracht(2008 年,私人通讯,2009 年 12 月至 2010 年 1 月)。


另请参阅

支撑多边形, de Grey 图, 距离图, Golomb 图, 图维度, 图嵌入, Hadwiger-Nelson 问题, Heule 图, 整数嵌入, 火柴棍图, Mixon 图, Moser 纺锤, Parts 图, 蝌蚪图, 单位距离嵌入, 单位邻域图, Voronov-Neopryatnaya-Dergachev 图, Wormald 图

使用 Wolfram|Alpha 探索

参考文献

Anning, N. H. 和 Erdős, P. "Integral Distances." Bull. Amer. Math. Soc. 51, 598-600, 1945.Buckley, F. 和 Harary, F. "On the Euclidean Dimension of a Wheel." Graphs and Combin. 4, 23-30, 1988.Chilakamarri, K. B. "Unit Distance Graphs in Rational n-Space." Discr. Math. 69, 213-218, 1988.Chilakamarri, K. B. 和 Mahoney, C. R. "Maximal and Minimal Forbidden Unit-Distance Graphs in the Plane." Bull. Inst. Combin. Appl. 13, 35-43, 1995.Chvátal, V. Problem 21 in Chvátal, V.; Klarner, D. E.; 和 Knuth, D. E. "Selected Combinatorial Research Problems." Tech. Report STAN-CS-72-292, Computer Science Department, School of Humanities and Sciences. Stanford, CA: Stanford University, pp. 11-13, 1972.Eades, P. 和 Wormald, N. C. "Fixed Edge-Length Graph Drawing Is NP-Hard." Discr. Appl. Math. 28, 111-134, 1990.Eppstein, D. "Unit Distance Graphs." 2010 年 1 月 4 日. http://11011110.livejournal.com/188807.html.Erdős, P. "On Sets of Distances of n Points." Amer. Math. Monthly 53, 248-250, 1946.Erdős, P.; Harary, F.; 和 Tutte, W. T. "On the Dimension of a Graph." Mathematika 12, 118-122, 1965.Gerbracht, E. H.-A. "On the Unit Distance Embeddability of Connected Cubic Symmetric Graphs." Kolloquium über Kombinatorik. Magdeburg, Germany. 2008 年 11 月 15 日.Globus, A. 和 Parshall, H. "Small Unit-Distance Graphs in the Plane." Bull. Inst. Combin. Appl. 90, 107-138, 2020.Hochberg, R. "A Program for Proving That a Given Graph Is Not a Unit-Distance Graph: Preliminary Report." In Proceedings of the 44th Annual Southeast Regional Conference (Melbourne, Florida, March 10-12, 2006). ACM-SE 44. 2006.Hochberg, R. 和 O'Donnell, P. "Some 4-Chromatic Unit-Distance Graphs Without Small Cycles." Geombinatorics 5, 137-141, 1996.Horvat, B. 和 Pisanski, T. "Products of Unit Distance Graphs." Disc. Math. 310, 1783-1792, 2010.Kurz, S. "Fast Recognition of Planar Non Unit Distance Graphs - Searching the Minimum 4-Regular Planar Unit Distance Graph." Submitted. http://www.wm.uni-bayreuth.de/fileadmin/Sascha/Publikationen/unmasking_non_unit_distance_graphs.pdf.Maehara, H. "On Euclidean Dimension of a Complete Multipartite Graph." Discr. Math. 72, 285-289, 1988.Maehara, H. "Note on Induced Subgraphs of the Unit Distance Graph." Discr. Comput. Geom. 4, 15-18, 1989.Maehara, H. "Distances in a Rigid Unit-Distance Graph in the Plane." Discr. Appl. Math. 31, 193-200, 1991.Maehara, H. "Distance Graphs in Euclidean Space." Ryukyu Math. J. 5, 33-51, 1992.Maehara, H. 和 Rödl, V. "On the Dimension to Represent a Graph by a Unit Distance Graph." Graphs Combin. 6, 365-367, 1990.Moser, L. 和 Moser, W. "Problem 10." Canad. Math. Bull. 4, 187-189, 1961.Purdy, C. 和 Purdy, G. "Minimal Forbidden Distance One Graphs." Congr. Numer. 66, 165-172, 1988.Schaefer, M. "Realizability of Graphs and Linkages." In Thirty Essays on Geometric Graph Theory. New York: Springer, pp. 461-482, 2013.Sloane, N. J. A. Sequences A059103A308349 in "The On-Line Encyclopedia of Integer Sequences."Soifer, A. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators. New York: Springer, 2008.Soifer, A. The New Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of Its Creators, 2nd ed. New York: Springer, 2024.Žitnik, A.; Horvat, B.; 和 Pisanski, T. "All Generalized Petersen Graphs are Unit-Distances Graphs." J. Korean Math. Soc. 49, 475-491, 2012.

在 Wolfram|Alpha 上引用

单位距离图

请引用本文为

Weisstein, Eric W. "单位距离图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/Unit-DistanceGraph.html

学科分类