图的线图 基本定义 图的线图（Line Graph）是一种从原图派生出的新图，记作 \( L(G) \)。其构造规则如下： 将原图 \( G \) 的每条边 \( e \in E(G) \) 转化为 \( L(G) \) 的一个顶点。 若原图 \( G \) 中两条边 \( e_ 1 \) 和 \( e_ 2 \) 有公共顶点（即相邻），则在 \( L(G) \) 中对应的顶点连一条边。 示例 ：若 \( G \) 是一个三角形（3条边），则 \( L(G) \) 也是一个三角形，因为每条边均与另外两条边相邻。 性质与特征 顶点度 ：在 \( L(G) \) 中，一个顶点的度等于原图对应边两端顶点的度之和减2。例如，若边 \( e \) 连接度数为 \( d(u) \) 和 \( d(v) \) 的顶点，则 \( \deg_ {L(G)}(e) = d(u) + d(v) - 2 \)。 连通性 ：若 \( G \) 连通且边数 \( |E(G)| \geq 1 \)，则 \( L(G) \) 必连通。 禁止子图 ：线图存在禁用特征（如 \( K_ {1,3} \) 爪形结构不能作为线图的诱导子图），这由比曼（Beineke）定理完整描述。 应用与推广 图论问题转化 ：某些原图问题可转化为线图的等价问题。例如，求 \( G \) 的边着色数等价于求 \( L(G) \) 的顶点着色数。 迭代线图 ：可对线图多次迭代（如 \( L^2(G) = L(L(G)) \)），研究其收敛性（如最终变为正则图或空图）。 有向图推广 ：有向图的线图定义类似，但需区分边的方向性（如仅当一条边的终点是另一条边的起点时才对应对应顶点相邻）。 算法与复杂度 识别算法 ：存在多项式时间算法判断一个图是否为某图的线图（如基于度序列和局部结构检测）。 重建问题 ：惠特尼（Whitney）定理指出，若两个连通图不同构于三角形或完全二部图 \( K_ {1,3} \)，则它们的线图同构当且仅当原图同构（唯一性有例外情况）。 扩展研究方向 超图线图 ：将超图的超边视为顶点，若超边有公共顶点则连边，推广线图概念。 谱性质 ：线图的邻接矩阵谱与原图的边-边关联矩阵相关，可用于分析图的结构特征。