当前位置:首页 >> 信息与通信 >>

浅谈图论(清华大学 黄天)


浅谈图论
清华大学贵系 黄天

图论的前世今生
图论〔Graph Theory〕是数学的一个分支,是应用数学的一部分。 它以图为研究对象,研究顶点和边组成的图形的数学理论和方法 。提出者 为欧拉(Euler) 。

图论起源于一个非常经典的问题——柯尼斯堡(Konigsber)问题, 也就是我们熟知的七桥问题。

/>后来此问题被远古大神欧拉解决,从此图论迅速发展起来。在图论的 历史中,还出现了许多经典问题,比如四色定理、汉密尔顿回路。 图论发展到我们现在,已经拥有一个很庞大的体系。图论成为了信息 学的一大专题,也成为不少Oier头疼的难题,当然!也是大神们虐场的必 备题(其实,大神们写个A+B也可以虐你>_<)。

图论在竞赛中的应用
年份 2011 2012 2013 2014 2015

题数

0

1

2

2

2

哈哈,图论出现的概率竟然与大模拟是相当的!

于是,精通找规律的我们发现今年会出2~3题!
PS:如果不是,不要打我>_<

竞赛中图论问题的难度
年份 2011 2012 2013 出现的位置 Day2 T3 Day1 T3、Day2 T3

2014 2015

Day1 T2、Day2 T2 Day1 T2、Day2 T3

所以说,图论经常会是压轴题的存在。一道图论题会直接导致省一和省 二的区别。 虽然大神可能会说打不打return 0才是我能否AK的关键。。。。

好的,我们现在步入正题。
学习图论的预备知识(大神们可以无视我开始刷题了): 00、认识图 01、能画图 10、能记图

00、认识图
什么是图?

图由点和边组成。根据边是否有方向,可分为有向图、无向图。树是 特殊的无向图。 图可以用二元组(V,E)表示,V表示点的集合,E表示边的集合。每条边 可以有一个边权。

01、能画图

由于我们这些蒟蒻没有vfleaking的秉 异天赋,我们只学习这样的画图: 比如说,给出这样的边: 起点 终点 边权

1
2 3 来自大触vfleaking的著名画作 2 4 3

2
3 1 4 5 5

1
2 1 3 4 2

1 4

4
5 2

3 2
2 3

1 1

10、能记图
记图的常用方法: (00)邻接矩阵 (01)邻接链表 (10)边集 (11)对于树来说,还有记录父亲节点、左儿子右兄弟的 方法。

(00)邻接矩阵
1 2 3 1 3

0
2 3 4

2
5

0

1 3

2

3 2

4

5

1 2 3 4 5

4
2 3 3 1

5
1 2

其中空着的位置代表该两点之间没有边。 设G[][]为某一幅图的邻接矩阵,那么对于这样的一条边,点i->点j有一条 权值为w的边,那么就令G[i][j]=w 对于无向图来说,i-j这样的一条边就令G[i][j]=G[j][i]=w

(00)邻接矩阵
void Build() { for (int i=0; i<M; i++) { int u,v,w; scanf("%d%d%d",&u,&v,&w); G[u][v]=w; //如果是无向图,则是G[u][v]=G[v][u]=w; } } 空间复杂度:O(N^2)

(01)邻接链表
原理:用链表把边存起来,直观上我们要用指针来写,但是我们可以用数组模拟指针。

Vector?

(01)邻接链表
void Insert(int u,int v,int w) { cnt++; //注意:在多组数据的时候,cnt和Root一定要初始化,不然很容易错。 Node[cnt]=v; Cost[cnt]=w; Next[cnt]=Root[u]; Root[u]=cnt; } void Build() { for (int i=0; i<M; i++)

空间复杂度O(M)

{
int u,v,w; scanf("%d%d%d",&u,&v,&w); Insert(u,v,w); //如果是无向图,再加一句Insert(v,u,w),记得数组翻倍!!!

}
}

(01)邻接链表
搜索边的时候,对于当前点Now,只需要这样写: for (int x=Root[Now]; x!=0; x=Next[x]) Node[x]就是Now连出去的点。 这样就能扫描完所有与Now相关的边。

(10)边集
这个其实不算是什么特别的存储方法,只是单纯的把每条 边的起点、终点、边权记录下来,有时会有特殊的作用。比如, 在最小生成树kruskal算法、最短路径Bellman-Ford算法中的应 用。

(11)树的特殊存储方法
a)记录父亲节点 这个就不用讲了吧,每个节点都记录其父亲节点,常用于 比较简单的树的遍历。

(11)树的特殊存储方法
b)左儿子右兄弟 把一棵多叉树转化为一棵二叉树,便于处理。转化的方式 是:左子树为孩子节点,右子树为兄弟结点。也就是说:

