图的线图
字数 2372 2025-12-09 06:33:17

图的线图

我们从一个具体的图 \(G\) 开始理解。设 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集。

  1. 线图的定义
    图 \(G\) 的线图，记为 \(L(G)\)，是另一个图，其构造规则如下：
  • \(L(G)\) 的每个顶点，对应原图 \(G\) 中的一条边。
  • 在 \(L(G)\) 中，两个顶点之间存在一条边，当且仅当它们所对应的 \(G\) 中的两条边在原图 \(G\) 中共享一个公共顶点（即这两条边是相邻的）。
    换句话说，线图将原图中“边”之间的关系，提升为“顶点”之间的关系。
  1. 一个简单例子
    考虑一个简单的路径图 \(P_3\)，它有 3 个顶点和 2 条边：\(V(P_3) = \{v_1, v_2, v_3\}\)，\(E(P_3) = \{e_1 = v_1v_2, e_2 = v_2v_3\}\)。
    构建其线图 \(L(P_3)\)：
  • \(L(P_3)\) 的顶点集：有两个顶点，分别对应 \(e_1\) 和 \(e_2\)，我们记作 \(u_1\) (对应 \(e_1\)) 和 \(u_2\) (对应 \(e_2\))。
  • 在 \(P_3\) 中，边 \(e_1\) 和 \(e_2\) 共享公共顶点 \(v_2\)，因此它们是相邻的。
  • 所以在 \(L(P_3)\) 中，顶点 \(u_1\) 和 \(u_2\) 之间用一条边相连。
  • 最终，\(L(P_3)\) 是一个由两个顶点和连接它们的一条边组成的图，即它同构于 \(P_2\)（两个顶点的路径）。
  1. 度数的变化
    在原图 \(G\) 中，一条边关联两个顶点。设边 \(e = uv \in E(G)\)，顶点 \(u\) 的度数为 \(d(u)\)，顶点 \(v\) 的度数为 \(d(v)\)。
    在 \(L(G)\) 中，对应边 \(e\) 的顶点（记为 \(w_e\)）的度数是多少？它等于在 \(G\) 中与边 \(e\) 相邻的边的数量。
    与 \(e\) 相邻的边包括：
  • 所有在 \(G\) 中与顶点 \(u\) 关联的其他边（除了 \(e\) 本身），共有 \(d(u) - 1\) 条。
  • 所有在 \(G\) 中与顶点 \(v\) 关联的其他边（除了 \(e\) 本身），共有 \(d(v) - 1\) 条。
    因此，在 \(L(G)\) 中，顶点 \(w_e\) 的度数为：

\[ d_{L(G)}(w_e) = (d_G(u) - 1) + (d_G(v) - 1) = d_G(u) + d_G(v) - 2 \]

这个公式建立了原图顶点度数与线图顶点度数之间的基本联系。
  1. 线图的若干性质
  • 连通性：如果原图 \(G\) 是连通的且边数至少为 1，那么其线图 \(L(G)\) 也是连通的。
  • 同构与原图恢复：不同的原图可能拥有同构的线图，例如星图 \(K_{1,3}\) 和路径图 \(P_3\) 的线图都是 \(P_3\) 本身。并非所有图都是某个图的线图。线图猜想（已被证明为定理）指出：一个图是某个图的线图，当且仅当它可以被一组完全子图（团）所覆盖，使得其每条边恰好在一个团中，并且其顶点满足特定的“可着色”条件（避开了 9 个特定的禁用子图）。恢复原图 \(G\) （在同构意义下）的过程称为“原图重构”，对于连通图，除了少数几个特例（如 \(K_3\) 和 \(K_{1,3}\) 的线图同构），原图是唯一确定的。
  • 迭代线图：可以对线图再次取线图，得到 \(L^2(G) = L(L(G))\)，以此类推。迭代线图的性质是图论中的一个研究方向。
  1. 线图与原图参数的关系
  • 顶点数与边数：设 \(G\) 有 \(n\) 个顶点，\(m\) 条边。则 \(L(G)\) 的顶点数就是 \(m\)。\(L(G)\) 的边数可以通过对原图所有顶点求和来计算：在原图每个顶点 \(v\) 处，关联它的 \(d(v)\) 条边在线图中两两相邻，形成一个大小为 \(d(v)\) 的团（完全子图），这个团贡献了 \(\binom{d(v)}{2}\) 条边。因此：

\[ |E(L(G))| = \sum_{v \in V(G)} \binom{d(v)}{2} = \frac{1}{2} \sum_{v \in V(G)} (d(v)^2 - d(v)) \]

  • 与关联矩阵的关系：设 \(B\) 是图 \(G\) 的顶点-边关联矩阵（行对应顶点，列对应边，如果边关联顶点则对应元素为 1，否则为 0）。那么，线图 \(L(G)\) 的邻接矩阵 \(A_L\) 满足 \(A_L = B^T B - 2I_m\)，其中 \(I_m\) 是 \(m\) 阶单位矩阵。而 \(B B^T\) 则是 \(G\) 的顶点邻接矩阵加上度对角矩阵。
  1. 应用
  • 图论本身：线图是研究边着色、欧拉环、中国邮递员问题等的有力工具。例如，原图 \(G\) 的一个正常边着色对应其线图 \(L(G)\) 的一个正常顶点着色。
    • 化学：在化学图论中，线图可以用来表示分子中化学键之间的关系。
    • 网络科学：在研究交通网络、通信网络时，有时将路线（对应原图的边）作为分析对象更为自然，这时就可以利用线图模型。
