图论第04讲课件.ppt

图论Graphic Theory 内容回顾 握手定理及其推论； Euler回路： (1)判别定理（充要条件）及推论； (2)Fleury算法； Hamilton回路： (1) Hamilton道路判别定理（充分条件）； (2) Hamilton回路判别定理（充分条件）。 第一章 图的基本概念 §1 引论 §2 图的概念 §3 道路和回路 §4 图的矩阵表示法 §5 中国邮路问题 §6 平面图 §4 图的矩阵表示法 §4 图的矩阵表示法 定义：对于图G=(V,E)，构造一个矩阵 其中n＝|V|； §4 图的矩阵表示法－1 置换矩阵：相当于将单位矩阵中相应的行与行，或者列与列互换的矩阵。 §4 图的矩阵表示法－2 邻接矩阵中图的性质： §4 图的矩阵表示法－3 §4 图的矩阵表示法－4 (3) B=A2。 §4 图的矩阵表示法－5 (4) 有向图中：C=AAT。 §4 图的矩阵表示法－6 (5) 有向图中：D=ATA。 图的同构 定义：若两个图顶点数相同且相对应，对应顶点之间的边也相对应，则称两个图同构。 G1＝(V1,E1)， G2＝(V2,E2)，G1－G2 ?若u1,v1∈V1， u2,v2∈V2，u1 －u2， v1 －v2，则(u1,v1) ∈E1－ (u2,v2) ∈E2。 图的同构-1 图的同构-2 判别定理：图G1 ，G2同构的充要条件是：存在置换矩阵P，使得：A1＝PA2P。 其中A1，A2分别是G1 ，G2的邻接矩阵。 如何判断两图同构是图论中一个困难问题。 课堂练习 1、判断下面两图是否同构，若同构写出对应关系，若不同构则写出理由。 §5 中国邮路问题 中国邮路问题(Chinese postman problem)， 是我国数学家管梅谷于1960年首次提出的。 问题描述： 设邮递员从邮局出发，遍历他所管辖的每一条街道，将信件送到后返回邮局，求所走的路径最短。 §5 中国邮路问题－1 中国邮路问题的图论模型为： 设G=(V,E)是连通图，而且对于所有的e∈E都赋以权c(e)≥0，求从点v0∈V出发，通过所有边至少一次最后返回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*) 中国邮路构造算法 设已经知道度为奇数的顶点为v1,v2,…,v2h 第一步：添加重复边：i从1到h，引从v2i-1到v2i的链Pi，并对Pi的每条边附加1条重复边； 第二步：检查重复边：检查图G的每条边，使得每条边最多有1条重复边，得到图G’，G’中重复边集记为E(0)； 中国邮路构造算法－1 第三步：设初值k＝0； 例子1－2 求出下图中以v1为起点的一条中国邮路。 例1-2解 解：其中v2，v3，v4，v5，v6，v7顶点的度都是奇数，引入重复边。 第一步：添加重复边： i从1到h，引从v2i-1到v2i的链Pi，并对Pi的每条边附加1条重复边； 例1-2解-1 下面看回路 ：v2-v3-v7-v2 其中E( )={(v2,v3),(v2,v7),(v3,v7)} 例1-2解-2 例1-2解-2 例1-2解-2 最后利用Fleury算法求出一个Euler回路： v1-v2-v3-v4-v3-v7-v2-v7-v4-v5-v7-v6-v5-v6-v1 代价一共是：41 课堂练习 求下图中一条中国邮路： * * 阙夏制作 1 (vi,vj)∈E； 称A是图G的邻接矩阵。 0 否则； 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 ＝ a