Menu
Article Study

【笔记】线图 / Line graph

Zepto

Zepto

• 5 min read
【笔记】线图 / Line graph

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

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&&deg[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;
}
Share