在图论中，一张无向图的线图是能体现其连边状态的一种生成图

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

Formal definition

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

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

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

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

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

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

sort(t+1t+1+G.n);

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

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