图论算法

计算机科学术语

图论算法是在计算机科学中占据重要地位的一类算法，它提供了一种简单而系统的建模方式，用于解决多种问题。许多实际问题可以通过转化为图论问题，再运用图论的基本算法来求解。

题目

一、求出这个图的补图　（1）输入无向图的各边所关联的顶点对，确定每个顶点度，以及图的最大度数和最小度数，求出这个图的补图。

（2）输入有向图的各边所关联的顶点对，确定每个顶点的出度和入度。

二、　编写一个程序，要求于无向图和有向图都能做到：输入图的邻接矩阵和正整数n，求长度为n的链和圈。

三、模拟判断一个程序中是否存在递归的函数，若存在，如何消除递归。

四、输入图的边，确定这是否为连通图。

（1）若不是连通图，则确定连通分图的个数；

（2）若是连通图，判断是否存在割边和割点，若存在各是什么？

五、输入一个多重图各边关联的顶点对。

（1）判断它是否存在欧拉圈，若存在，则求出一个欧拉圈；

（2）若不存在，则判断是否存在一个欧拉链，若存在则求之。

六、输入一个简单图的边列表。

（1）确定是否存在哈密尔顿圈，若存在求该哈密尔顿圈；

（2）若不存在，判断是否存在哈密尔顿链，若存在则求之。

七、自选一个算法求货郎担问题。

八、给定带权连通简单图的边及权列表，输入图中两个顶点，求两点是否可达？若可达距离为多少？并输出这条最短的链。

提示：

可以使用Dijkstra算法——迪杰斯特拉算法

九、给定无向图的边列表，对该图进行着色，求着色数。

十、输入一个加权无向简单图的边及权列表，求最小生成树，以及这棵最小生成树的权。

十一、输入一段文章，全部用小写字母，求各字母的哈夫曼编码。

十二、要给n个人分配m个资源，输入每个人可以获得的资源情况，求最大匹配，

要求所有资源在满足尽可能多的人获得的情况下，全部分配出去。

论证

论题

有向无回路图又称为dag。对这种有向无回路图的拓扑排序的结果为该图所有顶点的一个线性序列，满足如果G包含(u,v)，则在序列中u出现在v之前（如果图是有回路的就不可能存在这样的线性序列）。一个图的拓扑排序可以看成是图的所有顶点沿水平线排成的一个序列，使得所有的有向边均从左指向右。因此，拓扑排序不同于通常意义上对于线性表的排序。

有向无回路图经常用于说明事件发生的先后次序，图1给出一个实例说明早晨穿衣的过程。必须先穿某一衣物才能再穿其他衣物（如先穿袜子后穿鞋），也有一些衣物可以按任意次序穿戴（如袜子和短裤）。

图1中说明经拓扑排序的结点以与其完成时刻相反的顺序出现。因为深度优先搜索的运行时间为θ(V+E)，每一个v中结点插入链表需占用的时间为θ(1)，因此进行拓扑排序的运行时间θ(V+E)。

为了证明算法的正确性，我们运用了下面有关有向无回路图的重要引理。

引理1

有向图G无回路当且仅当对G进行深度优先搜索没有得到反向边。

证明：→：假设有一条反向边(u,v)，那么在深度优先森林中结点v必为结点u的祖先，因此G中从v到u必存在一通路，这一通路和边(u,v)构成一个回路。

←：假设G中包含一回路C，我们证明对G的深度优先搜索将产生一条反向边。设v是回路C中第一个被发现的结点且边(u,v)是C中的优先边，在时刻d[v]从v到u存在一条由白色结点组成的通路，根据白色路径定理可知在深度优先森林中结点u必是结点v的后裔，因而(u,v)是一条反向边。（证毕）

定理1

Topological_Sort(G)算法可产生有向无回路图G的拓扑排序

证明

假设对一已知有问无回路图G=(V,E)运行过程DFS以确定其结点的完成时刻。那么只要证明对任一对不同结点u,v∈V，若G中存在一条从u到v的有向边，则f[v]即可。考虑过程DFS(G)所探寻的任何边(U,V)，当探寻到该边时，结点V不可能为灰色，否则V将成为U的祖先，(U,V)将是一条反向边，和引理1矛盾。

因此，v必定是白色或黑色结点。若v是白色，它就成为u的后裔，因此f[v]

教材

我想很多学习图论的人都知道J.A. Bondy和U.S.R. Murty著的《Graph Theory with Application》(Elsevier,1976)是图论教材中的经典，时至今日，仍不失为初学者较好的入门书。还记得兰州交通大学的张忠辅教授说过，国内第一届图论学会就是把大家集中起来学习邦迪的《Graph Theory with Application》，由此可见这本书对国内图论届的影响是如此之大。吴望名等人将其译成中文版本《图论及其应用》（北京：科学出版社，1984），1988年张克民等人编写了该书的参考答案《图论及其应用习题解答》（清华大学出版社，1988）。

在2008年J.A. Bondy和U.S.R. Murty出了新书《Graph Theory》(GTM 244, Springer, 2008), 大家可不妨将其看成是《Graph Theory with Application》的第二版，这本书在内容上做了重新调整，毕竟在第一版出版后的近30年里涌现出了很多新的结果，所以《Graph Theory》在内容上加进了一些新的结果，这本书我只是读了其中的几章，觉得写的非常棒，建议大家能够读读，这里也值得一提的是将第一版最后提出的50个问题进行了更新，并补充了一些新的问题。总之，我个人认为，《Graph Theory》的确是一部很优秀的图论教材。

中国科学技术大学出版社出版的《图论及其算法》，融有向图和无向图为一整体，系统地阐述了图论的基本概念、理论、方法及其算法，内容包括图的基本概念、Euler图与Hamilton图、图论算法、树及其应用、平面图、独立集与匹配、网络流和Petri网。书中附有大量例题和习题，而且大部分习题有详细解答。该书选材精炼全面，内容处理恰当且有新意，立论严谨，叙述条理清晰，语言流畅。该书可用作高校计算机、电子、信息、管理、数学等专业本科生必修课教材，也可供相关专业的研究人员、教师及图论工作者参考。

实际应用

图论算法是我们经常用来求解实际问题的一种方法，在数学建模的求解过程中也经常应用

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省