算法基础08图论下集

‘壹’ 简介图论算法

图论101

图论是数学的一个非常广泛的分支，非常适用于现实世界中的问题。 最初，图论是"发明"来解决现实问题的，此后，它像所有其他数学分支一样，被抽象数学家所劫持。

在本教程和后续教程中，我们将介绍一些图论算法及其在python中的实现。 现在，回到主题。

简而言之，图是一组顶点/节点和边。 如果您对" set"不满意，请用collection代替。

在上图中，顶点/节点将是人物。

顶点是图的基本单位。 它几乎可以代表任何实体，通常以圆圈表示。

在上图中，连接人的线是边。

顶点之间的线或连接称为边。 它可以表示顶点之间的任何类型的关系。

边上具有方向的图称为有向图。 它可以用来显示与前辈（从父母到孩子的箭头）或祖先（从孩子到父母的箭头）的关系。

边上没有方向的边的图称为无向图。 它可用于显示双向道路。

边上带有数字的图形，代表交易成本，旅途公平，城市之间的距离等。它可以具有任何类型的边。

没有循环的无向图是一棵树。 在这里，循环意味着只有一种方法可以通过跟随给定其他节点的边缘来到达节点。

一棵树的所有节点都通过一条边连接到其他某个节点，并且有N个节点的N-1个边。

表示图形的方法有很多，最常见的两种是：

假设图中有N个节点。 我们可以使用具有N行和N列的矩阵来表示它，其中该矩阵的行和列将代表一个节点，并且其中的条目代表有向边（有或没有权重）。

它们形成代表行的节点到代表列的节点。 通常，0或无穷大用于表示节点之间没有边缘。 在Python中，邻接矩阵可以表示为：

类似地，对于N个节点的图，我们可以使用邻接表来表示该图，其中节点的所有边都保留在元组列表（节点，权重）中。 在python中，它可以表示为：

我使用嵌套字典（这就是我所说的）和带集合的字典（如果节点没有权重的边）来表示图。

在下一篇文章中，我将使用不同的方法发布精心设计的图类的Python代码，我们将使用该代码来实现图算法。

