离散数学 陈志奎 第十章 几种图的介绍

《离散数学 陈志奎 第十章 几种图的介绍》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十章几种图的介绍离散数学陈志奎主编人民邮电出版社前言自从1736年欧拉（L.Euler）利用图论的思想解决了哥尼斯堡（Konigsberg）七桥问题以来，图论经历了漫长的发展道路。在很长一段时期内，图论被当成是数学家的智力游戏，解决一些著名的难题，曾经吸引了众多的学者。图论中许多的概论和定理的建立都与解决这些问题有关。1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即「绕行世界」。用图论的语言来说，游戏的目的是在

2、十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的关注和研究。前言在图论的历史中，还有一个最著名的问题——四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。四色猜想有一段有趣的历史。每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中

3、的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。前言在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、博奕论、化学、社会科学、经济学、建筑学、心理学、语言学和计算机科学中的问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。本章将结合图论基础知识，进一步介绍一些常用的基本图类，如欧拉图、哈密尔顿图、二部图、平面图、网络等，除研究每种图类的本质特征之外，都力求结合一些实际问题来阐明图论的广泛可应用性，介绍一些最基本的图论

4、算法，使读者对图的理论和应用这两个方面都有一定的了解。PART01欧拉图主要内容PART02哈密尔顿图PART03二部图及匹配PART04平面图PART05网络PART06图的示例分析10.1欧拉图定义10.1图G中包含其所有边的简单开路径称为图G的欧拉路径，图G中包含其所有边的简单闭路径称为G的欧拉闭路。图10.1哥尼斯堡七桥图10.2哥尼斯堡七桥问题的图610.1欧拉图例10.1图10.3中（a）是欧拉闭路，（c）是欧拉路径，（b）既不是欧拉路径也不是欧拉闭路。图10.3710.1欧拉图定义10.2每个结点都是偶结点的连通无

5、向图称为欧拉图。每个结点的出度和入度相等的连通有向图称为欧拉有向图。例10.2图10.4中（b）是欧拉有向图。图10.4810.1欧拉图定理10.1设G是连通无向图，G是欧拉图，当且仅当G有欧拉闭路。910.1欧拉图定理10.2设G=为连通无向图，且，，则G有一条从至的欧拉路径当且仅当G恰有两个奇结点和。1010.1欧拉图定理10.3设G为弱连通的有向图。G是欧拉有向图，当且仅当G有欧拉闭路。定理10.4设G为弱连通有向图。和为G的两个不同结点。G有一条从至的欧拉路径，当且仅当=+1，=-1，且对G的其他结点v有=1

6、110.1欧拉图定理10.5如果和是可运算的欧拉图，则是欧拉图。由定理10.5可得图10.5图10.512PART01欧拉图主要内容PART02哈密尔顿图PART03二部图及匹配PART04平面图PART05网络PART06图的示例分析10.2哈密尔顿图爱尔兰数学家哈密尔顿（WilliamHamilton）爵士1859年提出了一个“周游世界”的游戏。这个游戏把一个正十二面体的二十个顶点看成地球上的二十个城市。棱线看成是连接城市的航路（航空、航海线或陆路交通线），要求游戏者沿棱线走，寻找一条经过所有结点（即城市）一次且仅一次的回路

7、，如图10.6（a）所示。也就是在图10.6（b）中找一条包含所有结点的圈。图（b）中的粗线所构成的圈就是这个问题的回答。与欧拉图不同，哈密尔顿图是遍历图中的每个结点，一条哈密尔顿回路不会在两个结点间走两次以上，因此没有必要在有向图中讨论。14图10.610.2哈密尔顿图爱尔兰数学家哈密尔顿（WilliamHamilton）爵士1859年提出了一个“周游世界”的游戏。这个游戏把一个正十二面体的二十个顶点看成地球上的二十个城市。棱线看成是连接城市的航路（航空、航海线或陆路交通线），要求游戏者沿棱线走，寻找一条经过所有结点（即城市）

8、一次且仅一次的回路，如图10.6（a）所示。也就是在图10.6（b）中找一条包含所有结点的圈。图（b）中的粗线所构成的圈就是这个问题的回答。与欧拉图不同，哈密尔顿图是遍历图中的每个结点，一条哈密尔顿回路不会在两个结点间走两次以上，因此没有必要在有向图中讨论。15