Enable JavaScript to interact with content and submit forms on Wolfram websites. Learn how

LineGraph

给出图 g 的线图.

LineGraph[{vw,…}]

使用规则 vw 指定图 g.

更多信息和选项

LineGraph[g] 中的每个顶点对应于 g 中的每条边.
对于一个无向图 g，如果 LineGraph[g] 中的这两个顶点对应的边共享一个顶点，那么称这两个顶点是相邻的.

对于一个有向图 g，如果 LineGraph[g] 中的这两个顶点对应的边是连通的，即一条边的终点是另一条边的起点，那么称这两个顶点是相邻的.
LineGraph[g] 中的顶点采用从1开始的连续整数.
LineGraph 可用于无向图、有向图和多图.

背景

LineGraph 返回的线图，其顶点是的边而其顶点邻接对应于的边邻接. 更正式地，给定有边 e₁,…,e_m 的图，则其有顶点 e₁,…,e_m. 对于无向图，若和入射于中的相同顶点则是中的边，而对于有向图，若图中的头部是的尾部则是中的边. 线图也称作伴随图、共轭图、覆盖图、衍生图、导出图、边图、边-点对偶图、代表图或 -obrazom 图.
线图被用于将图的关于顶点的理论结果翻译成关于边的结果. 例如，中的独立边集是中的独立顶点集，的边色数等于的色数等等.
线图通过一系列数学关系与其原始图相连接. 其中最简单的关系即的顶点数目等于的边数目. 另外，如果是一个有条边和点指数为 d₁,…,d_n 的个顶点的简单图，则中的边数目为 . 另一个允许线图显式结构的关系是对于简单图的关联矩阵和 m×m 的单位矩阵，的相邻矩阵由给出.
一个图是否为线图的判定可以在线性时间内做出. 当且仅当存在一个团族，图中的各顶点正好含有其中的两个元素，并且图中的各边由其中的一个元素引发时，图是简单图或多重图的线图. 若这个团族中的任意两个顶点不再两个相同的团中，则是简单图的线图.
若有含有九个禁向图的集合，各图至多有六个顶点，那么当且仅当其中不含作为该集合中诱导子图的图时，简单图是某些简单图的线图. 这个禁向图的集合由 GraphData["Beineke"] 给出并包含完整二分图，所以线图是无爪图. 这些禁向图中只有六个需要显示哪个有不少于5的最大度的简单图是线图（参见 GraphData["Metelsky"]）.
图论中的许多重要结果描述线图的特性. 例如，Vizing 理论意味着如果是个不含三角的简单图，则的色数等于中最大团的大小或比起多一，而 König 线着色理论一表明一个两偶图的线图是完美的（即的各诱导子图的色数等于该子图的最大团的大小）.

范例

打开所有单元关闭所有单元

基本范例 (1)

一个完全图的线图：

范围 (5)

LineGraph 适用于无向图：

有向图：

多图：

使用规则指定图：

LineGraph 也可用于大规模图：

属性和关系 (11)

一个图的边数等于对应的线图的顶点数：

一个连通图的线图是连通的：

一个线图的邻接矩阵可以通过计算：

在 g 的线图中的最大独立集合对应于 g 的最大匹配：

一个圈图与它的线图是同构的：

一个爪图的线图是一个三角形：

一个路径图的线图与是同构：

一个二分图的线图是完美的：

一个哈密顿图的线图是哈密顿的：

一个无向欧拉图的线图是欧拉图：

一个欧拉图的线图是哈密顿图：

巧妙范例 (1)

顶部