(本文翻译自sleepingFish的文章《Graph Theory Algorithms "Simplified"》，参考：https://medium.com/better-programming/graph-theory-algorithms-simplified-9a6868cc222)

‘贰’ 图论基础-1.查找所有路径

工作中某块需求涉及到查找两点之间全部路径的需求，尝试利用图的算法来解决这一问题。
目标：找出途中从开始到结束节点中间的所有路径

图是网络结构的抽象模型。图是一组由边连接的节点（或顶点），任何二元关系都可以用图来表示。
一个图G=(V, E)由以下兀素组成：

由一条边连接在一起的顶点称为相邻顶点 比如，A和B是相邻的
一个顶点的度是其相邻顶点的数量 比如，A和其他三个顶点相连接，因此，A的度为3
路径是顶点v1, v2, ...vk的一个连续序列 以上图为例， 其中包含路径A B E I 和 A C D G。

用例：

1.邻接矩阵：（Adjacency Matrix）适用于稠密图（完全图）

2.邻接表（Adjacency Lists）适用于稀疏图

和树数据结构类似，我们可以访问图的所有节点。有两种算法可以对图进行遍历：

1.将图抽象成用例

2生成邻接矩阵

3获取所有路径

参考文档：
https://juejin.im/post/5de7c053518825125d1497e2
https://juejin.im/post/5a32688b5188254dd9366d6a
不使用递归的生成路径方法： https://juejin.im/entry/5d849fb45188255a8b635058

‘叁’ 图论算法的介绍

图论算法在计算机科学中扮演着很重要的角色，它提供了对很多问题都有效的一种简单而系统的建模方式。很多问题都可以转化为图论问题，然后用图论的基本算法加以解决。遗传算法是解优化问题的有效算法，而并行遗传算法是遗传算法研究中的一个重要方向，受到了研究人员的高度重视。

‘肆’ 图算法(一): 图的概念基本表示

图并不是现实世界中的一幅画, 例如

在计算机中, 图是一种数据结构. 图是计算机科学的一个概念, 在数学中也有对应的数学分之: 图论.

计算机中的图如果表示出来大概长成这样

可以把上图想象成一个社交网络, 网络中的每个圆表示一个User, User存在某种关系.

或者看作是一个城市群, 每个圆表示一个城市, 城市之间通过道路联通.

直观的从图片上看 有3个组成部分:

更一般的叫法是:

有了这些概念, 在理解的基础上就可以对图做一个稍微正式点的定义了

上图中的图叫做简单图, 那什么样的图不叫简单图呢? 如下所示

在顶点0, 存在一个边, 这种边称之为 自环边(self-loop)
在顶点0和1之间, 除了之前那张图片上的一条边之外, 又多了一条边, 多出来的这条边称之为 平行边(parallel)

因此, 拥有自环边或平行边的图不是简单图.

上面给出的图的示例属于最简单的 无向无权图 .

因为图的边可以附加一些信息(权), 以及边是可以有方向的, 因此图有两个大类:

进一步的组合可以分为:

不同种类的图有不同的作用, 在开始学习图算法的时候, 应先从最简单的无权无向图开始.

通过图片可以很清楚的知道图的形状, 那么如何转换到计算机中表示呢?
对于这个问题, 有两种方式:

这两种方式各有优缺点, 具体选择哪一种需要看场景

‘伍’ 图论割集问题

回答楼主,图论大多问题的解决,需要用到遍历算法,判断割集我想不会有其它算法,遍历的算法目前是图论中最基本最重要的算法,当然对一些特殊的图可能会有其它方法.遍历算法的计算复杂度不是很大的,是多项式算法,在计算机上可以实现.当然在选取边和点时应考虑技巧性,这恐怕是个难题,否则会出现组合爆炸,就象货郎担问题一样,比如选择点可以首先考虑选取度数最大的点,选取边一定要选不在回路上的边.这需要你的智慧.
割集分为点割集和边割集,对一个图G=(V,E)来说如果存在一个结点集V的子集,从G中删除这些结点后,它的连通分图的个数增多,则称该子集为点割集,对一个连通图来说,删除这些结点后,连通图变为不连通.点割集一般不是唯一的,含有最小结点个数的点割集称为最小点割集,类似可定义边割集和最小边割集,仅含1个点的点割集称为割点,仅含1个边的边割集称为割边,割边也称为桥.
求一个连通简单图的割集的算法,我想可用遍历的算法,目前常用的是深度优先搜索或者广度优先搜索算法来做,这是图论中最基本的算法,这种算法可求出图的连通分图的个数,以此来判断某子集是否是割集.

‘陆’ 算法基础

谨以此文，感谢我在这个学校最喜欢的两个老师之一——肖my老师。本文基本为老师上课说讲授内容加上一部分自己的感悟拼凑而来，写作文本的目的是为自己的算法课程留下一点点东西，站在老师肩膀上形成粗糙的框架，方便以后的复习以及深入。文笔有限，其中包含的错误还请多多包容，不吝赐教。

to do list：

时间复杂度中递归树法；动规，分治新的感悟；

点覆盖：一组点的集合，使得图中所有边都至少与该集合中一个点相连。

支配集：一组点的集合，使得图中所有的点要么属于该集合，要么与该集合相连。

最大团：在一个无向图中找出点数最多的完全图。

独立集：一组点的集合，集合中的顶点两两不相邻。（团转过来）

SAT问题：也称布尔可满足性问题。给一组变

其中Ci被称为句子。

点覆盖<->独立集<->最大团

最小割：割是一组边集。如s-t割就是如果去掉这些边，将把原图划分为两个点集，其中一个点集包含s，一个点集包含t。（两个是指不相连，而不是代表不存在边相连，如反向边）

decision problem: 是否存在。

search problem:找到一个解。

（这个还能扩展，比如decision problem在多项式时间内解决，所以他是P问题吗）

渐进符号：

注意以上三种都是紧的，对应的两个小写的符号是不紧的，即如下图所示：

概念：算法的时间复杂度是一个函数，用于定性描述算法的运行时间。注意，这个一个代表算法输入字符串长度的函数。

[注]输入字符串长度是一个比较关键的理解，比如在背包问题中，其时间复杂度为O(nW)，因为W不定，所以只能是一个伪多项式时间。

比较：c < log2N < n < n * Log2N < n^2 < n^3 < 2^n < 3^n < n! < n^n

大致：常数<对数<幂函数<指数函数<阶乘

对于指数是n相关的进行比较，优先比较指数，再比较底数。

记住一个特例：n ^(logn)<n!<n n

计算：

一般来说，计算采用主方法和递归树法，其中递归树技巧性比较强，主方法其实也是递归树推导归纳而来，且主方法能得到一个比较紧的结果。

主方法：

f(n) = af(n-b)+g(n) =>O( a^(n/b) *g(n) )

P：decision problems有一个多项式算法。

NP（nondeterministic polynomial-time）：decision problems能够在多项式时间内验证。

NPC：NP完全问题，首先这个问题是NP的，其次，其他所有问题都可以多项式时间内归约到它。

NPH：如果所有NP问题都可以多项式时间归约到某个问题，则称该问题为NP困难。

因为NP困难问题未必可以在多项式时间内验证一个解的正确性（即不一定是NP问题），因此即使NP完全问题有多项式时间的解（P=NP），NP困难问题依然可能没有多项式时间的解。因此NP困难问题“至少与NP完全问题一样难”。

一些NP问题能在多项式时间内解决，因为 P∈NP

NP难类型问题的证明：

先选好一个已知NP难的问题，然后将已知NP难问题多项式归约到要证明的问题上。先给出这个归约，然后再证明这个归约的正确性。

NPC类型问题的证明：

证明一个问题Y是NPC问题，先说明Y是NP的，然后找到一个NPC问题X，将这个问题X归约到问题Y上，即证明完成。

常见的NPC问题（重要，规约的时候有用！）：

packing problems: set-packing，独立集

覆盖问题：集合覆盖问题，顶点覆盖问题

严格满足问题(constraint satisfaction problems)：SAT，3SAT

序列问题：哈密尔顿回路，旅行商问题

划分问题：3D-matching, 3着色问题

数字问题：子集合问题（子集元素之和为t），背包问题

其他：分团问题（是否存在一个规模为k的团）

规约的概念与理解

规约：意味着对问题进行转换，例如将一个未知的问题转换成我们能够解决的问题，转换的过程可能涉及到对问题的输入输出的转换。

自归约：search problem <=p decision problem

归约：A归约到B，也就是说，我们对A套一个函数f，在f函数的作用下形成一个新的问题，对这个问题运用B的黑盒解法，能够解决问题A。

(B <=p A)一般说来，B问题如果可以归约到A问题，也就是说，一个解决A问题的算法可以被用做子函数（子程序）来解决B问题，也就是说，求解B问题不会比求解A问题更困难。因此，如果B问题是困难的，那么A问题也就是困难的，因为不存在求解A问题的高效算法。(最后一句不懂)

我简单说一下我理解的规约，以X规约到Y为准，大概分成两个方面：

注：在 三 的一些实例中细品。

概念：在对问题求解时，总是做出在当前看来是最好的选择。

贪心的证明：先假设贪心算法得到的解不是最优解，假设S1是贪心算法得到的解，而S2是所有最优解中和S1具有最多相同元素的解，然后比较S1和S2，观察S1和S2中第一个（最前面一个）不一样的元素，然后在贪心解S2中将不一样的元素换成S1中的那个元素得到另一个最优解S3，这样S3和S1比S2和S1有更多相同元素，和假设S2是与S1有最多相同元素的最优解矛盾，这样来推导S1是最优解。

我的理解：假设这个不是最优的，但是一定存在一个最优的解在某一个位置之前和我当前解结构是一样的，那么在这个位置，选最优解也可以选当前解，不影响最终答案。

[注]概念很简单，但是实际操作的时候，贪心的角度很重要，同样的贪心，方向对了，算法就是对的。

例子：

给你一系列活动，每个活动有一个起始时间和一个结束时间，要求在活动不冲突的情况下找到一种有最多活动的安排。

对于这个问题，我们有一下几种贪心的角度：

①将任务按照 开始时间 升序排列。

②将任务按照 结束时间 升序排列。

③将任务按照 任务时长 升序排列。

④对于每一个任务，都记录与其他任务冲突的数量，按照 冲突数量 的升序排列。

其中1，3，4都是不可以的。

任务结束时间的贪心证明（反证法）：

假设贪心不是最最优的，那我们在最优解中找一个与当前解有最相似的解。

由图可以知道，贪心贪的就是最早结束，所以如果不是最优，那么最优的结束时间一定晚于贪心的结束时间。

由上图就可以证明。

最大流通常与最小割相联系。

f 为任意一个流，cap为容量，对于任意的s-t割出来的点集（A，B），v( f ) <= cap(A, B)。

当流增加到与割的容量相等时候，就不可能再有增长空间了，称为最大流。

对于割的容量来说，不同的割法会有不同流量，有些割法永远不会有流达到，比如部分A = {s}, B = {V - s}，这种把源点割出来的割法。

综上，通过这种感性的认识，如果能找到一个最小的割，那么这个割就一定是最大能跑到的流（如果流能更高的话在这个割上就会超过容量，反证。）

上图为一条增广路，一条增广路即为一条s-t的路径，在路径上仍有流可以跑，其曾广的流就是该条路径上最小的剩余容量。（相当于每找一条增广路，就至少有一条边达到满流。）

直到在图中找不到增广路，此时已经达到了最大流。

找ST集合：把满流的边去掉，从S出发走到能到的点，遍历的点就是S集合；剩下的点就属于T集合。注意，如果找到了在找S集合的时候找到了T点，说明还可以继续找增广路。

[补]有一个很有趣的延伸，如多源点多终点问题。问：如果我有两个源点s1，s2，两个终点t1，t2，我想求一组流，使得s1-t1，s2-t2的流达到最大，是否可以加一个源点S，S与s1，s2相连，边流无限大；加一个终点T，T与t1，t2相连，边流无限大，然后这组ST的最大流即可。——答案是No，无法保证是s1-t1，s2-t2，有可能交错。

例子讲的感觉不是特别好，对理解感觉起不到很大作用，希望以后有新的想法后进行补充。

规约是一个重要的概念和思想。

一个图的 最大独立集 与 最小点覆盖 是不相交的两个点集，它们的并就是整个点集。

个人理解：独立集和点覆盖都是从点的角度进行划分的，如果我们从边的角度来看，①一个最小的点覆盖即为我集合中的每一个点都尽可能与更多的边相连，②同时，一条边的两个端点中，只能有一个端点在最小点覆盖中[下注]

[注]我们假设有一条边两个端点（u，v）都在点覆盖之中，首先显然u，v都不是端点，因为假设u是端点的话只需要选择v即可；

给一个集合S和一堆S的子集S1，S2，...，Sm，问是否存在存在k个子集，使它们的并集为S。

构造：

集合为点，集合中的元素为边，有相同元素的边相连。（注意如果某一元素只在一个子集中出现，应该怎么处理呢！）

规约：在构造的图中找最小的点覆盖，选中的点能覆盖所有的边即为对应集合的并集能包含所有的元素。所以就完成了集合覆盖到点覆盖的规约。

构造：每个句子构造一个三角形，把对应变量但是相反取值的点相连。

规约：3SAT的有一个特点就是，每一个句子中至少有一个为真即可，每个句子都必须是真。将相同变量相反取值相连的目的就是，在最大独立集中，比如选择x为真，则剩下所有句子中x-ba一定不会被选中，同时由独立集和构造出来三角形的性质可以知道，每一个句子，有且仅有一个会被选中（为真）。如上图，x1-ba为真，x2-ba和x3任选一个为真即可满足。

search problem <=p decision version

比如：如果能在多项式时间内找到一个哈密尔顿圈，那么就能在多项式时间内找到一个哈密尔顿圈（删边）

在此再谈P和NP：

我们知道有些问题是可以从搜索问题规约到判断问题的，也就是所该问题如果能在多项式内判断，那么久能在多项式中搜索到，那么我们只需要说，这个判断问题能在多项式时间内求解，就叫做P问题，也就是上图红字的意思；那NP问题呢，必须要给出一个解的实例，判断的是这个实例是否满足求解问题，这个才是上图中的红字。比如，我如果能在多项式时间内判断哈密尔顿圈是否（Yes/No）存在，那这个就是ploy-time algorithm，如果我给出了一系列点，能过多项式时间内判断这些点能否构成哈密尔顿圈，那这个就是poly-time certifier。

构造：把一个点拆分成三个点。

构造：（下面两个图要连在一起看）

从行的角度看，一行代表一个变量；从列的角度来看，每三列代表一个句子。两边中一边是两个点，一边是一个点，所以有k个句子的话，每一行有3k+3个节点。从哈密尔顿圈的答案转到3SAT的答案看这个圈在每一行是从左到右还是从右到左。

子集和问题：给一个集合S，问是否能在集合中选取元素，使得总和为W。

构造：如下图，按照前六行和前三列进行分割，可以分成4部分，其中1,3,4部分是固定的，即在第一部分，变量v列和 变量为v（包括变量及取反）的行对应的格子为0，其余为0；第三部分全为0；第四部分按照12依次写下来。第二部分，如果Ci句子中有变量v，则记为1，因为一个句子只有三个变量，可以简单通过第二部分每一列和为3进行判定。此时集合已经构造出来，W为111444，与上面的规约相似，可以通过3SAT的简单性质进行感性的认知。

近似的想法很简单，要解决一个问题，我们希望能够做到①求解结果是最优的 ②在多项式时间内解决 ③对于任意的实例都能够通过该算法解决。现在对于部分问题，无法完全满足以上要求，所以就牺牲了①，但是我们希望结果不是盲目的，所以就引入了近似的概念。

近似算法。比如2-近似，认为W为近似解，W 为最优解，在求最小值的情况下W<=2W ；在求最大值的情况下，W>=1/2W*

给m个机器和n个任务，每个任务有一个ti的执行时间，我们认为完成最后一个任务所需的时间为负载时间，希望能够让这个负载时间最短。

第一种：将任务依次放在机器上，当某个机器空闲时立即放入新任务。此时是2近似的。

证明：

引理1.最短时间安排是大于等于任务中时间最长的任务，L* >= max tj

我们在考虑放入最后一个任务前，根据我们放置的规则，该机器是耗时最短，也就是说，该机器此时的用时是低于除掉最后一个任务后的平均时长，更低于所有任务的平均时长（引理2）；再根据引理1，最后一个任务应该是小于最优解的。

补充：

在这里，我还想讨论一下这个近似算法的中等于符号，先上结论：等号不一定能够找到一个实例，但是可以构造出一种结构，通过取极限求得，我们认为这样 也算是紧的。

构造实例：有m个机器，其中m(m-1)个任务的用时为1，1个任务的用时为m。肯定有一种任务集合，可以按照以下方式进行安排，此时的贪心解为19。

此时最佳的解为10，如下图：

通过推广可以知道此时的比为（2m-1）/m，当m取极限，能够达到2倍。

第二种：将任务从大到小排序，然后依次放在机器上，当某个机器空闲时立即放入新任务。此时是2近似的。

引理3：如果有大于m个任务，那么L*>=2t(m-1)。证明：t(m+1)是目前最短的任务，且目前所有机器上都有任务了，所以该任务加入时最优的情况不过是加入设备的原有任务刚好和t(m+1)相等，即等号。

（2近似）在n个点中，选取k个中心点，使得这些中心点能够以半径R的圆包含所有的点，让其中最大的半径最小，如下图所示：

基础：距离需要满足的三个定理①(同一性)dist(x, x) = 0 ②(自反)dist(x, y) = dist(y, x) ③(三角不等式)dist(x, y) <=dist(x, z)+dist(z, y)

r(C)为C集合中所有点的最大覆盖半径。（需要求min r(C)）

算法：在点集中任选一个作为中心点，然后重复以下步骤k-1次:选取距离已选点集中最远的点，加入点集。

证明：先假设r(C )< 1/2 * r(C)以选好的点画半径为1/2 * r(C)的圆，显然可知[注]，这个圆里有且仅有一个r(C )中的点。那么根据在下图中，根据三角不等式可以得出：

[注]在每个点上r(c )一定会包含到c点，而r(C )<1/2 * r(C)，相当于大圆套小圆，所以c*一定在c的圆中。

（2近似）问题还是很好理解的，在点上加权值，要找一个点覆盖，使得权值最小。如下图左边就是一个带权的最小点覆盖。

算法： 任选一条边(i, j)加上代价，这个代价从零开始，且这个代价的最大值低于i和j节点的权值。显然，这个边权值的最大值取决于两个端点权值的最小值，我们认为当边权值与点权值相等时，对应的那个点是紧的。把所有紧的点找出来即为点覆盖。

流程：

证明：

引理：边权之和小于等于点覆盖的点权之和。这主要是由于涉及到一条边上两个点都被选（紧的）的情况，感性认知可以看上图，缩放证明如下：

w(S)是等于所选的节点的权值之和的，等于所选节点节点所对应的边权之和，可以把它放大到所有节点对应边权之和，这样因为一条边(u, v)在u上算过一次后还要在v上算一次，所以等于边权和的两倍。再由上面引理可得。

主要为了线性规划和整数规划。

（2近似）没啥好说的，只需要把方程构造出来就行了。

由于求解出来结果不一定是整数，所以我们认为某一点的值大于1/2，就选入点集。

证明：

因为xi+xj >=1,且都是正数，那必至少一个点是大于1/2的（反证，两个都小于1/2则和小于1）。

给你n个物品和一个背包，每个物品有一个价值v和一个大小w，背包的容量是W，要求让背包装下尽可能大价值。

背包的时间复杂度：O(nW)

注意其中n表示物品的个数，无论是1个还是999个，他都是多项式的，这个很好理解。但是W就不一样了，这是一个数字。我理解的是这个数字会很奇特，比如1.00001，比如99999，这些有可能看起来不大但是实际在处理的时候很难处理的数字，统一的来说，如果我们把这些数字放在电脑上，都会以二进制的方式存储起来，有些数字用十进制表示很小，但是放在二进制上面就会很大，由W导致不能在多项式时间内解决（找不到一个范围/上界来框它）。

算法： 为了处理这个问题，我们改动了dp的状态转移方程，要让这个转移方程和W无关[注]。

此时还不是多项式的，然后我们再对value进行约。[注]

[注]这两步中，我们把w改成v，并对v进行近似处理。OPT的含义变成了，在面对是否选择第i个物品时，要想让价值达到当前值，最少的weight。理由是更改后的误差是可以忍受的：对v进行近似，结果只会出现最大价值的上下误差，如果对w进行近似，则有可能出现该物品不能放入背包中，导致整个物品直接放弃的情况。

‘柒’ 运筹学中的图论问题

很多实际的生产问题都能被抽象成一张大的图。具体一点的例子，比如需要在若干个城市之间铺设铁路或者架设电网，那么城市就是图里面的点，铁路电网就是图里面的边。抽象一点的例子，比如完成一个项目的过程中所有可能出现的状态都可以视为一个点，而状态到状态之间的转换就是边。上一篇文章中我们说过运筹学是处理实际生产生活中遇到的问题的。一旦实际问题被抽象成了一个图的模型（注意与机器学习里面的图模型区分开来），很多图论里面的算法就可以用来解决实际问题，所以图论是运筹学当中的一个很大的分支。今天我们就介绍一下几个图论的基本算法及其在生产生活中的应用。

一最小生成树

比如现在要在若干个村子之间架设电网，保证每个城市都通上电（先不考虑电网输电能力大小）。虽然理论上讲，任何两个村子之间都可以架设电线，不过那样的话成本很到，不划算，我们需要在所有可能的连线里面找到一组总长最短的边，保证这些边把每个村子都连上了。在图论中，这是一个典型的最小生成树问题。有两种解决最小生成树的方法，第一种办法是把所有的边按照从小到大的顺序添加到图里面，如果产生回路就舍弃它，直到覆盖了所有的点。另一种方法是把图上的边按照从大到小的顺序删除，直到再删下去就一定会产生离散的点为止。

二最短路径

图论中应用最广的问题可能就是最短路径问题了。地图上很多城市之间都有道路相连，想从一个城市到另一个城市，往往有多种选择，可是走那条路距离最短呢？如果地图规模不大，我们可以一眼就看出来。可是随着地图规模变大，就很难再一眼看出来了，需要有严格的算法保证找到最短路径。目前已经有了很多种最短路径算法，他们的基本思想也不尽相同。以着名的Dijkstra算法为例，它每次会选择距离“所有已经选择过了的点”中距离最近的下一个点，一步步的迭代下去。这个流程保证了算法会按照距离出发点由近到远的顺序选择每一个点。

三最大流-最小割问题

油气输送网络又许多不同的边组成，每一条边的运输能力有限。输送油气资源的时候，为了最大化运输量，需要合理安排通过每一条边的油气流量。这就是在一个网络寻找最大流的问题（等价于寻找最小割）。解决问题的想法很简单，找到一组边，它们把整个网络分成了两部分，流的源和目的地址分属于这两个部分。我们称这样一组边为图的一个分割。由于所有的油气流都要通过分割中的边，所以最大流其实受制于分割的流通能力的。于是最大流应该等于流通能力最小的分割。剩下的问题，就是一步步调整，找到最小分割了。

‘捌’ 图论基础

图 是由顶点V和边E的集合组成的二元组，记G=(V,E)

有向图、无向图、有权图、无权图、连通图（联通分量）、二分图

顶点的 度 （无向图种与顶点相连的边的数目）、 入度 （有向图中以该顶点为终点的边的数目）、 出度 （有向图中以该顶点为起点的边的数目），度等于入度和出度之和，所有边的入度和=所有边的出度和=边数

图的定义是指将边作为一个集合，从而允许两个无向边具有相同的端点。对于两个有向边可以有相同的起点和终点。这种边称为 平行边 或者 多重边 。另一种边的特殊类型是顶点和自己连接，也就是说两个顶点重合，我们称这样的边为 自循环 。除了少数例外，图没有平行边和自循环

图G中从顶点u到顶点v有一条路径，我们称u到达v，并且v是从u 可达 的。在无向图中，可达性的概念是对称的。

如果一个图是 连通 的，则意味着对于任何两个顶点，它们中间都是有路径的。

如果对于G的任何两个顶点u和v，都有u可达v并且v可达u，则有向图是 强连通 的

图G的 子图 是顶点和边是G的顶点和边的各自的子集的图H。G的 生成子图 是包含图G的所有顶点的图。

如果图G是不连通的，它的最大联通子图称为G的连通分支。

森林 是没有循环的图。 树 是连通的森林，即没有循环的联通图。图的 生成树 是树的生成子图

特性1 ：如果G是由m条边和顶点集V的图，那么 ，即边对顶点度数的总贡献度是边数目的两倍

特性2 ：如果G是有m条边和顶点集V的有向图，那么 即边对它的起点u的出度贡献了一个单元，对终点v的入度贡献了一个单元。因此边对顶点出度的总贡献和边的数目相等，入度也是一样。

特性3 ：给定G为具有n个顶点m条边的简单图。如果G是无向的，那么 ，如果G是有向的，那么

特性4： 给定G是有n个顶点和m条边的无向图。

边列表 ：对所有边采用无序的列表。但是没有有效的办法找到特定的边(u,v)​，或者将所有的边入射到顶点v

邻接列表 ：为每个顶点维护一个单独的列表，包括入射到顶点的那些边。可以通过取较小集合的并集来确定完整的边集合，也可以更高效地找到所有入射到给出顶点的边

邻接图 ：和邻接列表非常相似，但是所有入射到顶点的边的次级容器被组织成一个图，而不是一个列表，用相邻的顶点作为键。这允许在O(1)的时间内访问特定的边(u,v)

邻接矩阵 ：对于有n个顶点的图维持一个n*n矩阵来提供最坏的情况下访问特定边(u,v)的时间O(1)。每一项专用于为顶点u和v的特定对存储一个参考边(u,v)；如果没有这样的边存在，该表项即为空

可能是最简单的，但不是最有效的。所有顶点存储在一个无序的列表V中，并且所有的边对象存储在一个无序的列表E中

将图形的边存储在较小的位置来对其进行分组，从而和每个单独的顶点相关联的次级容器结合起来。具体的，对每个顶点v维持一个集合l(v)，该集合被称为v的 入射 列表，其中全部都是入射到v的边。（在有向图的情况下，输出边和输入边分别存储在两个单独的集合lout(v)和lin(v)中。

同时要求邻接列表的基本结构在某种程度上保持顶点集合V，因此可以在O(1)时间内为给出的顶点v找出次级结构l(v)

命题 ：对于i=1，...，n，当且仅当有向图 从 到 有一条有向路径时，有向图 有边 ，其中中间的顶点在集合 中，特别的， 和 相等， 是 的传递闭包

该命题为计算G的依赖于一系列界限的每个 传递闭包提出了一个简单算法。这个算法被称为 Floyd_Warshall算法

没有有向循环的有向图被叫作 有向非循环图 ，或者简称 DAG

‘玖’ 图论算法及其MATLAB实现的图书目录

第1章 图论的基础知识1
1.1图论的起源1
1.2着名的图论学者——欧拉1
1.3图2
1.4特殊图类3
1.5有向图4
1.6图的矩阵表示5
1.6.1邻接矩阵5
1.6.2关联矩阵5
1.7图论的基本性质和定理6
1.8计算有向图的可达矩阵的算法及其MATLAB实现6
1.9关联矩阵和邻接矩阵的相互转换算法及其MATLAB实现7
习题一11
第2章 最短路12
2.1路12
2.2最短路问题13
2.3求连通图最短距离矩阵的算法及其MATLAB实现14
2.4求两点间最短路的Dijkstra算法及其MATLAB实现15
2.4.1 Dijkstra算法16
2.4.2 Dijkstra算法的MATLAB实现16
2.5求两点间最短路的改进的Dijkstra算法及其MATLAB实现18
2.5.1 Dijkstra矩阵算法Ⅰ18
2.5.2 Dijkstra矩阵算法Ⅱ18
2.6 求两点间最短路的WarshallFloyd算法及其MATLAB实现21
2.6.1 Floyd算法的基本思想22
2.6.2 Floyd算法的基本步骤22
2.6.3 WarshallFloyd算法的MATLAB实现22
2.7求任意两点间最短路的算法及其MATLAB实现25
2.8求从一固定点到其他所有点最短路的算法及其MATLAB实现27
2.9求必须通过指定两个点的最短路的算法及其MATLAB实现29
2.10求图的两顶点间最短路与次短路的算法及其MATLAB实现32
2.11求最大可靠路的算法及其MATLAB实现34
2.12求最大期望容量路的算法及其MATLAB实现36
习题二38
第3章 连通图40
3.1判断图的连通性算法及其MATLAB实现40
3.2连通图的中心和加权中心的算法及其MATLAB实现42
3.3连通无向图一般中心的算法及其MATLAB实现44
习题三46
第4章 树48
4.1树及其性质48
4.2割点、割边、割集50
4.3二元树与Huffman树51
4.3.1有序二元树51
4.3.2 Huffman树51
4.4求Huffman树及其MATLAB实现52
4.5广度优先搜索算法及其MATLAB实现55
4.6深度优先搜索算法及其MATLAB实现57
4.7求割点算法及其MATLAB实现61
4.8生成树及其个数65
4.9求无向图的生成树算法及其MATLAB实现67
4.10求有向图的生成树算法及其MATLAB实现69
4.11求有向连通图的外向树与内向树数目的算法及其MATLAB实现71
4.12最小生成树问题73
4.13求最小生成树的Kruskal算法及其MATLAB实现74
4.13.1 Kruskal算法的基本思想74
4.13.2 Kruskal算法的MATLAB实现74
4.14求最小生成树的Prim算法及其MATLAB实现76
4.14.1 Prim算法的基本思想76
4.14.2 Prim算法的MATLAB实现77
习题四79
第5章Euler图和Hamilton图81
5.1 Euler图81
5.2“一笔画”问题及其理论81
5.3中国邮递员问题82
5.4 Fleury算法及其MATLAB实现82
5.4.1 Fleury算法的步骤82
5.4.2 Fleury算法的MATLAB实现82
5.5 Hamilton图87
5.6旅行售货员问题88
5.7改良圈算法及其MATLAB实现89
习题五92
第6章 匹配问题及其算法93
6.1问题起源——婚配问题93
6.2二分图的有关知识93
6.3匹配、完美匹配、最大匹配93
6.4匹配的基本定理94
6.5应用案例——BernolliEuler错放信笺问题95
6.6寻求图的一个较大基数匹配算法及其MATLAB实现95
6.7人员分配问题97
6.8匈牙利算法及其MATLAB实现97
6.8.1匈牙利算法基本步骤97
6.8.2匈牙利算法的MATLAB实现98
6.8.3案例及其MATLAB实现100
6.9最优分配问题101
6.10 KuhnMunkres算法及其MATLAB实现101
6.10.1 KuhnMunkres算法的基本思想101
6.10.2利用可行顶点标记求最佳匹配的KuhnMunkras算法步骤102
6.10.3 KuhnMunkres算法的MATLAB实现102
6.10.4简单实验105
习题六107
第7章 网络流的算法108
7.1网络、流和割108
7.1.1网络和流108
7.1.2割109
7.2网络的最大流问题110
7.3最大流最小割定理110
7.4 FordFulkerson标号算法及其MATLAB实现111
7.4.1 FordFulkerson标号算法的基本步骤111
7.4.2 FordFulkerson 标号算法的MATLAB实现112
7.4.3案例及其MATLAB实现113
7.5 Dinic算法及其MATLAB实现114
7.5.1 Dinic算法的基本思想114
7.5.2 Dinic算法的MATLAB实现115
7.5.3案例