(11)树的特殊存储方法
b)左儿子右兄弟 具体实现: 要开三个数组:节点数组v(也可不开,用下标代替),左 节点数组left,右节点数组right。每次读入一组父亲节点和孩 子节点,如果把它放在后面,那么当多个的时候就还要在前面 再扫描一次,时间复杂度就是O(n^2)。但是可以直接把当前的 这一个孩子节点插在最前面,时间复杂度会降低到O(n)。

(11)树的特殊存储方法
b)左儿子右兄弟 具体实现: scanf("%d%d",&father,&son); if (left[father]!=0) { right[son]=left[father]; left[father]=son; } else left[father]=son;

不过其实就我个人来讲,我觉 得这种方法并没有特别方便的 地方,一般可以用邻接链表来 代替。

图论中的常见算法
图的遍历 最短路径 最小生成树

强连通分量

树的一些处理

图的遍历
a)广度遍历 b)深度遍历 c)DAG的拓扑排序

DAG的拓扑排序
对一个有向无环图(DAG)G进 行拓扑排序,是将G中所有顶点排 成一个线性序列,使得图中任意一 对顶点u和v,若边(u,v)∈E(G),则 u在线性序列中出现在v之前。

具体的实现: 1、每次找到入度为0的点,将其加 入已排好序的队列队尾。 2、将当前入度为0的点以及它所连 出去的边都在图中删掉。 3、重复1、2步直至图为空。

DAG的拓扑排序

那是不是每次都要将所有点扫描一 遍看看哪些是入度为0的点呢?这样 一来时间复杂度可是平方级别的呀!

DAG的拓扑排序
当然不用! 用一个数组记录每个点初始状态下 的入度。 在初始的时候将入度为0的点加入宽 度搜索的队列中。 在宽搜的时候,对于当前点,将其 出边对应的所有点的入度都减一, 然后顺便判断一下入度是否变成了0, 如果是,就将该点加入队尾。

DAG的拓扑排序

int tail=0; for (int i=1; i<=N; i++) if (ru[i]==0) { tail++; que[tail]=i; } for (int head=1; head<=tail; head++) for (int x=Root[que[head]]; x!=0; x=Next[x]) { ru[Node[x]]--; if (ru[Node[x]]==0) { tail++; que[tail]=Node[x]; } }

poj2367
给出一个数n, 然后n行,编号1到n, 每行输入几个数,该行的编号排 在这几个数前面,输出一种符合要求的编号名次排序。 5 0 4510 10 530 30 1

5
2

3

4

最短路径

最短路径
BFS
Bellman-ford SPFA Dijkstra

Floyd
还有Johnson、A*算法,但是这些不那么常用,而且时间有 限,这里不多讲。

BFS灌水法
usaco火情蔓延 一个R*C的方格图,时刻0时某些方格自燃,每秒钟向四个方向蔓延,问 需要多少时间才使得整个方格图都在燃烧。 拯救公主 http://bailian.openjudge.cn/practice/4105/ http://blog.csdn.net/a948433271/article/details/47073971 2 使用条件:边权为1 2 1 2 2 1 0 1 2

2 1 2 2

BFS灌水法

2 2 1 2

