离散2-13-可达关联矩阵欧拉图.ppt

-吴扬扬- 主要内容： §11.3 图的矩阵表示 2. 可达矩阵 定义: 设有向图G=V, E, V={v1, …, vn}, 则G的可达矩阵P=(pij)n?n , 其中: §11.3 图的矩阵表示 3.关联矩阵 有向图的关联矩阵 定义: 设G=V, E是有向图且没有自回路, V={v1, …, vn}, E={e1, …, em}, 则G的关联矩阵I=(aij)n?m , 其中: §11.4 欧拉图和哈密尔顿图 1. 欧拉图(1) §11.4 欧拉图和哈密尔顿图 1. 欧拉图(2) 充分性 设G是连通无向图, 若G有2个度数为奇数的顶点，则任取其一为起点构造通路; 若G无度数为奇数的顶点，则任取一个结点作为起点构造通路。 §11.4 欧拉图和哈密尔顿图 1. 欧拉图(3) 定理11.4.2 有向图G存在欧拉通路 iff G连通且所有顶点的 入度等于出度或者除两个顶点外,其余顶点的入度均等于出度， 两个特殊顶点中一个入度比出度大1，另一个出度比入度大1。 推论11.4.2 有向图G存在欧拉回路 iff G所有顶点入度等于出度。 例2： * * 图的矩阵表示 邻接矩阵 可达矩阵 关联矩阵 欧拉图 基本概念 判定定理 单位矩阵 例3: 求右图的可达矩阵。 ∴ 可达矩阵 如何判断Vi可达vj？ v1 v2 v3 v4 v5 例4： e1 e2 e3 e4 e5 e6 v1 v2 v3 v4 v5 e1 e2 e3 e4 e5 e6 -1 -1 0 0 0 0 1 1 1 -1 0 0 0 0 -1 1 0 0 0 0 0 0 1 -1 0 0 0 0 -1 1 v5 v1 v2 v3 v4 关联矩阵的性质：P233 无向图的邻接、关联矩阵定义、性质(度数, 判断孤立点和平行边) -吴扬扬- 普雷格尔河 A B C D A B C D 定义: 设G=V, E, 经过G每一条边一次且仅一次且行遍图所有顶点的通(回)路, 称为欧拉通(回)路， 存在欧拉回路的图称为欧拉图。 例1： 1 2 3 4 5 6 判定定理? 定理证明 哥尼斯堡(俄罗斯加里宁格勒)七桥问题 a b c d G=V, E V=? E=? a b c e1 e2 e3 e4 e5 be1ae2be5ce3ae4c 判定定理： 定理11.4.1 非平凡无向图G=V, E存在欧拉通路 iff G是连通的, 且有0个或2个度数为奇数的顶点。 分析例1和哥尼斯堡七桥问题。 证明：必要性 设G存在欧拉通路，则G是连通的。 设v0e1v1…vm-1emvm为G的一条欧拉通路, ∵通路中每一中间结点必关联2条边， ∴中间结点的度数必为偶数。 若v0=vm , 则端点的度数也为偶数。 若v0≠vm, 则在两端点处，v0和vm分别仅关联一条边e1和em， 两端点的度数均为奇数。 ∴ G有0个或2个度数为奇数的顶点。 则G的结点均在通路中。 设L: v0e1v1e2…vk-1ekvk,是长度最大的简单通路，则L是欧拉通路。 ∵若L不是欧拉通路， ∴ L中必有vt且边e1’=(vt,u1)不在L中。 若vt=v0或vk,则有比L更长的简单通路u1e1’v0e1v1e2…vk-1ekvk, 或v0e1v1e2…vk-1ekvke1’u1，矛盾。 ∵ G连通 否则,∵v0和vk外的顶点度数必为偶数 ∴ 还有e2’=(u1, u2)不在L中, 依次类推, 可得比L长的简单通路v0e1...vte1’u1e2’...ep’vt...vk-1ekvk, 与L是长度最大的简单通路矛盾。 ∴ L是欧拉通路。 ?例1 证明：非平凡无向图G=V,E存在欧拉通路 iff  G是连通的,且有0个或2个度数为奇数的顶点。 a b c d a b c d a b c d 作业：P234 3(2)(3) P241 2