人民邮电出版社：高等学校21世纪教材《离散数学》电子教案（PPT课件）第十一章 几类重要的图

高等学校21卌纪教材 第1一章几类重要的图 11.1欧拉图与哈密尔顿图 11.2二部图 11.3树 11.4平面图 PT PRESS 人民邮电出版社 退出

第十一章 几类重要的图 11.1 欧拉图与哈密尔顿图 11.2 二部图 11.3 树 11.4 平面图 退出

高等学校21卌纪教材 11.1欧拉图与哈尔顿图 1736年瑞士数学家欧拉发表了图论的第 篇著名论文“哥尼斯堡七桥问题”(下称七桥问 题)。这个问题是这样的:哥尼斯堡城有一条横 贯全城的普雷格尔河,城的各部分用七桥联结, 每逢节假日,有些城市居民进行环城周游,于 是便产生了能否“从某地出发,通过每桥恰好 次,在走遍了七桥后又返回到原处”的问题。 PT PRESS 人民邮电出版社

11.1 欧拉图与哈密尔顿图 1736年瑞士数学家欧拉发表了图论的第一 篇著名论文“哥尼斯堡七桥问题”(下称七桥问 题)。这个问题是这样的：哥尼斯堡城有一条横 贯全城的普雷格尔河，城的各部分用七桥联结， 每逢节假日，有些城市居民进行环城周游，于 是便产生了能否“从某地出发，通过每桥恰好 一次，在走遍了七桥后又返回到原处”的问题

高等学校21卌纪教材 在图111.1画出了哥尼斯堡城图,城的四块 陆地部分以A,B,C,和D标记。欧拉巧妙地把 哥尼斯堡城图化为图111.2所示图G,他把陆地 设为图G中的结点,把桥画成相应地联结陆地即 结点的边。于是,通过哥尼斯堡城中每座桥恰 好一次问题,等价于在图G中从某一结点出发找 出一条链,它通过每条边恰好一次后回到原出 发结点,亦即等价于在图G中寻找一个圈,它通 过G中每一条边恰好一次。 PT PRESS 人民邮电出版社

在图11.1.1画出了哥尼斯堡城图，城的四块 陆地部分以A，B，C，和D标记。欧拉巧妙地把 哥尼斯堡城图化为图11.1.2所示图G，他把陆地 设为图G中的结点，把桥画成相应地联结陆地即 结点的边。于是，通过哥尼斯堡城中每座桥恰 好一次问题，等价于在图G中从某一结点出发找 出一条链，它通过每条边恰好一次后回到原出 发结点，亦即等价于在图G中寻找一个圈，它通 过G中每一条边恰好一次

高等学校21卌纪教材 B C D 图111.1 PT PRESS 人民邮电出版社

图 11.1.1

A B C 图1112 PT PRESS 人民邮电出版社

图 11.1.2

高等学校21卌纪教材 欧拉在这篇论文中提出了一条简单准则, 确定七桥问题是不能解的。下面就来讨论这个 问题。 定义1.1图G中的一圈(或回路),若它通 G中的每一条边(或弧)恰好一次,则称该圈(或回 路)为欧拉圈(或回路),具有这种圈(或回路)的图 称为欧拉无向(或有向)图。 定理1.1给定连通无向图G,G有欧拉圈 台G中每个结点都是偶度结点 PT PRESS 人民邮电出版社

欧拉在这篇论文中提出了一条简单准则， 确定七桥问题是不能解的。下面就来讨论这个 问题。 定义11.1.1 图G中的一圈(或回路)，若它通 G中的每一条边(或弧)恰好一次，则称该圈(或回 路)为欧拉圈(或回路)，具有这种圈(或回路)的图 称为欧拉无向(或有向)图。 定理11.1.1 给定连通无向图G，G有欧拉圈 G中每个结点都是偶度结点

高等学校21卌纪教材 由定义1.1.可知,具有欧拉圈的图 是欧拉图,故图G为欧拉图G中每个结 点都是偶度结点。 由于七桥问题所对应的图中每个结点 都是奇度结点,根据上述定理可知,七桥 问题无解。 PT PRESS 人民邮电出版社

由定义11.1.1可知，具有欧拉圈的图 是欧拉图，故图G为欧拉图G中每个结 点都是偶度结点。 由于七桥问题所对应的图中每个结点 都是奇度结点，根据上述定理可知，七桥 问题无解

高等学校21卌纪教材 定义1..2图G中的一条链(或路),若它通 过G中的每条边(或弧)恰好一次,则称该链(或路) 为欧拉链(或路) 定理11.1.2给定连通无向图G=,u, v∈T且≠v,u与v间存在欧拉链>G中仅有u和v 为奇度结点。 PT PRESS 人民邮电出版社

定义11.1.2 图G中的一条链(或路)，若它通 过G中的每条边(或弧)恰好一次，则称该链(或路) 为欧拉链(或路)。 定理11.1.2 给定连通无向图G=，u， v∈V且u≠v，u与v间存在欧拉链G中仅有u和v 为奇度结点

高等学校21卌纪教材 定理1..3给定弱连通有向图G,G有欧拉 回路G中的每个结点的入度等于出度。 定理11.4给定弱连通有向图G=, u,v∈且nv,u与在欧拉路令→G中唯有u和 v的入度不等于出度,且u的入度比其出度大于1 和的出度比其入度小于1(或者反之)。 PT PRESS 人民邮电出版社

定理11.1.3 给定弱连通有向图G，G有欧拉 回路G中的每个结点的入度等于出度。 定理11.1.4 给定弱连通有向图G=， u，v∈V且u≠v，u与v存在欧拉路G中唯有u和 v的入度不等于出度，且u的入度比其出度大于1 和v的出度比其入度小于1(或者反之)

高等学校21卌纪教材 这两个定理的证明,可以看作是关于无向 图的欧拉圈和欧拉链的推广。因为对于有向图 的任意一个结点来说,如果入度与出度相等, 则该结点为偶度结点;如果入度与出度之差为1 时,该结点必是奇度结点,所以定理1.13和 1414与前面两个定理的证明类似。 PT PRESS 人民邮电出版社

这两个定理的证明，可以看作是关于无向 图的欧拉圈和欧拉链的推广。因为对于有向图 的任意一个结点来说，如果入度与出度相等， 则该结点为偶度结点；如果入度与出度之差为1 时，该结点必是奇度结点，所以定理11.1.3和 14.1.4与前面两个定理的证明类似