int BFS(int s,int t) { 2 1 0 1 2 memset(vis,false,sizeof(vis)); 2 1 2 memset(dis,0,sizeof(dis)); int tail=1; 2 que[tail]=s; vis[s]=true; for (int head=1; head<=tail; head++) for (int x=Root[que[head]]; x!=0; x=Next[x]) if (!vis[Node[x]]) { tail++; que[tail]=Node[x]; dis[Node[x]]=dis[que[head]]+1; vis[Node[x]]=true; } return dis[t]; }

Bellman Ford
基本思路: 1、对于没一条边都松弛一遍。 2、重复以上操作N-1(点的个数)遍。 若在n-1次松弛后还能更新,则说明图中有负 环,因此无法得出结果,否则就完成。

int BellmanFord(int s,int t) { for (int i=1; i<=N; i++) dis[i]=oo; dis[s]=0; for (int i=1; i<N; i++) for (int j=1; j<=M; j++) if (dis[From[j]]+Cost[j]<dis[Endv[j]]) dis[Endv[j]]=dis[From[j]]+Cost[j]; }

Bellman Ford

SPFA
改进自Bellman Ford
用队列来进行优化 多次入队,多次松弛

O(km)?

SPFA int SPFA(int s,int t)
{

memset(inq,false,sizeof(inq)); for (int i=1; i<=N; i++) dis[i]=oo; inq[s]=true; int tail=1; que[tail]=s; dis[s]=0; for (int head=1; head<=tail; head++) { for (int x=Root[que[head]]; x!=0; x=Next[x]) if (dis[que[head]]+Cost[x]<dis[Node[x]]) { dis[Node[x]]=dis[que[head]]+Cost[x]; if (!inq[Node[x]]) { que[++tail]=Node[x]; inq[Node[x]]=true; } } inq[que[head]]=false; } return dis[t];

两个优化策略: a)如果dis[tail_N]<dis[head_N], 插到队首。 b)设当前dis的平均值为x,若当前 dis[head_N]大于x,将其弄到队尾, 继续看新的dis[head_N],直至找到 一个dis[head_N]<=x,才开始松弛。

Djikstra
具体实现: 每次选队列中距离最小的顶点进行松弛。 正确性?
使用条件:边权为正(?)
1
4 5

时间复杂度O(N^2),优化之后可以达到O(MlogN), 写得弱会达到O(MlogM)。 3

2

-2

Djikstra
int Dijkstra(int s,int t) { for (int i=1; i<=N; i++) dis[i]=oo; dis[s]=0; memset(vis,false,sizeof(vis)); for (int i=1; i<=N; i++) { int Min=oo, k=0; for (int j=1; j<=N; j++) if ((dis[j]<Min) && (!vis[j])) { Min=dis[j]; k=j; } if (Min==oo) break; vis[k]=true; for (int x=Root[k]; x!=0; x=Next[x]) if ((Min+Cost[x]<dis[Node[x]]) && (!vis[Node[x]])) dis[Node[x]]=Min+Cost[x]; } return dis[t]; }

Floyed
? 动态规划思想 ? 以路径中除两端点外编号最大的顶点 作为阶段来划分 ? f[k][i][j] ? 优化空间后f[i][j] ? 时间复杂度O(N^3)

for (int k = 1; k <=n; ++k) for (int i = 1; i <= n; ++i) for (int j = 1; j <= n; ++j) if ((k!=i) && (k!=j) && (i!=j)) F[i][j] = min(F[i][j], F[i][k]+F[k][j])

习题
http://poj.org/problem?id=1860 http://poj.org/problem?id=3259 http://poj.org/problem?id=1062 http://poj.org/problem?id=2253

http://poj.org/problem?id=1125

最小生成树(MST)

MST重要性质
设G=(V,E),U是V的一个真子集,若(u,v)是G中所有的一个端点在U(u∈U)里、 另一个端点不在U(即v∈V-U)里的边中,具有最小权值的一条边,则一定存在G 的一棵最小生成树包括此边(u,v)

证明?

