主題
Search

線圖

DOWNLOAD Mathematica Notebook下載 Wolfram 筆記本
LineGraph

線圖 L(G) （也稱為伴隨圖、共軛圖、覆蓋圖、導數圖、匯出圖、邊圖、邊到頂點對偶圖、互換圖、代表圖或 theta-obrazom 圖）是透過將圖的每條邊關聯一個頂點，並且當且僅當 iff G 的對應邊有一個公共頂點時，連線兩個頂點而獲得的 簡單圖 G (Gross and Yellen 2006, p. 20)。

給定一個線圖 L(G)，其底層圖 G 被稱為 L(G) 的 根圖。 簡單 線圖的 根圖 是唯一的，除了 K_3=C_3 的情況 (Harary 1994, pp. 72-73)。

LineGraphDirected

有向圖 G 的線圖是 有向圖 L(G)，其 頂點集 對應於 G 的 弧集，並且如果 G 中邊 e_1 的頭與邊 e_2 的尾相遇，則存在從邊 e_1 到邊 e_2 的 弧 (Gross and Yellen 2006, p. 265)。

線圖在 Wolfram 語言中實現為LineGraph[g]。 許多命名圖的預計算線圖示識可以在 Wolfram 語言中使用以下方式獲得GraphData[graph,"LineGraphName"].

頂點數為 n=1, 2, ... 的簡單線圖的數量分別是 1, 2, 4, 10, 24, 63, 166, 471, 1408, ... (OEIS A132220)，而連通簡單線圖的數量分別是 1, 1, 2, 5, 12, 30, 79, 227, ... (OEIS A003089)。

下表總結了一些命名圖及其對應的線圖。

GL(G)
爪形圖 K_(1,3)三角形圖 C_3
完全二部圖 K_(2,3)稜柱圖 Y_3
立方圖立方八面體圖
圈圖 C_n圈圖 C_n
十二面體圖二十面十二面體圖
路徑圖 P_2單點圖 K_1
路徑圖 P_n路徑圖 P_(n-1)
方形圖 C_4方形圖 C_4
星圖 S_5四面體圖 K_4
星圖 S_6五胞體 圖 K_5
星圖 S_n完全圖 K_(n-1)
四面體圖 K_4八面體圖
三角形圖 C_3三角形圖 C_3

線圖是 無爪圖。

具有 n 個節點、e 條邊和頂點度 d_i 的 圖 的線圖包含 n^'=e 個節點和

e^'=1/2sum_(i=1)^nd_i^2-e

條邊 (Skiena 1990, p. 137)。 圖的 關聯矩陣 C 和其線圖的 鄰接矩陣 L 透過下式相關：

L=C^(T)C-2I,

其中 I 是 單位矩陣 (Skiena 1990, p. 136)。

Krausz (1943) 證明了對於一個簡單圖 G，當且僅當 iff G 分解為完全子圖，且 G 的每個頂點最多出現在分解的兩個成員中時，解 L(H)=G 存在。 然而，由於可能涉及大量分解，該定理對於實現高效演算法沒有用處 (West 2000, p. 280)。

van Rooij 和 Wilf (1965) 表明，對於一個簡單圖 G，當且僅當 iff G 是 無爪圖 且 G 的任何匯出 鑽石圖 沒有兩個奇三角形時，解 L(H)=G 存在。 在這裡，如果對於某個 v in V(G)，鄰域 N(v) 和頂點集 V(T) 的交集中的點數為奇數，則稱三角形子圖 T 為偶三角形；如果對於每個 v in V(G)，N(V) 和 V(T) 的交集中的點數為偶數，則稱三角形子圖 T 為偶三角形 (West 2000, p. 281)。

NonLineGraphs

一個 簡單圖 是某個 簡單圖 的線圖，當且僅當 iff 它不包含上述九個 Beineke 圖 中的任何一個作為 禁忌匯出子圖 (van Rooij and Wilf 1965; Beineke 1968; Skiena 1990, p. 138; Harary 1994, pp. 74-75; West 2000, p. 282; Gross and Yellen 2006, p. 405)。 這個陳述有時被稱為 Beineke 定理。 這九個圖在 Wolfram 語言中實現為GraphData["Beineke"]。 在這九個圖中，一個有四個節點（爪形圖 = 星圖 S_4 = 完全二部圖 K_(1,3)），兩個有五個節點，六個有六個節點（包括 輪圖 W_6）。

NonLineGraphs5

最小頂點度至少為 5 的圖是線圖，當且僅當 iff 它不包含上述六個 Metelsky 圖 中的任何一個作為 匯出子圖 (Metelsky and Tyshkevich 1997)。 這六個圖在 Wolfram 語言中實現為GraphData["Metelsky"].

如果圖的 圖譜 的最小元素小於 -2，則該圖不是線圖 (Van Mieghem, 2010, Liu et al. 2010)。

Whitney (1932) 表明，除了 K_3 和 K_(1,3) 之外，任何兩個具有同構線圖的 連通圖 都是同構的 (Skiena 1990, p. 138)。

