在图论中,一张无向图的线图是能体现其连边状态的一种生成图。有关线图的中文资料很少,但有关它的外文资料非常丰富。在这篇文章中,我将简单介绍线图的定义,以及提出计算线图最小生成树大小的一种方法。
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++ 代码
struct Edge{
int from,to,val,id;
};
struct Graph{
int n,m;
int node_val[maxn];
vector<Edge>e;
};
int fa[maxn];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int Kruskal(Graph G){
int ans=0;
vector<int> son[maxn];
pair<int,int> t[maxn];
for (int i=1;i<=G.n;++i)
t[i]=make_pair(G.node_val[i],i);
sort(t+1,t+1+G.n);
for (int i=1;i<=G.m;++i)
fa[i]=i;
for (int i=1;i<=G.m;++i)
son[G.e[i].from].push_back(i),
son[G.e[i].to].push_back(i);
for (int i=1;i<=G.n;++i){
int u=t[i].second;
for (int j=1;j<son[u].size();++j){
int fx=find(son[u][j-1]),fy=find(son[u][j]);
if (fx==fy) continue;
fa[fx]=fy;ans+=t[i].first;
}
}
return ans;
}
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++ 代码
struct Edge{
int from,to,val,id;
bool operator < (const Edge &x) const{
return val<x.val;
}
};
struct Graph{
int n,m;
int node_val[maxn];
vector<Edge>e;
};
int fa[maxn];
int find(int x){
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int deg[maxn],n_deg[maxn];
int Kruskal(Graph G){
int ans=0;
sort(G.e.begin(),G.e.end());
for (int i=1;i<=G.n;++i)
fa[i]=i;
for (int i=1;i<=G.m;++i){
int u=G.e[i].from,v=G.e[i].to;
int val=G.e[i].val;
if (deg[u]==1&°[v]==1) continue;
ans+=val*(deg[u]-max(1,n_deg[u]));
ans+=val*(deg[v]-max(1,n_deg[v]));
ans-=val;n_deg[u]++;n_deg[v]++;
int fx=find(u),fy=find(v);
fa[fx]=fy;
if (fx==fy) ans-=val;
}
return ans;
}