主题
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 图, 根图, 全图

使用 Wolfram|Alpha 探索

参考文献

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.

在 Wolfram|Alpha 上引用

线图

请引用为

Weisstein, Eric W. "线图。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/LineGraph.html

学科分类