Lehot (1974) 給出了一個線性時間演算法，可以從其線圖重建原始圖。 Liu et al. (2010) 給出了一個 O(n^2) 演算法，用於從其線圖重建原始圖，其中 n 是線圖中的頂點數。 該演算法比 Roussopoulos (1973) 的高效演算法更省時。

尤拉圖 的線圖既是尤拉圖又是 哈密頓圖 (Skiena 1990, p. 138)。 關於線圖的圈的更多資訊由 Harary 和 Nash-Williams (1965) 以及 Chartrand (1968) 給出。

LineGraphs

取兩次線圖不會返回原始圖，除非圖 G 的線圖與 G 自身同構。 事實上，唯一與自身線圖同構的 連通圖 是 C_n 的 圈圖，其中 n>=3 (Skiena 1990, p. 137)。 圈圖的圖並 (例如，2C_3、C_3+C_4 等) 也與其線圖同構，因此與其線圖同構的圖是度為 2 的正則圖，並且與其線圖同構的非必要連通簡單圖的總數由其具有最小部分 >=3 的 頂點計數 的分割槽數給出，對於 n=1, 2, ... 分別為 0, 0, 1, 1, 1, 2, 2, 3, 4, 5, 6, 9, 10, 13, 17, ... (OEIS A026796)，其中前幾個在上面進行了說明。

另請參閱

Beineke 圖, 無爪圖, Metelsky 圖, 根圖, 全圖

使用 探索

參考文獻

Beineke, L. W. "Derived Graphs and Digraphs." In Beiträge zur Graphentheorie (Ed. H. Sachs, H. Voss, and H. Walther). Leipzig, Germany: Teubner, pp. 17-33, 1968.Beineke, L. W. "Characterizations of Derived Graphs." J. Combin. Th. 9, 129-135, 1970.Chartrand, G. "On Hamiltonian Line Graphs." Trans. Amer. Math. Soc. 134, 559-566, 1968.Degiorgi, D. G. and Simon, K. "A Dynamic Algorithm for Line Graph Recognition." In WG '95: Proceedings of the 21st International Workshop on Graph-Theoretic Concepts in Computer Science. London: Springer-Verlag, pp. 37-48, 1995.DistanceRegular.org. "Line Graphs." http://www.distanceregular.org/indexes/linegraphs.html.Gross, J. T. and Yellen, J. Graph Theory and Its Applications, 2nd ed. Boca Raton, FL: CRC Press, pp. 20 and 265, 2006.Harary, F. Graph Theory. Reading, MA: Addison-Wesley, 1994.Harary, F. and Nash-Williams, C. J. A. "On Eulerian and Hamiltonian Graphs and Line Graphs." Canad. Math. Bull. 8, 701-709, 1965.Krausz, J. "Démonstration nouvelle d'une théorème de Whitney sur les réseaux." Mat. Fiz. Lapok 50, 78-89, 1943.Lehot, P. G. H. "An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph." J. ACM 21, 569-575, 1974.Liu, D.; Trajanovski, S.; and Van Mieghem, P. "Reverse Line Graph Construction: The Matrix Relabeling Algorithm MARINLINGA Versus Roussopoulos's Algorithm." 22 Oct 2010. http://arxiv.org/abs/1005.0943.Metelsky, Yu. and Tyshkevich, R. "On Line Graphs of Linear 3-Uniform Hypergraphs." J. Graph Th. 25, 243-251, 1997.Naor, J. and Novick, M. B. "An Efficient Reconstruction of a Graph from Its Line Graph in Parallel." J. Algorithms 11, 132-143, 1990.Roussopoulos, N. D. "A max{m,n} Algorithm for Determining the Graph H From Its Line Graph G." Info. Proc. Let. 2, 108-112, 1973.Saaty, T. L. and Kainen, P. C. "Line Graphs." §4-3 in The Four-Color Problem: Assaults and Conquest. New York: Dover, pp. 108-112, 1986.Skiena, S. "Line Graph." §4.1.5 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 128 and 135-139, 1990.Sloane, N. J. A. Sequences A003089/M1417, A026796, and A132220 in "The On-Line Encyclopedia of Integer Sequences."Šoltés, Ľ. "Forbidden Induced Subgraphs for Line Graphs." Disc. Math. 132, 391-394, 1994.Van Mieghem, P. Graph Spectra for Complex Networks. Cambridge, England: Cambridge University Press, 2010.van Rooij, A. and Wilf, H. "The Interchange Graph of a Finite Graph." Acta Math. Acad. Sci. Hungar. 16, 263-269, 1965.Roussopoulos, N. D. "A max{m,n} Algorithm for Determining the Graph h from its Line Graph g." Inform. Proc. Lett. 2, 108-112, 1973.West, D. B. "Characterizing Line Graphs." Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 279-282, 2000.Whitney, H. "Congruent Graphs and the Connectivity of Graphs." Amer. J. Math. 54, 150-168, 1932.

在 上引用

線圖

請引用為

Weisstein, Eric W. "線圖。" 來自 Web 資源。 https://mathworld.tw/LineGraph.html

學科分類