图论及其算法吴闻第一章 基本概念 1.1 引言 1.2 图的定义 1.3 道路和回路 1.4 树1.1 引言 图论是一个应用十分广泛而又极其有趣的数学分支物理、化学、生物、科学管理、计算机等各个领域都可找到图论的足迹介绍几个图论有关的简单例子1.1 引言 例1 下图是一个公路网，V1,V2,.,V10是一些城镇，每条线旁边的数字代表这一段公路的长度现在问，要从V1把货物运到V10，走哪条路最近?1.1 引言 例1实际上，就是图论中的求最短路径问题在现实中有很多此类问题，所以图论中求最短路径算法是一个非常经典和重要的算法1.1 引言 例2 下图是一个公路网，V1,V2,.,V10看成公路网的一个站点，若这个公路网目前被敌方占领请分析一下，最少需要破坏其公路网的几个站点，就可摧毁敌方整个运输线1.1 引言 例2属于图的连通性问题找出图中的割顶集，就是问题的解军事指挥中很多此类问题1.1 引言 例3 飞行大队有若干个来自各地的驾驶员，专门驾驶一种型号的飞机，这种飞机每架有两个驾驶员由于种种原因，例如相互配合的间题，有些驾驶员不能在同一架飞机上飞行，问如何搭配驾驶员，才能使出航的飞机最多1.1 引言 例3 用V1,V2,.,V10代表这10个驾驶员。
如果两个人可以同机飞行，就在代表他们两个之间连一条线;两个人不能同机飞行，就不连例如V1和V2可以同机飞行，而V1和V 3就不行1.1 引言 例3此类问题属于图的最大匹配问题 将实际生活中的事物分析转化为图论问题的实例还很多.1.2 图的定义 图：由若干个不同顶点与连接其中某些顶点的边所组成的图形图的表示：通常用一个大写字母G来表示图，用V来表示所有顶点的集合，E表示所有边的集合，并且记成G=(V,E)1.2 图的定义 子图：如果对图G=(V,E)与G=(V,E),G的顶点集是G的顶点集的一个子集(VV),G的边集是G的边集的一个子集(EE)，我们说G是G的子图1.2 图的定义 环：如果一条边，它的起点和终点相同，这样的边称为环平行边：若连接两个顶点的边有多条，则这些边称之为平行边孤立点：不与任何边关联的顶点称为孤立点1.2 图的定义 简单图：如果一个图没有环，并且每两个顶点之间最多只有一条边，这样的图称之为简单图在简单图中，连接Vi与Vj的边可以记成(Vi,Vj)完全图：如果G是一个简单图，并且每两个顶点之间都有一条边，我们就称G为完全图通常将具有n个顶点的完全图记为Kn二分图：如果G是一个简单图，它的顶点集合V是由两个没有公共元素的子集X=X1,X2,.,Xn与Y=Yl,Y2,.,Ym组成的，并且Xi与Xj(1i,jn),Ys与Yt(1s,tm)之间没有边连接，则G叫做二分图。
1.2 图的定义 简单图、完全图、二分图1.2 图的定义 完全二分图：如果在二分图G中，IXI=N,IYI=M，每一个XiX与每一个YjY有一条边相连，则G叫做完全二分图1.2 图的定义 如果G是一个N个顶点的简单图，从完全图Kn中把属于G的边全部去掉后，得到的图称为G的补图，通常记为G一个图的补图的补图就是自身1.2 图的定义 相邻：如果图G的两个顶点Vi与Vj之间有边相连，我们就说Vi与Vj是相邻的，否则就说Vi与Vj是不相邻的如果顶点V是边e的一个端点，就说顶点V与边e是相邻的，e是从V引出的边度数：从一个顶点V引出的边的条数，称为V的度数，记作d(V)1.2 图的定义 下图中，d(V1)=d(V2)=d(V3)=d(V4)=d(V5)=5-1=4,d(Y3)=2等等1.2 图的定义 K度正则图：把每个顶点的度数为常数K的图叫做K度正则图经常使用下面两个符号:1.2 图的定义 从顶点度数问题的讨论中，引出一些有趣的结论:1.2.对于任意的图G，奇次顶点的个数一定是偶数1.2 图的定义 例1、空间是否有这样的多面体存在，它们有奇数个面，而每个面又有奇数条边?分析:根据题意，可以构造一个图，以面为顶点，当且仅当两个面有公共棱时，则在G的相应两顶点间连一条边，得到图G。
依题意，图的顶点个数是奇数，而且每个顶点的度数d(V)是奇数，从而 也是奇数，与结论1相违，故这种多面体不存在1.2 图的定义 例2、晚会上大家握手联欢，问是否会出现握过奇次手的人是奇数的情况?分析:一个图，以人为顶点，两人握手时，则相应的两个顶点之间连一条边，于是每人握手的次数即相应顶点的度数由结论2，奇次顶点的个数总是偶数，所以握过奇次手的人数是奇数的情况不可能出现1.3 道路与回路 道路：在图G中，一个由不同的边组成的序列e1,e2.,eg，如果ei是连接Vi-1与Vi(i=1,2,.,g)的，我们就称这个序列为从V0到Vg的一条道路，数g称为路长，V0与Vg称为这条道路的两个端点，Vi(1=i=g-1)叫做道路的内点如果G是简单图，这条道路也可以记作(V0,V1,.,Vg)1.3 道路与回路 下图中e1,e2,e3,e4,e5,e6组成一条道路1.3 道路与回路 轨道：在道路的定义中，并不要求V0至Vg，互不相同如果V0至Vg互不相同，这样的道路称为轨道，记成P(V0,Vg)回路：V0=Vg的路称为回路圈：V0=Vg的轨道叫做圈K阶圈：长为K的圈叫做K阶圈显然，如果有一条从V到V的道路上去掉若干个回路，便可得到一条从V到V的轨道。
1.3 道路与回路 U,V两顶点的距离：U,V间最短轨道的长度，记作为D(U,V)连通图：若U与Y之间存在道路，则称U与V相连通图G中任意两个顶点皆连通时，称G为连通图1.3 道路与回路 如果图G是一条从V0到Vg的道路，那么该条道路上的每一个内点Vi(1=i0这时对于G的任意一个生成树T，我们把属于T的各条边的长度之和称为T的长度，记作L(T)3.1求无向图的最小生成树一、最小生成树的由来 下图中，T1和T2是G的生成树，L(T1)=22,L(T2)=173.1求无向图的最小生成树一、最小生成树的由来 最小生成树问题：如何从G的所有生成树中，找出长度最小的生成树这个问题即所谓最小生成树间题3.1求无向图的最小生成树二、最小生成树的计算 一开始，先将G图中的边都去掉，只留下孤立的顶点，这个图即为G图最初的生成子图G1然后逐步地将当前最小边e1加上去，每次加的时候，要保持“没有圈”的性质，在加了N-1条边(N是顶点个数)后，G1便成为所要求的最小生成树了3.1求无向图的最小生成树二、最小生成树的计算 算法步骤如下：第四章 图的连通性 4.1 连通性的基本概念和定义 4.2 深度优先搜索(dfs)4.3 求割顶和块 4.4 求极大强连通子图 4.5 求最小点基 4.6 可靠通讯网的构作4.1 连通性的基本概念和定义 在无向图G中，如果从顶点V到顶点V有路径，则称V和V是连通的。
如果对于图中任意两个顶点Vi,VjV,Vi和Vj都是连通的，则称该图为连通图所谓连通分量指的是无向图中的极大连通子图4.1 连通性的基本概念和定义 在有向图G中，如果对于每一对Vi,VjV,ViVj,从Vi到Vj，和从Vi到Vj都存在路径，则称G是强连通图有向图中的极大强连通子图称作有向图的强连通分量4.1 连通性的基本概念和定义 一个连通图的生成树是一个极小连通子图，它含图的全部顶点，但只有足以构成一棵树的N-1条边超过N-1条边必有回路，就不再是树了4.1 连通性的基本概念和定义 为更精确的描述图的连通性，还需引入两个概念：顶连通度K(G)边连通度K(G)4.1 连通性的基本概念和定义顶连通度：V是连通图G的一个顶点子集在G中删去V及与V相关联的边后图不连通，则称V是G的割顶集最小割顶集中顶点的个数，记成K(G)，称为G的连通度规定K(完全图)=顶点数-1;K(不连通图)=K(平凡图)=0K(G)=1时，割顶集中的那个顶点叫做割顶没有割顶的图叫做块，G中成块的极大子图叫做G的块4.1 连通性的基本概念和定义 下图中，K(G2)=1,K(G3)=3,K(G4)=5-1=4;G3与G4是块;G2中有两个三角形块。
4.1 连通性的基本概念和定义边连通度K(G)E是连通图G的一个边子集在G中删去E中的边后图不连通，则称E是G的桥集.若G中已无桥集E，使得|E|M,G叫做M连通图;K(G)M时，G称为M边连通图下面给出连通图G的两个特征:1.K(G)K(G)G的顶点度数的最小值 2.顶点数大于2的2连通图的充分必要条件是任两个顶点在一个圈上4.2 深度优先搜索(dfs)深度优先搜索过程:先任取一个顶点为根，记为U，作为深搜的起始出发点，设置U顶点为已访问再从U的邻接顶点中，任选W顶点，对应关联边(U,W)，将该边定方向为U到W此时边(U,W)称为“已检查”，且作为树枝边且加入树枝边集合中，U称为W的父亲点，记为U=father(W)再以W顶点作为新的出发点，重复上面步骤4.2 深度优先搜索(dfs)一般情况下当访问某顶点X时，有两种可能:1、如果X顶点的所有关联边被检查过了，则回溯至X的父亲顶点，从father(X)再继续搜索，此时X顶点已无未用过的关联边;2、如存在X顶点未用过的关联边，则任选其中一边(X,Y)，对其定向为从X到Y,此时说边(X,Y)正等待检查4.2 深度优先搜索(dfs)检查结果有两种情况:1.如Y顶点从未被访问过，则顺着(X,Y)边访问Y，下一步从Y开始继续搜索。
此时(X,Y)是前向边，且顶点X=father(Y)，图上用实线表出;2.如Y顶点已被访问过，则再选一X顶点未用过的关联边此时(X,Y)是后向边，用虚线表出4.2 深度优先搜索(dfs)此时，(X,Y)的归属已明确，(X,Y)就检查完毕在dfs搜索期间，将顶点X被首次访问的序号作为顶点的dfn值，记为dfn(X)，如dfn(X)=i，则X是深搜过程中第i个被访问的顶点，dfn(X)称为X的深度优先搜索序数，当搜索返回根时，连通图的所有顶点都访问完毕现在图中的边都定了方向，且分成前向边以及后向边(虚线)，前向边(实线)组成的有向树，称为dfs树4.2 深度优先搜索(dfs)对左图进行dfs搜索得到右图的dfs树每个顶点旁数字为顶点dfn值4.2 深度优先搜索(dfs)无向图G的dfs算法分析4.2 深度优先搜索(dfs)dfs树由前向边组成，若非连通图，则对每一个连通分量进行一次dfs搜索，结果产生一个由若干dfs树组成的森林如果从U到W有树边组成的有向路，则称U和W有直系关系，U称为W的祖先点，W称为U的后代点如(U,W)是树中一条边，U又确切地称为W的父亲点，W也可称为U的儿子点一个顶点可有多个儿子点，顶点U和它的所有后代点组成关于树中以U为根的子树。
4.2 深度优先搜索(dfs)有向图的dfs本质上近似无向图，区别在于搜索只能顺边的方向去进行(有向边，简称弧)有向图中的弧根据被检查情况可有4种，一条未检查的弧(U,W)可按如下4种情况，分类归划成(其中2,3,4所述的三种情况中，设W已访问过)：4.2 深度优先搜索(dfs)1.W是未访问过的点，(U,W)归入树枝弧 2.W是U的已形成的dfs森林中直系后代点，则(U,W)称为前向弧无论(U,W)是树枝弧还是前向弧，dfn(W)dfn(U)3.W是U的已形成的dfs森林中直系祖先点，则(U,W)称为后向弧4.U和W在已形成的dfs森林中没有直系上下关系，并且有dfn(W)dfn(U)这种类型的横叉弧4.2 深度优先搜索(dfs)4.2 深度优先搜索(dfs)下图为有向图的dfs示例：,是树枝弧，组成dfs森林(用粗线表示);是后向弧;是前向弧;,是横叉弧4.2 深度优先搜索(dfs)有向图和无向图的dfs算法基本相似4.3 求割顶和块 割顶：如果一个连通图，删除某一顶点，不在连通，这个顶点就称为割顶块：一个连通图，如果删除任一顶点不会破坏连通性，即没有割顶，这个连通图称为块4.3 求割顶和块 分析一个由无向图表示的通讯网，顶点看作是通讯站，无向边代表两个通讯站之间可以互相通讯。
问:1.若其中一个站点出现故障，是否会影响系统正常工作;(求割顶)2.这个通讯网可以分成哪几个含站点尽可能多的子网，这些子网内的任一站点出现故障，都不会影响子网工作求块，即没有割顶的连通子图)4.3 求割顶和块给定dfs树，割顶的判断：1.如U不是根，U成为割顶当且仅当存在U的某一个儿子顶点S，从S或S的后代点到U的祖先点之间不存在后向边2.如被选为根，则成为割顶当且仅当它有不止一个儿子点4.3 求割顶和块给定dfs树，割顶的判断：4.3 求割顶和块 割顶的判断法则是构思算法的精华，为此引入一种顶点U的标号函数LOW(U)=min(dfn(U),LOW(S),dfn(W)其中:S是U的儿子，(U,W)是后向边显然LOW(U)值恰是U或U的后代所能追溯到的最早(序号小)的祖先点序号一般约定，顶点自身也认为自己是祖先点所以有可能LOW(U)=dfn(U)或LOW(U)=dfn(W)4.3 求割顶和块 利用标号函数LOW，我们可以将割顶判定1重新描述成:顶点U作为G的割顶当且仅当U有一个儿子S，使得LOW(S)dfn(U)，即S和S的后代不会追溯到比U更早的祖先点4.3 求割顶和块 LOW(U)值的计算步骤如下:在算法执行中，对任何顶点U计算LOW(U)值是不断修改的，只有当以U为根的dfs子树和后代的LOW值、dfn值产生后才停止。
4.3 求割顶和块 求割顶算法4.3 求割顶和块 示例如下：从左图V3出发，按上述算法进行搜索，得出dfs树和各顶点dfn值、LOW值见右图由于是前向边，且dfn(V5)=21,LOW(V5)=2，又LOW(V4)=2，由基本事实1得出V4是割顶，并导出V4,V3,V2和V4,V5,V6,V7两个块4.4 求极大强连通子图 极大强连通子图：有向图中任意两个顶点都有向路双向连通的最大子图 为了在dfs森林的基础上找强分支子树的根，我们引人了顶点U的标值函数LOWLINK(U)：LOWLINK(U)=mindfn(U),dfn(W)其中W是从U或U的后代点出发用一条后向弧或横叉弧所能到达的同一强连通分支中的顶点4.4 求极大强连通子图 由此可以看出，LOWLINK(U)正是U所处的强分支中从U出发先用树枝弧、前向弧，最后用后向弧或横叉弧到达的dfn最小的顶点的序值而对于强分支的根i显然有LOWLINK(i)=dfn(i)因此当深度优先搜索从一个使dfn编码=LOWLINK值的顶点U返回时，从树中移去根为U的所有顶点每一个这种顶点的集合是一个强分支，即极大强连通子图.4.4 求极大强连通子图 算法的主要思路是用逐步迭代计算出LOWLINK(U)值。
4.4 求极大强连通子图 求极大强连通分支的算法。