Prim
具体实现: 每次选队列中当前边边权最小的顶点进行松弛。时间复杂 度O(n^2),优化后O(mlogn)
使用条件:边权为正

Kruskal
具体实现: 按边权从小到大枚举边e=(u,v) 若u和v尚未连通,添加当前边。 直到形成一棵树。

习题
http://poj.org/problem?id=1789 http://poj.org/problem?id=2485 http://poj.org/problem?id=1258 http://poj.org/problem?id=3026

Tarjan算法

一些应用
? 在一个连通图G中,有些点一旦被去除就会导致图不连通,同样的,有些边 一旦被去除也会导致图G失去连通性,那么如何求出这些点和边就是一个需 要被解决的问题。 ? 一般的有向图都不是DAG

? 但可以找出所有强连通分量,缩点后的图为DAG

一些概念
? 无向图中

? 桥(割边)、割点(顶)、双连通分量(点、边)
? 有向图中 ? (极大)强连通分量 ? 树边、非树边

Tarjan算法
? 定义dfn、low两个一维数组。用dfn[i]记录编号为i的点 的遍历序号,即第几个被遍历到的,用low[i]记录编号 为i的点在接下来的遍历中可以访问到的最小序号。


由分析得知,对于通过树边e遍历出的点u,如果在接 下来的遍历中u无法访问到序号比u更小的点,即dfn[u]等 于low[u],那么e就为桥。而根据low值的定义又可以知道u 的low值可以由与u有边相连的点的low值计算出来。

割点
割点的求法其实与桥的类似。 如果点u是割点,那么一定存在一个u的儿子v,low[v]是不小于dfn[u]的。 不过割点有比较多细节处理: 00、如果u为深度优先遍历的根节点,那么只有当它有至少2个儿子v1、v2 同时满足它们的low值不小于u的dfn值时结论才成立。 01、在第00点中,v1、v2必须是u的儿子,即必须是由u通过树边遍历出的 点。如右图,若v2和u有边相连但不是u的儿子,则v2必然在以v1为根的子 树中,此时u只是图“边缘”上的一个点,删除u后v1、v2仍然连通,在图 的连通性方面v1、v2也是等价的,所以应不对v2进行考虑。 10、low[v]==dfn[u]的情况

强连通分量
在深度优先遍历的过程中,每次新遍历到一个点,就将该点压入栈中。 当以某点u为根的子树遍历完之后,u的low值仍等于u的dfn值,则说明找 到了一个新的强连通分量,此时因为强连通分量中的点均在以u为根的子树 中,即应当在栈之中,所以从栈尾点一直到u这一段点就是组成当前强连通 分量的点集。

强连通分量
1 2 5 4

3

6

7

显然1、234、567分别成为了三个强连通分量。但是深度优先遍历按照 1234567的顺序遍历时,5会因为有边指向6并接着访问到了4导致5的low值 等于4的dfn值,而4的dfn值是显然比5的dfn值小的,因此这样便无法在遍 历完以5为根的子树后判断出567这个强连通分量,相反的会把1567判定为一 个强连通分量。 对567进行遍历时其实234已经被作为一个强连通分量剔除了,不再将对图的 其他部分进行影响,所以在更新low值的时候不应该考虑已经被划分到某强 连通分量中的点,即只考虑仍在栈中的点。

双连通分量
双连通分量其实与强连通分量没有多大的不同。 一、边双连通分量: 不存在割边的双连通分量,将原图删去割边得到多个边双连通分量 算法是Tarjan中点入栈的算法 二、点双连通分量: 每个点双连通分量没有关节点, 同时原图的关节点可以存在于多个点双连通分量中 算法是Tarjan中边入栈的算法 一般无向图把所有双连通分量缩成一个点之后变成了什么?

习题
? poj2186

? 有N(N<=10000)头牛,每头牛都想成为most popular的牛,给出 M(M<=50000)个关系,如(1,2)代表1欢迎2,关系可以传递,但是不可以 相互,即1欢迎2不代表2欢迎1,但是如果2也欢迎3那么1也欢迎3. ? 给出N,M和M个欢迎关系,求被所有牛都欢迎的牛的数量。