图的线图 我们从一个具体的图 \( G \) 开始理解。设 \( G = (V, E) \)，其中 \( V \) 是顶点集，\( E \) 是边集。 线图的定义 图 \( G \) 的 线图 ，记为 \( L(G) \)，是另一个图，其构造规则如下： \( L(G) \) 的每个顶点，对应原图 \( G \) 中的一条边。 在 \( L(G) \) 中，两个顶点之间存在一条边，当且仅当它们所对应的 \( G \) 中的两条边在原图 \( G \) 中共享一个公共顶点（即这两条边是相邻的）。 换句话说，线图将原图中“边”之间的关系，提升为“顶点”之间的关系。 一个简单例子 考虑一个简单的路径图 \( P_ 3 \)，它有 3 个顶点和 2 条边：\( V(P_ 3) = \{v_ 1, v_ 2, v_ 3\} \)，\( E(P_ 3) = \{e_ 1 = v_ 1v_ 2, e_ 2 = v_ 2v_ 3\} \)。 构建其线图 \( L(P_ 3) \)： \( L(P_ 3) \) 的顶点集：有两个顶点，分别对应 \( e_ 1 \) 和 \( e_ 2 \)，我们记作 \( u_ 1 \) (对应 \( e_ 1 \)) 和 \( u_ 2 \) (对应 \( e_ 2 \))。 在 \( P_ 3 \) 中，边 \( e_ 1 \) 和 \( e_ 2 \) 共享公共顶点 \( v_ 2 \)，因此它们是相邻的。 所以在 \( L(P_ 3) \) 中，顶点 \( u_ 1 \) 和 \( u_ 2 \) 之间用一条边相连。 最终，\( L(P_ 3) \) 是一个由两个顶点和连接它们的一条边组成的图，即它同构于 \( P_ 2 \)（两个顶点的路径）。 度数的变化 在原图 \( G \) 中，一条边关联两个顶点。设边 \( e = uv \in E(G) \)，顶点 \( u \) 的度数为 \( d(u) \)，顶点 \( v \) 的度数为 \( d(v) \)。 在 \( L(G) \) 中，对应边 \( e \) 的顶点（记为 \( w_ e \)）的度数是多少？它等于在 \( G \) 中与边 \( e \) 相邻的边的数量。 与 \( e \) 相邻的边包括： 所有在 \( G \) 中与顶点 \( u \) 关联的其他边（除了 \( e \) 本身），共有 \( d(u) - 1 \) 条。 所有在 \( G \) 中与顶点 \( v \) 关联的其他边（除了 \( e \) 本身），共有 \( d(v) - 1 \) 条。 因此，在 \( L(G) \) 中，顶点 \( w_ e \) 的度数为： \[ d_ {L(G)}(w_ e) = (d_ G(u) - 1) + (d_ G(v) - 1) = d_ G(u) + d_ G(v) - 2 \] 这个公式建立了原图顶点度数与线图顶点度数之间的基本联系。 线图的若干性质 连通性 ：如果原图 \( G \) 是连通的且边数至少为 1，那么其线图 \( L(G) \) 也是连通的。 同构与原图恢复 ：不同的原图可能拥有同构的线图，例如星图 \( K_ {1,3} \) 和路径图 \( P_ 3 \) 的线图都是 \( P_ 3 \) 本身。并非所有图都是某个图的线图。 线图猜想 （已被证明为定理）指出：一个图是某个图的线图，当且仅当它可以被一组完全子图（团）所覆盖，使得其每条边恰好在一个团中，并且其顶点满足特定的“可着色”条件（避开了 9 个特定的禁用子图）。恢复原图 \( G \) （在同构意义下）的过程称为“原图重构”，对于连通图，除了少数几个特例（如 \( K_ 3 \) 和 \( K_ {1,3} \) 的线图同构），原图是唯一确定的。 迭代线图 ：可以对线图再次取线图，得到 \( L^2(G) = L(L(G)) \)，以此类推。迭代线图的性质是图论中的一个研究方向。 线图与原图参数的关系 顶点数与边数 ：设 \( G \) 有 \( n \) 个顶点，\( m \) 条边。则 \( L(G) \) 的顶点数就是 \( m \)。\( L(G) \) 的边数可以通过对原图所有顶点求和来计算：在原图每个顶点 \( v \) 处，关联它的 \( d(v) \) 条边在线图中两两相邻，形成一个大小为 \( d(v) \) 的团（完全子图），这个团贡献了 \( \binom{d(v)}{2} \) 条边。因此： \[ |E(L(G))| = \sum_ {v \in V(G)} \binom{d(v)}{2} = \frac{1}{2} \sum_ {v \in V(G)} (d(v)^2 - d(v)) \] 与关联矩阵的关系 ：设 \( B \) 是图 \( G \) 的顶点-边关联矩阵（行对应顶点，列对应边，如果边关联顶点则对应元素为 1，否则为 0）。那么，线图 \( L(G) \) 的邻接矩阵 \( A_ L \) 满足 \( A_ L = B^T B - 2I_ m \)，其中 \( I_ m \) 是 \( m \) 阶单位矩阵。而 \( B B^T \) 则是 \( G \) 的顶点邻接矩阵加上度对角矩阵。 应用 图论本身 ：线图是研究边着色、欧拉环、中国邮递员问题等的有力工具。例如，原图 \( G \) 的一个正常边着色对应其线图 \( L(G) \) 的一个正常顶点着色。 化学 ：在化学图论中，线图可以用来表示分子中化学键之间的关系。 网络科学 ：在研究交通网络、通信网络时，有时将路线（对应原图的边）作为分析对象更为自然，这时就可以利用线图模型。