第08讲 图的基本概念及最小支撑树问题

图的基本概念及最小支撑树问题 无向图定义 无向图G = , 其中(1) V 为顶点集，元素称为顶点(2) E为VV 的多重集，其元素称为无向边，简称边实例 设 V = v1, v2, ,v5, E = (v1,v1), (v1,v2), (v2,v3), (v2,v3), (v2,v5), (v1,v5), (v4,v5) 则 G = 为一无向图相关定义1.邻接：两个点有公共边，两条边有公共顶点；2.关联：边与其顶点；3.环：一条边的两个顶点重合；4.重边：两个点之间有多于一条边；5.简单图：既无环也无重边的图；6.补图：图G的补图定义为 ：与G有相同的顶点集， 中两个点相邻当且仅当它们在G中不相邻；7.二部分图(二分图)8.支撑子图9.导出子图10. 点度、通路、回路GG有向图定义 有向图D=, 只需注意E是VV 的多重子集图2表示的是一个有向图，试写出它的V 和 E 注意：图的数学定义与图形表示，在同构的意义下是一一对应的网络(带权图)对于图G的每条边e都赋予一个值w(e),称为边的权，则G连同边上的权称为一个网络，记为G=(V,E,w)无向图的关联矩阵无向图的关联矩阵（对图无限制）定义 无向图G=，|V|=n，|E|=m，令 mij为 vi 与 ej的关联次数，称(mij)nm为G 的关联矩阵，记为M(G). 性质：平行边的列相同平行边的列相同)4(2)3(),.,2 , 1()()2(),.,2 , 1(2)1(,11mmnivdmmjmjiijimjijniij jiijmjmjiijiijniijmnivdmvdmmjm,1110)3(,.,2 , 1),()1(),()1()2(),.,2 , 1(0)1( 的的终终点点为为，不不关关联联与与，的的始始点点为为jijijiijevevevm10,1 定义定义 有向图有向图D=，则称则称 (mij)n m为为D的的关联矩阵关联矩阵，记为，记为M(D). (4) 平行边对应的列相同平行边对应的列相同性质性质有向图的关联矩阵邻接矩阵定义 设无向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令cij为顶点 vi 和 vj 之间边的条数，称(cij)为D的邻接矩阵，记作A(D)，或简记为A. 定义 设有向图D=, V=v1, v2, , vn, E=e1, e2, , em, 令cij为顶点 vi 邻接到顶点 vj 边的条数，称(cij)为D (cij)的邻接矩阵，记作A(D)，或简记为A. 图的连通性无向图的连通性(1) 顶点之间的连通关系：G=为无向图 若 vi 与 vj 之间有通路，则 vivj 是V上的等价关系 R=| u,v V且uv (2) G的连通性与连通分支 若u,vV，uv，则称G连通 V/R=V1,V2,Vk，称GV1, GV2, ,GVk为连通分 支，其个数 p(G)=k (k1)； k=1，G连通割集1. 删除顶点及删除边 Gv 从G中将v及关联的边去掉 GV从G中删除V中所有的顶点 Ge 将e从G中去掉 GE删除E中所有边 2. 点割集与边割集 点割集与割点定义 G=, VV V为点割集p(GV)p(G)且有极小性 v为割点v为点割集定义 G=, EE E是边割集p(GE)p(G)且有极小性 e是割边（桥）e为边割集无向树定义(1) 无向树连通无回路的无向图(2) 平凡树平凡图(3) 森林至少由两个连通分支（每个都是树）组成(4) 树叶1度顶点(5) 分支点度数2的顶点 树的充要条件定理16.1 设G=是n阶m条边的无向图，则下面各命题是等价的：(1) G 是树(2) G 中任意两个顶点之间存在惟一的路径.(3) G 中无回路且 m=n1. (4) G 是连通的且 m=n1.(5) G 是连通的且 G 中任何边均为桥.(6) G 中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到惟一的一个含新边的圈. 支撑树定义：T为G的支撑子图，且T为树，称T为G的支撑树。定理：G有支撑树当且仅当G为连通图；12121212121200121212(,):,( ),(,)(,)( ).,( ):,(,)( )S SS SV GSSS SSSS SE GTGTGTTTeTTeT TS SS SGe且表示 与之间的边的集合，且反树：设 为图 的支撑树，令称为 的反树。对于 的任意一条边，不连通，设其两个连通分支分别为它们所对应的点集分别为，则构成 的一个割集，记为。支撑树 000,1( ):,TGTGTeTeTeGnGC eTe Te定理：设 是图 的支撑树，则不包含 的任何割集，但对中任一条边存在唯一的割集，它包含在中。基本割集：对于 每条边 都存在 的唯一割集，这样的割集一共个，称为 的基本割集。对于中每一条边都包含唯一的回路.最小值支撑（生成）树定义：网络中权值最小的支撑树，称为该网络的最小支撑树。0( )( )( )max( )( )min( )eC eeeTGTGTew ew eTew ew e定理：设 是 的支撑树，则下面几个命题等价：（1）：是 的最小支撑树；（2）： 对任意上的边 有（3）： 对任意 上的边 有Kruskal算法 121.( )().(),0,1;2. 343.1,24. ,1;5.1 mjjw ew ew eSijG SejjjmSSeiiinG S 设若包含圈，转 ，否则转 ；令若转 ，否则停止；令并设若，则结束，这时即为所求；否则转2.Kruskal算法设G=，将G中非环边按权从小到大排序：e1, e2, , em.(1) 取e1在T中(2) 查e2，若e2与e1不构成回路，取e2也在T 中，否则弃e2.(3) 再查e3, 直到得到生成树为止. 例子所求最小生成树如所求最小生成树如图所示，图所示，W(T)=38. 求图的一棵最小生成树求图的一棵最小生成树.Dijkstra算法 12311., , ,.,2.min , , , ;3.,min ,2.tniikiikkvSkkikjjjkjTRvSv vvuwuuwuRRvSSvTTeSTvSuu w令选取若则停止，G中不存在支撑树；否则令若，则停止， 为最小支撑树；否则对于一切令转时间复杂性Kruskal算法:Dijkstra算法：2(log )O nn2()O n作业140:1,2P