资源描述：
《图论第04讲.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、图论GraphicTheory阙夏制作内容回顾握手定理及其推论；Euler回路：(1)判别定理（充要条件）及推论；(2)Fleury算法；Hamilton回路：(1)Hamilton道路判别定理（充分条件）；(2)Hamilton回路判别定理（充分条件）。第一章图的基本概念§1引论§2图的概念§3道路和回路§4图的矩阵表示法§5中国邮路问题§6平面图§4图的矩阵表示法§4图的矩阵表示法定义：对于图G=(V,E)，构造一个矩阵其中n＝
2、V
3、；1(vi,vj)∈E；称A是图G的邻接矩阵。0否则；§4图的矩阵表示法－1置换矩阵：相当于将单位矩阵中相应的行与行，或者列与
4、列互换的矩阵。100001010P＝a11a12a13a21a22a23a31a32a33A＝a11a12a13a31a32a33a21a22a23PA＝a11a13a12a31a33a32a21a23a22(PA)P＝P就是一个置换矩阵§4图的矩阵表示法－2邻接矩阵中图的性质：v1v2v3v40110101111000100A＝无向图的邻接矩阵是对称的！(1)A=(αij)n×n中，第i行或第i列中非0元素的个数等于顶点vi的度。(无向图)§4图的矩阵表示法－3v4v1v2v30110000101011010A＝竖入横出(2)A=(αij)n×n中，第i列中非
5、0元素的个数等于顶点vi的入度，第i行中非0元素的个数等于顶点vi的出度。(有向图)§4图的矩阵表示法－4(3)B=A2。a11a12…a1na21a22…a2n……an1an2…annB=A2=a11a12…a1na21a22…a2n……an1an2…ann×＝(bij)n×nbij表示vi两步到达vj的路径数目§4图的矩阵表示法－5(4)有向图中：C=AAT。a11a12…a1na21a22…a2n……an1an2…annC=(cij)=a11a21…an1a12a22…an2……a1na2n…ann×cij表示以vi,vj为始点的终点数目。cij=∑αik
6、αjkvivjvk§4图的矩阵表示法－6(5)有向图中：D=ATA。a11a12…a1na21a22…a2n……an1an2…annD=(cij)=a11a21…an1a12a22…an2……a1na2n…ann×dij表示以vi,vj为终点的始点数目。dij=∑αikαjkvivjvk图的同构定义：若两个图顶点数相同且相对应，对应顶点之间的边也相对应，则称两个图同构。G1＝(V1,E1)，G2＝(V2,E2)，G1<－>G2若u1,v1∈V1，u2,v2∈V2，u1<－>u2，v1<－>v2，则(u1,v1)∈E1<－>(u2,v2)∈E2。v1v2v3v4
7、vavbvcvd图的同构-1v1v2v3v4图G1vavbvcvd图G20111101111011110A1＝12340111101111011110A2＝abcdv1<->vav2<->vbv3<->vcv4<->vd图的同构-2判别定理：图G1，G2同构的充要条件是：存在置换矩阵P，使得：A1＝PA2P。其中A1，A2分别是G1，G2的邻接矩阵。如何判断两图同构是图论中一个困难问题。课堂练习1、判断下面两图是否同构，若同构写出对应关系，若不同构则写出理由。12345e1e2e3e4e5e6e7图1abcdek1k2k3k4k5k6k7图2》》§5中国邮路问题
8、中国邮路问题(Chinesepostmanproblem)，是我国数学家管梅谷于1960年首次提出的。问题描述：设邮递员从邮局出发，遍历他所管辖的每一条街道，将信件送到后返回邮局，求所走的路径最短。§5中国邮路问题－1中国邮路问题的图论模型为：设G=(V,E)是连通图，而且对于所有的e∈E都赋以权c(e)≥0，求从点v0∈V出发，通过所有边至少一次最后返回v0的回路C，使得达到最小。邮局v1v2v3v4v5v634521426351v0§5中国邮路问题－2问题分析：（1）如果道路正好是一个Euler图，则容易求解，用Fleury算法求出一个Euler回路即可；（
9、2）如果不是Euler图，则加上如干重复边，使之变成Euler图，然后求Euler回路。现在问题的关键：如何加重复边！中国邮路问题是Euler回路的近似求解。§5中国邮路问题－3定理：设E*E是使W(E*)=达到最小的重复边集合，当且仅当对于Ga图的任一回路，恒有W(∩E*)≤W(E()-E*)E*是重复边集合Ga是加重复边以后的Euler图E*={(v2,v3)}E(C)={(v1,v2),(v1,v3)(v2,v3)(v2,v4)(v3,v4)}v1v3v23234v42中国邮路构造算法设已经知道度为奇数的顶点为v1,v2,…,v2h第一步：添加重复边：i从
10、1到h，引从v2i-1到
