编图论.ppt

每条边都是无向边的图称为无向图；每条边都是有向边的图称为有向图；在一个图中如果一些边是无向边，另一些边是有向边，则称这个图为混合图。 如G = V, E其中V = {v1,v2,v3,v4}E={v1,v2,v2,v1,v2,v3,(v1,v1),(v1,v3),(v3,v4)} 3.1.2 图的基本概念与握手定理定义2 1. 在无向图G=V,E中与结点v关联的边的条数(自回路算两条边)，称为该点的度数，记为deg(v)。2. 在有向图G=V,E中以结点v为始点的边的条数称为该点的出度，记为deg+(v)；以结点v为终点的边的条数称为该点的入度，记为 deg－(v)。 定理1(握手定理) 图G=V,E中，结点度数之和等于边数的两倍，即 定理2 在有向图中，所有结点的入度之和等于所有结点的出度之和。 3.1.4 通路与回路 有边重复出现的通路称为复杂通路；有边重复出现的回路称为复杂回路。 v3e8v4e7v5e2v1e1v2是？ 定理3 在一个具有n个结点的图中，如果从结点vi到vj存在一条通路，则从vi到vj存在一条长度不超过n－1的通路。 3.2 图的连通性3.2.1 连通性 结点间的连通关系是等价关系，其等价类V1,V2,...,Vm是V的一个划分，子图G(V1), G(V2),..., G(Vm)称为图G的连通分支，通常用W(G)来表示G中连通分支的个数。 定义13 设u与v是图G的两个结点，若u与v连通，则称u与v间最短的路为u与v之间的短程线，短程线的长度可作为结点u与v间的距离，记作d(u,v)，其满足下列性质： d(u,v)≥0, d(u,u)=0 (非负性) d(u,v)=d(v,u) （对称性） d(u,v)+d(v,w) ≥ d(u,w) （三角不等式）若u与v不连通，d(u,v)=∞。 无向图的连通性不能直接推广到有向图，有向图的可达性不是等价关系。若u可达v, 其最短路的长度称为u与v间的距离，记作du,v, 其满足下列性质： (1) du,v≥0 (2) du,u=0 (3) du,v+dv,w≥du,w (4) 若u不可达v, 则记du,v=∞ (5) 若u可达v ,且v可达u时,du,v不一定等于dv,u。 定义14 在有向图D中，任何一对结点间，至少有一个结点可达另一个结点，则称该图为单侧连通的。如果图D的任何一对结点间都互相可达，称该图为强连通的。如果略去D中各边的方向成为无向图后是连通的，则称该图是弱连通的。 定理5 有向图强连通?存在经过每个结点一次的回路。 定义16 设无向图G=V,E ，若存在结点集V?V,使图G删除V后，所得子图G－V的连通分支数W(G－V)W(G)，而删除任何V?V，都有W(G－V)=W(G)，则称V为G的一个点割集，只有一个结点的点割集，称该点为割点。 定义17 设无向图G=V,E ，若存在边集E?E,使图G删除E后，所得子图G－E的连通分支数W(G－E)W(G)，而删除任何E?E，都有 W(G－E)=W(G)，则称E为G的一个边割集，只有一边的边割集，称该边为割边或桥。 定义18 设G为无向连通图?(G) = min{|V||V是G的点割集或G-V为平凡图}称?(G)为G的点连通度或连通度。 定义19 设G为无向连通图 ?(G) = min{|E| | E是G的边割集}称?(G)为G的边连通度。 定理9 无向图中：?(G)≤?(G)≤?(G). 定理10 一个连通无向图G中的结点v是割点的充分必要条件是：存在两个结点u与w,使得结点u与v的每一条路都通过v。 3.4 最短路径 3.4.2 狄克斯特拉(Dijkstra)算法 例1 求下图a到z的最短通路 v1 v7 v2 v3 G v6 v5 v4 {(v1,v2)(v3,v4)},{(v2,v3)(v1,v4)}, {(v4,v5)(v5,v6)},{(v6,v7)}为四个边割集。 (v6,v7)为一条割边。 {(v5,v6)(v6,v7)},{(v4,v5)(v6,v7)}不是边割集。 由定义可知： 若G是平凡图，则V=?，∴?(G) = 0； ?(Kn) = n－1； 若图G存在割点，则?(G) = 1； 若G是非连通图，则?(G) = 0。 由定义可知： 若G是平凡图，则E=?，∴?(G) = 0； 若图G存在割边，则?(G) = 1； 若G是非连通图，则?(G) = 0。 证：若G为非连通图,有?(G)=?(G)=?(G)=0.否则 (1)∵每点的关联边必包含一边割集∴?(G)≤?(G). (