在图论中,一张无向图的线图是能体现其连边状态的一种生成图。有关线图的中文资料很少,但有关它的外文资料非常丰富。在这篇文章中,我将简单介绍线图的定义,以及提出计算线图最小生成树大小的一种方法。

Formal definition

给定一张无向图 $G$,它的线图 $L(G)$ 满足以下条件

  • $L(G)$ 中的每个节点表示 $G$ 中的一条边;
  • $L(G)$ 中两个节点之间连边,当且仅当它们代表的边在 $G$ 中有公共点。

Example

下面展示了一张图(蓝色节点)和它的线图(绿色节点),线图上每个节点标出了原图上边两个端点的编号。

Minimum spanning tree

现在我们有一张无向图 $G$ 和它的线图 $L(G)$。如果我们我们把图 $G$ 的点和边都赋上权值,在 $L(G)$ 中,我们可以认为点权为原图中对应边的边权,边权为原图中对应公共点的点权。

我们解决这个问题的思路都基于 Kruskal 算法。

for $L(G)$

Kruskal 基于一个贪心思想:优先选择边权小的边。

在我们按点权对 $G$ 中的节点排序,那么 $L(G)$ 中被优先加入最小生成树的边就是 $G$ 中点权最小的点连出的某两条边在 $L(G)$ 中对应的两个点之前的边。

如图,蓝点和实线是 $G$ 中的点和边,绿点和虚线是 $L(G)$ 中的点和边。按点权从小到大处理到上图中心处蓝点时,我们需要做的是让 $L(G)$ 的边组成的这个环联通。显然,加入边的顺序对最小生成树没有影响,因为它们的边权相同,最终的效果也相同。

C++ 代码

for $L(L(G))$

对于线图的线图,情况要稍稍复杂一点。

对于下图,蓝点属于 $G$,绿点属于 $L(G)$,而黄点属于 $L(L(G))$。为了方便,$L(L(G))$ 中的边没有全部绘出。

我们知道,经过两次变换之后,$L(L(G))$ 中边的边权和 $G$ 中边的边权是相等的。遵循 Kruskal 算法的思想,我们按边权对 $G$ 中的边进行排序。在下图中,蓝色边是我们要处理的 $G$ 中最小的边,而绿色的边是和它边权相等的 $L(L(G))$ 中的边。

记蓝色边的两个端点为 $u,v$,点 $i$ 的度数为 $d_i$,绿色边的数量为 $d_u+d_v-2$。 要让这些点联通,我们需要做的是选择 $d_u+d_v-3$ 条绿边。

为了给读者一点思考的难度,接下来的处理方式我不再做说明,请读者自行画图理解。如果要给一点提示的话,这里遵循的是连通分量与度数的基本关系。

C++ 代码