图论学习笔记5

图论学习笔记5

一月 07, 2024

定义

平面图的定义是一张无向图如果能够画在一个平面上，使得其任意两条边不在交点处相交，那么这个无向图就是一个平面图。

并且这个无向图需要连通。

$K_{3,3}$ 和 $K_{5}$ 不是平面图。

$K_{3,3}$ 是二分图，左部右部均有 $3$ 个点，任意两个不在同一边的点都有连边。

$K_{5}$ 是具有 $5$ 个顶点的完全图。

对偶图

每一个平面图都有相应的对偶图，平面图的对偶图的对偶图就是它自己。

对偶图是将某个平面图的所有面看做点，然后若某两个面中有边隔开，那么这两个面在对偶图中所对应的点就有连边。

容易证明，平面图的对偶图也是平面图。

性质

设这个平面图具有 $n$ 个点，$m$ 条边，$r$ 个面（包括最外面的那个面），那么有欧拉公式：$n+r=m-2$。

证明可以用对偶图的形式来证明，即均找一棵最小生成树，然后就可以显然得证了。

并且如果某个含有 $n$ 个节点的平面图，边数最大是 $3m-6$，这个在缩小数据范围规模的时候很有效果。

判断

若两个图 $G_1$ 与 $G_2$ 同构，或通过反复插入或消去 2 度顶点后是同构的，则称二者是同胚的。

库拉图斯基定理：

  • 图 $G$ 是平面图当且仅当 $G$ 不含与 K_5 或 K_{3,3} 同胚的子图。

此处不做详解。

应用

如果平面图的每条边都有边权，并且有源点和汇点，那么我们可以将最大流（最小割）转化为最短路进行求解。

具体例子如下，如下图（左）是一个平面图，但是有源点和汇点，每条边还有不同方向的边权：

设原图的源点为 $1$，汇点为 $6$，那么我们先连接 $1$ 和 $6$，方便处理，然后对于新的平面图构建对偶图，图的边权是隔开两个面的边权，然后 $S$ 就是 $1 \sim 6$ 围出来的平面所代表的点，$T$ 就是最外层一个大平面。

我们可以清楚地看到，任何一条从 $S$ 到 $T$ 的路径都对应了原图的一组最小割的方案，于是我们直接从 $S$ 到 $T$ 跑最短路即可。

下面的代码把 $1$ 到 $6$ 新加的边是翻到了上面的，$S$ 也在上面，所以可能会有所不同。

特别地，如果是有向图，我们需要像网络流那样建立两条边，每条边的权值不一样，而题目中的图通常是网格图的形式，我们可以以 P2046 [NOI2010] 海拔 为例，考虑建边，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include<bits/stdc++.h>
#define ll long long
#define N 2000005
#define K 1005
using namespace std;
struct node{
	ll id,x;
	bool operator<(const node& a)const{
		return a.x<x;
	}
};
ll n,m,i,j,id[K][K],id2[K][K],s,t=1,x,la[N],ne[N],to[N],val[N],tot,dis[N],a[K][K],b[K][K],c[K][K],d[K][K];
priority_queue<node> q;
inline void merge(ll x,ll y,ll z,ll z2){
	tot++,ne[tot] = la[x],la[x] = tot,to[tot] = y,val[tot] = z;
	tot++,ne[tot] = la[y],la[y] = tot,to[tot] = x,val[tot] = z2;
}
void dijkstra(){
	for(ll i=s;i<=t;i++) dis[i]=0x3f3f3f3f3f3f3f3f;
	dis[s]=0;
	q.push((node){s,0});
	while(q.size()){
		node tmp = q.top();
		q.pop();
		if(dis[tmp.id]!=tmp.x) continue;
		for(ll i=la[tmp.id];i;i=ne[i]){
			if(dis[to[i]]>tmp.x+val[i]){
				dis[to[i]] = tmp.x+val[i];
				q.push((node){to[i],dis[to[i]]});
			}
		}
	}
	cout<<dis[t]<<endl;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	n++,m=n;
	for(i=1;i<n;i++) for(j=1;j<m;j++) id[i][j]=t++;
	for(j=0;j<n;j++) for(i=1;i<m;i++) cin>>a[j][i];
	for(i=1;i<n;i++) for(j=0;j<m;j++) cin>>b[i][j];
	for(j=0;j<n;j++) for(i=1;i<m;i++) cin>>c[j][i];
	for(i=1;i<n;i++) for(j=0;j<m;j++) cin>>d[i][j];
   //注意，从 s 连出去的边边权都是顺着的（ab数组），连向 s 的边边权都是 0；t 亦是如此。
   
   //但是从上连向下的边边权就是 a，反过来边权就是 c，可以理解为不变。（ac 是从左到右，从右到左的数组）
   
   //但是从左连向右的边边权就是 d，反过来边权就是 b，可以理解为反向。（bd 是从上到下，从下到上的数组）
	for(i=0;i<n;i++){
		for(j=1;j<m;j++){
			if(i==0) merge(s,id[i+1][j],a[i][j],0);
			else if(i==n-1) merge(id[i][j],t,a[i][j],0);
			else merge(id[i][j],id[i+1][j],a[i][j],c[i][j]);
		}
	}
	for(i=1;i<n;i++){
		for(j=0;j<m;j++){
			if(j==0) merge(id[i][j+1],t,b[i][j],0);
			else if(j==m-1) merge(s,id[i][j],b[i][j],0);
			else merge(id[i][j],id[i][j+1],d[i][j],b[i][j]);
		}
	}
	dijkstra();
	return 0;
}
/*
Input:
1
1
2
3
4
5
6
7
8

Output:
3

2
10 6 7 2 1 6
8 9 4 5 10 7
1 6 1 8 6 4
3 1 9 9 2 5
*/

特别地，如果是一般的平面图需要让我们找到对偶图的话，我们可能需要用到最小左转法，这个知识点的内容太过高深，不在我们的讨论范围内。