第10章_图与网络分析(清华教材)

第10章图与网络分析第一节图论的基本概念（1）引言十八世纪的哥尼斯堡城中流过一条河（普雷.格尔河），河上有7座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这7座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“哥尼斯堡7桥”难题。第一节图论的基本概念（2）“哥尼斯堡7桥”难题最终在1736年由数学家Euler的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到1936年匈牙利数学家O.König写出了图论的第一本专著《有限图与无限图的理论》。在图论的发展过程中还有两位著名科学家值得一提，他们是克希霍夫和凯莱。克希霍夫在研究电网络时对图的独立回路理论作出了重要的贡献，而化学家凯莱在对碳氢化合物的同分异构体的数量进行计数时推动了图论中树的计数问题的研究。第一节图论的基本概念（3）图论的历史上最具有传奇色彩的问题也许要数著名的“四色猜想”了——历史上许许多多数学猜想之一。它描述对一张地图着色的问题，曾经有一位数学家这样说：“对于这个问题，一位数学家可以用不到五分钟的时间向马路上任何一位行人讲述清楚它，然后，两人都明白这一问题，但是，两人都无能为力。”幸运的是在1970’s终于由美国的两位数学家借助大型计算机将其证明了。第一节图论的基本概念（4）定义：有序二元组G=(V,E)称为一个图，其中(1)V=｛v1,v2,…,vn}是有穷非空集，称为顶点集，其中的元素叫图G的顶点.(2)E={eij}称为边集，其中的元素叫图G的边.若eij={Vi,Vj}是个无序二元组，则图G是个无向图则图为右图形式：例1设G=(V,E)，其中V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5},第一节图论的基本概念（5）端点：若eij={Vi,Vj}，则称eij连接Vi和Vj,点Vi和Vj称为eij的端点一条边的端点称为与这条边关联例1设G=(V,E)，其中V={v1,v2,v3,v4}，E={e1,e2,e3,e4,e5},点邻接的：与同一条边关联的两个端点称为邻接的第一节图论的基本概念（4）常用术语：(1)端点相同的边称为环(4)边和它的端点称为互相关联的．(5)既没有环也没有多重边的图，称为简单图(2)若一对顶点之间有两条以上的边联结，则这些边称为重边．(3)有边联结的两个顶点称为相邻的顶点，有一个公共端点的边称为相邻的边．(6)一个没有环但允许多重边的图，称为多重图第一节图论的基本概念（5）顶点的次数:(1)在无向图中，与顶点v关联的边的数目（环算两次）称为v的次数，记为d(v)．(2)悬挂点：次为1的点。悬挂边：悬挂点的关联边。孤立点：次为零的点。4)(4vd第一节图论的基本概念（6）定理1:||2)()(EvdGVv定理2任何图中奇次顶点的总数必为偶数．链：如果图中的某些点、边可以排列成点和边的交错序列，则称此为一条链。圈：如一条链中起点和终点重合，则称此为一条圈。初等链（圈）：如果链（圈）中点都是不同的，就称之为初等链（圈）。简单链（圈）：如果链（圈）中边均不相同，就称之为初等链（圈）。连通图：如果图中的任意两点之间至少存在一条链，则称图为连通图，否则为不连通图。支撑子图：给了一个图G=(V,E),如果图G′=(V′,E′),使V=V′及E′包含于E,则称G′是G的一个支撑子图。基础图：设给了一个有向图,D=(V,A),从D中去掉所有弧上得箭头就得到一个无向图,称之为D的基础图,记为G(D).对无向图链与路（圈与回路）这两个概念是一致的。v1v5v4v2v3e1e8e7e6e5e4e3e2有向图),,,,,,,,,,(56211344223vevevevevev路链（点不同）),,,,,,(4311223vevevev简单链（边不同）第一节图论的基本概念（13）对有向简单图G＝（V，E）对应着一个|V||V|阶矩阵A＝（aik)，其中则称矩阵A是图G的邻接矩阵例设图为否则连向当有弧从0ji1aji则其邻接矩阵为432143210110000001011000Avvvvvvvv＝对有向赋权图Ｇ，其邻接矩阵)(ijaA，其中：EvvjiwEvvwajiijjiijij),(0,),(若若为其权且若无向赋权图的邻接矩阵可类似定义．A=4321432105375083802720vvvvvvvv返回第二节图的连通与割集（1）在图G中的，一个点和边的交替序列（ni，eij，nj，…nk，ekl，nl）称为G中由ni到nl的一条路，记为{ni,nl}简单路：如果路中的边不重复，称为简单路当G是简单图时，一、图的连通初级路：如果路中的点不重复，称为初级路由ni到nl的一条路可以用点的序列来表示：（ni，nj，…nk，nl）回路：在G中，一条至少包含一条边，并且ni＝nl的{ni,nl}称为G点一条回路。树：一个无圈的连通图称为树。性质：树G=（V，E）的顶点数为p，边数为q，则q=p-1。例如：支撑树：图T=（V，E′）是图G=（V，E）的支撑子图，若图T是一个树，则称T是图G的一个支撑树。10.2树10.2.1树与支撑树定理3：设图G=(V,E)是一个树,顶点个数,则G中至少有两个悬挂点。定理4：设图G=(V,E)是一个树的充分必要条件是G不含圈，且恰有条边。2)(Gp1p定理5：设图G=(V,E)是一个树的充分必要条件是G是连通图，且边数定理6：设图G=(V,E)是一个树的充分必要条件是G的任意顶点之间恰有一条链。1)()(GpGq（1）G不含圈（2）G是连通图（3）（4）图G=(V,E)是一个树上述条件有两个成立，就推出其余条件成立。1)()(GpGq树的性质：1在图中任意两点之间必有一条而且只有一条通路。2在图中划去一条边，则图不连通。树是边最少的连通图3在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。4图中边数有n=p-1（p为顶点数）支撑树和最小支撑树的实际应用在实际生活中，支撑树和最小支撑树有许多重要的应用。例如：用网络G表示n个城市之间的通信线路，其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价，由此构造了一个赋权图。我们可以通过求该图的最小支撑树达到求解通信线路或总代价最小的最佳方案。求支撑树——“破圈法”和“避圈法”v1v2v3v5e2e3e5e1e6e7e8e4v4定理7：图G有支撑树，当且仅当图G是连通的。v1v2v5e2e3e5e1e6e7e8e4v4我们给定一个连通图，如右所示，求它的支撑树。破圈法：在图中任选一个圈，从这个圈中去掉一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。v3v1v2v5e2e3e5e1e6e7e8e4v4v1v2e1v3e2e4v4v5e6避圈法：开始选一条边，以后每一步中，总从未被选取的边中选出一条与已选边不构成圈的边。v3根据破圈法和避圈法两种方式得到了图的两个不同的支撑树，由此可以看到连通图的支撑树不是唯一的。v1v2v3v5e1e6e8e4v410.2.2最小支撑树问题最小支撑树：给图G中的每一条边（vi，vj）一个相应的数ij，则称G为赋权图。ij称为边（vi,vj）的权数。在赋权图G的所有支撑树中，必有某个支撑树，其所有边的权数和最小，称这个树为图G的最小支撑树。求赋权图G的最小支撑树的方法也有两种，“破圈法”和“避圈法”。破圈法：在原图中，任选一个圈，从圈中去掉权最大的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。655172344v1v2v3v4v5v6v3v21v42v53v64v15655172344v1v2v3v4v5v6避圈法：开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。第三节最短路问题（1）路的权（或者路的长）：给定一个有（无）向网络G=(V,A,W)，设P为G中的一条有向路，令则称W(P)为路径P的权（或长）最短路：在网络G中，从顶点u到顶点v的具有最小权的路P＊(u,v)称为顶点u到顶点v的最短路。在无向网络图中，最短路就简称为最短路在有向网络图中，最短路称为最短有向路Paaw)(W(P)最短路是一条路径，且最短路的任一段也是最短路最短路有一个重要而明显的性质：第三节最短路问题（6）Dijkstra算法中的符号：P：表示某个点的P标号（永久标号）T：表示某个点的T标号（临时标号）Si：表示第i步时具有P标号点的集合λ(v)＝m：表示从Vs到V的最短路上，V的前一个点是Vmλ(v)＝M：表示G中不含从Vs到V的路λ(v)＝0：表示V＝VsDijkstra算法的具体步骤：第三节最短路问题（7）Dijkstra算法步骤：第0步：(开始i=0）令S0={Vs}，λ(Vs)＝0,对每一个V≠Vs,令T（V）＝∞，，λ(V)＝M,令K＝s第1步：若Si=V，则算法终止，这时每个V都在Si中，最短路长为P(V)第2步：考察每个(Vk,Vj)∈E,且VjSi的点Vj如果T(Vj)P(Vk)+wkj则把T(Vj)修改为P(Vk)+wkj，把λ(Vj)修改为k,否则转第3步第3步：令)}{T(Vmin)T(VjjiijSV若T(Vji)∞则Vji的T标号变为P标号，P(Vji)=T(Vji),令Si+1=Si∪{Vji}k=ji,把i换成i+1,转第1步，否则终止第三节最短路问题（8）例求V1到其余各点的最短距离V1V2V5V4V3V6V7V8V9163221064110224336第三节最短路问题（9）例求下图下列有向图的顶点u1到其余顶点的最短有向路解：第一步置i=0，S0={V1},P(V1)=0,λ(V1)=0,令T（Vi）＝∞，λ(Vi)＝M,(i=2,3,…6),k=1V6V1V2V426453235V3V5741V6V1V2V426453235V3V57410534第三节最短路问题（10）V6V1V2V426453235V3V574105343108把T(V2)修改为P(V1)+W12=5,λ(V2)=1,同理T(V4)＝3,T(V6)＝4λ(V4)＝1,在所有T标号中T(V4)=3最小，令P(V4)=3,S1={V1,V4},k=4第三节最短路问题（11）V6V1V2V426453235V3V574105431084i=1，把T(V5)=8,T(V3)=10,λ(V5)＝4,λ(V3)=4,在所有T标号中T(V6)=4最小，令P(V6)=4,S2={V1,V4,V6},k=6第二步第三节最短路问题（12）V2V6V1V426453235V3V57410531084置P={1,4,6}，T={2,3,5}置P={1,2,4,6}，T={3,5}V6V1V426453235V3V5741053884V2第三节最短路问题（13）置P={1,2,4,6}，T={3,5}V6V1V426453235V3V5741053884V2V6V1V426453235V3V5741053884V2置P={1,2,3,4,6}，T={5}第三节最短路问题（14）V6V1V426453235V3V5741053884V2置P={1,2,3,4,6}，T={5}V6V1V426453235V3V5741053884V2置P={1,2,3,4,5.6}，T={}第三节最短路问题（15）例2求下图从顶点V1到其余顶点的最短路解：第一步置u1=0，uj=w1j，j=2,3,…,8，P={1}，T={2,3,…,8}V8V1V2V393821619V5V7243V4V675160281第2步在T中寻找一点k，使得}{uminujTjk第三节最短路问题（16）V8V1V2V393821619V5V7243V4V675160281第2步在T中寻找一点k，使得}{uminujT