图论第04讲.ppt

1、图论Graphic Theory,阙夏制作,内容回顾,握手定理及其推论； Euler回路： (1)判别定理（充要条件）及推论； (2)Fleury算法； Hamilton回路： (1) Hamilton道路判别定理（充分条件）； (2) Hamilton回路判别定理（充分条件）。,第一章 图的基本概念,1 引论 2 图的概念 3 道路和回路 4 图的矩阵表示法 5 中国邮路问题 6 平面图,4 图的矩阵表示法,4 图的矩阵表示法,定义：对于图G=(V,E)，构造一个矩阵 其中n|V|；,1 (vi,vj)E；,称A是图G的邻接矩阵。,0 否则；,4 图的矩阵表示法1,置换矩阵：相当于将单位矩阵

2、中相应的行与行，或者列与列互换的矩阵。,1 0 0 0 0 1 0 1 0,P ,a11 a12 a13 a21 a22 a23 a31 a32 a33,A ,a11 a12 a13 a31 a32 a33 a21 a22 a23,PA ,a11 a13 a12 a31 a33 a32 a21 a23 a22,(PA)P ,P就是一个置换矩阵,4 图的矩阵表示法2,邻接矩阵中图的性质：,无向图的邻接矩阵是对称的！,(1)A=(ij)nn中，第i行或第i列中非0元素 的个数等于顶点vi的度。(无向图),4 图的矩阵表示法3,竖入横出,(2) A=(ij)nn中，第i列中非0元素的个数等于 顶点v

3、i的入度，第i行中非0元素的个数等于顶点 vi的出度。(有向图),4 图的矩阵表示法4,(3) B=A2。,bij表示vi两步到达vj的路径数目,4 图的矩阵表示法5,(4) 有向图中：C=AAT。,cij表示以vi,vj为始点的终点数目。,cij=ik jk,4 图的矩阵表示法6,(5) 有向图中：D=ATA。,dij表示以vi,vj为终点的始点数目。,dij=ik jk,图的同构,定义：若两个图顶点数相同且相对应，对应顶点之间的边也相对应，则称两个图同构。 G1(V1,E1)， G2(V2,E2)，G1G2 若u1,v1V1， u2,v2V2，u1 u2， v1 v2，则(u1,v1) E

4、1 (u2,v2) E2。,图的同构-1,图的同构-2,判别定理：图G1 ，G2同构的充要条件是：存在置换矩阵P，使得：A1PA2P。 其中A1，A2分别是G1 ，G2的邻接矩阵。 如何判断两图同构是图论中一个困难问题。,课堂练习,1、判断下面两图是否同构，若同构写出对应关系，若不同构则写出理由。,5 中国邮路问题,中国邮路问题(Chinese postman problem)， 是我国数学家管梅谷于1960年首次提出的。 问题描述： 设邮递员从邮局出发，遍历他所管辖的每一条街道，将信件送到后返回邮局，求所走的路径最短。,5 中国邮路问题1,中国邮路问题的图论模型为： 设G=(V,E)是连通图

5、，而且对于所有的eE都赋以权c(e)0，求从点v0V出发，通过所有边至少一次最后返回v0的回路C，使得 达到最小。,5 中国邮路问题2,问题分析： （1）如果道路正好是一个Euler图，则容易求解，用Fleury算法求出一个Euler回路即可； （2）如果不是Euler图，则加上如干重复边，使之变成Euler图，然后求Euler回路。 现在问题的关键：如何加重复边！ 中国邮路问题是Euler回路的近似求解。,5 中国邮路问题3,定理：设E* E是使W(E*)= 达到最小 的重复边集合，当且仅当对于Ga图的任一回 路 ，恒有W( E*)W(E( )-E*),E*是重复边集合,Ga是加重复边以后的

6、Euler图,E*=(v2,v3) E(C)=(v1,v2),(v1,v3)(v2,v3 )(v2,v4 )(v3,v4),中国邮路构造算法,设已经知道度为奇数的顶点为v1,v2,v2h 第一步：添加重复边：i从1到h，引从v2i-1到v2i的链Pi，并对Pi的每条边附加1条重复边； 第二步：检查重复边：检查图G的每条边，使得每条边最多有1条重复边，得到图G，G中重复边集记为E(0)；,中国邮路构造算法1,第三步：设初值k0；,(a)若E(k)对于回路 有 ，则,E(k1)=E(k) E( )，kk1，转(a)；,(b)输出E(k)， E(k)便是最优集。,第四步：用Fleury算法求出Elu

7、er回路。,例子12,求出下图中以v1为起点的一条中国邮路。,v1,v2,v3,v4,v6,v5,v7,5,1,3,2,2,3,2,5,4,3,3,例1-2解,解：其中v2，v3，v4，v5，v6，v7顶点的度都是奇数，引入重复边。 第一步：添加重复边： i从1到h，引从v2i-1到v2i的链Pi，并对Pi的每条边附加1条重复边；,v1,v2,v3,v4,v6,v5,v7,5,1,3,2,2,3,2,5,4,3,3,E(0)=(v2,v3),(v4,v5),(v6,v7),第二步：检查重复边：检查图G的每条边，使得每 条边最多有1条重复边，得到图G，G中重复边集 记为E(0)；,例1-2解-1

8、,下面看回路 ：v2-v3-v7-v2 其中E( )=(v2,v3),(v2,v7),(v3,v7),v1,v2,v3,v4,v6,v5,v7,5,1,3,2,2,3,2,5,4,3,3,E(0)=(v2,v3),(v4,v5),(v6,v7), 5 224, E(1)E(0) E( )(v2,v7),(v3,v7),(v4,v5),(v6,v7),例1-2解-2,v1,v2,v3,v4,v6,v5,v7,5,1,3,2,2,3,2,5,4,3,3,E(1)= (v2,v7),(v3,v7),(v4,v5),(v6,v7),下面看回路 ： v4-v5-v6-v7-v4 其中E( )=(v4,v

9、7),(v4,v5),(v5,v6 ),(v6,v7), 437 235, E(2)E(1) E( )(v2,v7),(v3,v7),(v4,v7),(v5,v6),例1-2解-2,v1,v2,v3,v4,v6,v5,v7,5,1,3,2,2,3,2,5,4,3,3,E(2)= (v2,v7),(v3,v7),(v4,v7),(v5,v6),下面看回路 ： v3-v4-v7-v3 其中E( )=(v3,v4),(v4,v7),(v3,v7), E(3)E(2) E( )(v2,v7),(v3,v4),(v5,v6), 224 3,例1-2解-2,最后利用Fleury算法求出一个Euler回路： v1-v2-v3-v4-v3-v7-v2-v7-v4-v5-v7-v6-v5-v6-v1 代价一共