Some Tips
? 由于tarjan算法的时间复杂度非常可观,所以经常数据范围会比较大,直接 写递归会爆栈,所以要写非!递!归!╮(╯▽╰)╭(所以说为什么标程都是用 递归写的(→_→)) ? 无向图的重边情况

? 考虑原图的连通性。原图很可能本身就是不连通的,这时候任何一个点都 将成为割顶,任何一条边都会成为桥。
? 在求无向图的割顶时,对于u由非树边访问到的已经遍历过的点v,不能错 用v的low值更新u的low值,因为可能v就是割顶,一旦v被删除u就无法通 过v访问到low值比v的dfn值更低的点,所以只能用v的dfn值来更新u的low 值。

习题
http://poj.org/problem?id=2186 http://poj.org/problem?id=3352

树上的一些操作

倍增算法
具体应用:求树上任意两点的lca(这 个问题其实还有很多解法)。 lca:最近公共祖先

具体实现: 先对于树的每个节点按照DFS序进行编号,然后用RMQ的方法, 做好树上的st表,每次询问的时候就可以将时间复杂度控制在 O(logN)。

st表
for (int i=1; i<=N; i++) F[i][0]=Fa[i]; for (int i=1; i<=P; i++) //P为令2^P大于 N的最小整数 for (int j=1; j<=N; j++) F[j][i]=F[F[j][i-1]][i-1];

询问
int Query(int x,int y) { if (id[x]<id[y]) swap(x,y); for (int i=P; i>=0; i--) if (id[F[x][i]]>id[y]) x=F[x][i]; return F[x][0]; }

习题
http://poj.org/problem?id=1330

Some Other Problems:
a)求树的直径 很多种方法。 b)树的最小表示法 树同构? c)*树链剖分 d)差分约束系统 e)二分图匹配

一些习题
NOIP2013 Day1 T3:

A 国有 n 座城市,编号从 1 到 n,城市之间有 m 条双 向道路。每一条道路对车辆都有 重量限制,简称限重。现 在有 q 辆货车在运输货物,司机们想知道每辆车在不超过 车辆限重的情况下,最多能运多重的货物。 0 < n <10,000,0 < m < 50,000 暴力怎么过?MST?倍增?

一些习题
NOIP2012 Day2 T3:
H国有n个城市,这n个城市用n-1条双向道路相互连通构成一棵树,1号城市是首都,也是 树中的根节点。H国的首都爆发了一种危害性极高的传染病。当局为了控制疫情,不让疫情扩 散到边境城市(叶子节点所表示的城市),决定动用军队在一些城市建立检查点,使得从首都 到边境城市的每一条路径上都至少有一个检查点,边境城市也可以建立检查点。但特别要注意 的是,首都是不能建立检查点的。 现在,在H国的一些城市中已经驻扎有军队,且一个城市可以驻扎多个军队。一支军队可 以在有道路连接的城市间移动,并在除首都以外的任意一个城市建立检查点,且只能在一个城 市建立检查点。一支军队经过一条道路从一个城市移动到另一个城市所需要的时间等于道路的 长度(单位:小时)。 请问最少需要多少个小时才能控制疫情。注意:不同的军队可以同时移动。 2≤m≤n≤50,000

