高等学校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