主題
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 圖

使用 探索

參考文獻

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.

在 上引用

單位距離圖

請引用本文為

Weisstein, Eric W. "單位距離圖。" 來自 Web 資源。 https://mathworld.tw/Unit-DistanceGraph.html

學科分類