一些习题
NOIP2013 Day2 T3:
小 B 最近迷上了华容道,可是他总是要花很长的时间才能完成一次。于是,他想到用编程 来完成华容道:给定一种局面,华容道是否根本就无法完成,如果能完成,最少需要多少时间。 小 B 玩的华容道与经典的华容道游戏略有不同,游戏规则是这样的: 一、在一个 n*m 棋盘上有 n*m 个格子,其中有且只有一个格子是空白的,其余 n*m-1个 格子上每个格子上有一个棋子,每个棋子的大小都是 1*1 的; 二、有些棋子是固定的,有些棋子则是可以移动的; 三、任何与空白的格子相邻(有公共的边)的格子上的棋子都可以移动到空白格子上。 游戏的目的是把某个指定位置可以活动的棋子移动到目标位置。 给定一个棋盘,游戏可以玩 q 次,当然,每次棋盘上固定的格子是不会变的,但是棋盘上 空白的格子的初始位置、指定的可移动的棋子的初始位置和目标位置却可能不同。第 i 次玩的 时候,空白的格子在第 EXi行第 EYi 列,指定的可移动棋子的初始位置为第 SXi 行第 SYi 列,目 标位置为第 TXi 行第 TYi 列。 假设小 B 每秒钟能进行一次移动棋子的操作,而其他操作的时间都可以忽略不计。请你告 诉小 B 每一次游戏所需要的最少时间,或者告诉他不可能完成游戏。 1 ≤ n, m ≤ 30,q ≤ 500

参考文献:
许若辰、屈运华 胡伯涛 黎才华 石昊悦 百度百科、wiki 总结DFN-LOW算法在图论中的应用 图论知识总结 图论专题 常见图论问题模型

Thank you!
E-mail:any3231@126.com


相关文章:
清华大学电路原理备考经验谈
清华大学电路原理备考经验谈_研究生入学考试_高等教育...网络图论(05、06、08、09、11) 8. 状态方程(05...而个人感觉,这正是数学解题能力提高最大的几十 天...
图论在实际生活中的应用
参考文献: 参考文献: [1]殷剑宏、吴亚开.图论及其算法[M].合肥:中国科学技术大学出版社,2005 [2]严蔚敏.数据结构(c 语言版)[M].北京:清华大学出版社,2009 ...
图论模型应用
计算机科学中的图论概念(WG 2010)国际会议预报 36th...大学) 范更华(福州大学) 黄靖(加拿大 Victoria 大学...清华大学、北京大学、南开大学、山东大学、厦门大学、...
算法合集之《由图论问题浅析算法优化
本资料由-大学生创业|创业|创业网 http://www.chuangyw.com/提供资料 由图论问题浅析算法优化武钢三中 贾由 【摘要】 论文以图论问题为对象、以算法优化为主题...
算法合集之《由图论问题浅析算法优化》
算法合集之《由图论问题浅析算法优化》_数学_自然科学_专业资料。【摘要】 论文...是后向边两端点之间的最短路径长度,我们需 径 6 2 2 1 浙江大学在线题库,...
图论思考题
图论思考题_工学_高等教育_教育专区。图论思考题图论思考题 1. 今有 a, b, c, d, e, f, g 7 人,其中 a 会讲英语; b 会讲英语和汉语; c 会讲英...
信息管理与信息系统专业主要课程
问题,是学习计算机专业理论的重要数学工具,主要内容为数理逻辑、集合论和 图论。...推荐教材: 《计算机网络工程教程》 ,黄叔武、杨一平主编,清华大学出版社, 2004...
数学与应用数学毕业论文题目
年全国高教杯大学生数学建模竞赛题的探究与拓展 关于 2 循环矩阵的特征值 关于...的应用浅析 图论在高中数学中的若干应用 图论在数学模型中的应用 图论在中学数学...
数模竞赛能力要求
图论、数论等 如: 图论算法(包括最短路、网络流、...清华大学出版社 《数据结构》清华大学出版社 《算法...《论文 2004》 经验: 1、赛后我们用了 3 天加一...
(张正仓)浅谈如何有效运用历史地图提高课堂实效性
(张正仓)浅谈如何有效运用历史地图提高课堂实效性_初三政史地_政史地_初中教育...读图,不仅 要仔细观察图面上的所有信息点,更要注意图与教材的联系,切忌就图论...
更多相关标签:
图论及其应用 张清华 | 电子科技大学图论答案 | 电子科技大学图论作业 | 北京师范大学 图论 | 湘潭大学图论考试 | 中山大学图论考试 | 东北大学 图论 习题 | 浅谈大学生创业 |