主题
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.net.cn/LineGraph.html

学科分类