,第十章 几种图的介绍,离散数学 陈志奎主编 人民邮电出版社,前言,自从1736年欧拉（L.Euler）利用图论的思想解决了哥尼斯堡（Konigsberg）七桥问题以来，图论经历了漫长的发展道路。在很长一段时期内，图论被当成是数学家的智力游戏，解决一些著名的难题，曾经吸引了众多的学者。图论中许多的概论和定理的建立都与解决这些问题有关。 1859年，英国数学家哈密顿发明了一种游戏：用一个规则的实心十二面体，它的20个顶点标出世界著名的20个城市，要求游戏者找一条沿着各边通过每个顶点刚好一次的闭回路，即绕行世界。用图论的语言来说，游戏的目的是在十二面体的图中找出一个生成圈。这个问题后来就叫做哈密顿问题。由于运筹学、计算机科学和编码理论中的很多问题都可以化为哈密顿问题，从而引起广泛的关注和研究。,前言,在图论的历史中，还有一个最著名的问题四色猜想。这个猜想说，在一个平面或球面上的任何地图能够只用四种颜色来着色，使得没有两个相邻的国家有相同的颜色。每个国家必须由一个单连通域构成，而两个国家相邻是指它们有一段公共的边界，而不仅仅只有一个公共点。四色猜想有一段有趣的历史。每个地图可以导出一个图，其中国家都是点，当相应的两个国家相邻时这两个点用一条线来连接。所以四色猜想是图论中的一个问题。它对图的着色理论、平面图理论、代数拓扑图论等分支的发展起到推动作用。,前言,在电子计算机问世后，图论的应用范围更加广泛，在解决运筹学、信息论、控制论、网络理论、博奕论、化学、社会科学、经济学、建筑学、心理学、语言学和计算机科学中的问题时，扮演着越来越重要的角色，受到工程界和数学界的特别重视，成为解决许多实际问题的基本工具之一。 本章将结合图论基础知识，进一步介绍一些常用的基本图类，如欧拉图、哈密尔顿图、二部图、平面图、网络等，除研究每种图类的本质特征之外，都力求结合一些实际问题来阐明图论的广泛可应用性，介绍一些最基本的图论算法，使读者对图的理论和应用这两个方面都有一定的了解。,欧拉图,主要内容,哈密尔顿图,二部图及匹配,平面图,网络,图的示例分析,10.1 欧拉图,定义10.1 图G中包含其所有边的简单开路径称为图G的欧拉路径，图G中包含其所有边的简单闭路径称为G的欧拉闭路。 图10.1 哥尼斯堡七桥 图10.2 哥尼斯堡七桥问题的图,6,10.1 欧拉图,例10.1 图10.3中（a）是欧拉闭路，（c）是欧拉路径，（b）既不是欧拉路径也不是欧拉闭路。 图10.3,7,10.1 欧拉图,定义10.2 每个结点都是偶结点的连通无向图称为欧拉图。每个结点的出度和入度相等的连通有向图称为欧拉有向图。 例10.2 图10.4中（b）是欧拉有向图。 图10.4,8,10.1 欧拉图,定理10.1 设G是连通无向图，G是欧拉图，当且仅当G有欧拉闭路。,9,10.1 欧拉图,定理10.2 设G=为连通无向图，且 ， ，则G有一条从 至 的欧拉路径当且仅当G恰有两个奇结点 和 。,10,10.1 欧拉图,定理10.3 设G为弱连通的有向图。G是欧拉有向图，当且仅当G有欧拉闭路。 定理10.4 设G为弱连通有向图。 和 为G的两个不同结点。G有一条从 至 的欧拉路径，当且仅当 = +1， = -1，且对G的其他结点v有 =,11,10.1 欧拉图,定理10.5 如果 和 是可运算的欧拉图，则 是欧拉图。 由定理10.5可得图10.5 图10.5,12,欧拉图,主要内容,哈密尔顿图,二部图及匹配,平面图,网络,图的示例分析,10.2 哈密尔顿图,爱尔兰数学家哈密尔顿（William Hamilton）爵士1859年提出了一个“周游世界”的游戏。这个游戏把一个正十二面体的二十个顶点看成地球上的二十个城市。棱线看成是连接城市的航路（航空、航海线或陆路交通线），要求游戏者沿棱线走，寻找一条经过所有结点（即城市）一次且仅一次的回路，如图10.6（a）所示。也就是在图10.6（b）中找一条包含所有结点的圈。图（b）中的粗线所构成的圈就是这个问题的回答。 与欧拉图不同，哈密尔顿图是遍历图中的每个结点， 一条哈密尔顿回路不会在两个结点间走两次以上，因此没有必要在有向图中讨论。,14,图10.6,10.2 哈密尔顿图,爱尔兰数学家哈密尔顿（William Hamilton）爵士1859年提出了一个“周游世界”的游戏。这个游戏把一个正十二面体的二十个顶点看成地球上的二十个城市。棱线看成是连接城市的航路（航空、航海线或陆路交通线），要求游戏者沿棱线走，寻找一条经过所有结点（即城市）一次且仅一次的回路，如图10.6（a）所示。也就是在图10.6（b）中找一条包含所有结点的圈。图（b）中的粗线所构成的圈就是这个问题的回答。 与欧拉图不同，哈密尔顿图是遍历图中的每个结点， 一条哈密尔顿回路不会在两个结点间走两次以上，因此没有必要在有向图中讨论。,15,图10.6,10.2 哈密尔顿图,定义10.3 给定无向图G，图G中包含其所有顶点的简单开路径称为图G的哈密尔顿路径，图G中包含其所有顶点的简单闭路径称为G的哈密尔顿回路。具有哈密顿回路的图称为哈密尔顿图。 由定义可知哈密尔顿圈与哈密尔顿路通过图G中的每个结点一次且仅一次，例如图10.6（b）就是哈密尔顿图（哈密尔顿圈用实线标出）。,16,10.2 哈密尔顿图,例10.3 图10.7中，图（a）、（b）中有哈密尔顿圈，图（c）中有哈密尔顿路，（d）中既没有哈密尔顿圈也没有哈密尔顿路。 图10.7 哈密尔顿图和欧拉图相比，虽然考虑的都是遍历问题，但是侧重点不同。欧拉图遍历的是边，而哈密尔顿图遍历的是结点。另外两者的判定困难程度也不一样，前面我们已经给出了判定欧拉图的充分必要条件，但对于哈密尔顿图的判定，至今还没有找出判定的充要条件，只能给出若干必要条件或充分条件。,17,10.2 哈密尔顿图,定理10.6 若 G 是哈密尔顿图，则对于结点集 的任一非空真子集 有 。其中 表示在 G中删去 S中的结点后所构成的图， 表示 的连通分支数。,18,哈密尔顿图的必要条件可用来判定某些图不是哈密尔顿图，只要能够找到不满足定理条件的结点集 V的非空子集 S。,10.2 哈密尔顿图,例10.4 图10.8（a）不是哈密尔顿图。 图10.8（a）中共有9个结点，如果取结点集S=3个白点，即 。而这时 （如图（b）。这说明图10.8（a）不是哈密尔顿图。但要注意若一个图满足定理10.6的条件也不能保证这个图一定是哈密尔顿图，如图10.8（c）。,19,图10.8,10.2 哈密尔顿图,定理10.7 设图 G是具有n（3）个结点的无向简单图，如果 G中每一对结点度数之和大于等于n-1，则在 G 中存在一条哈密尔顿路。 定理10.8 若G是具有n（3）个结点的无向简单图，对于G中每一对不相邻的结点 均有 ，则G是一个哈密尔顿图。 定理10.7和10.8都是充分条件，即满足这些条件的图一定是哈密尔顿图。但不是所有的哈密尔顿图都满足这些条件。例如图10.9是哈密尔顿图,但它不满足上述定理的条件。,20,图10.9,10.2 哈密尔顿图,例10.5 某地有5个风景点。 若每个景点均有两条道路与其它景点相通，问是否可经过每个景点恰好一次而游完这5处？ 解：将景点作为结点，道路作为边，则得到一个有5个结点的无向图。 由题意，对每个结点 ，有 则对任两点 ， 均有 可知此图一定有一条哈密尔顿路，本题有解。,21,10.2 哈密尔顿图,例10.6 今有 和 7人，已知下列事实。 a讲英语； b讲英语和汉语； c讲英语、意大利语和俄语； d讲日语和汉语； e讲德国和意大利语； f讲法语、日语和俄语； g讲法语和德语。 试问这7个人应如何排座位，才能使每个人都能和他身边的人交谈？,22,解：设无向图 ，其中 图G是连通图，如图10.10（a）所示。将这7个人排座围圆桌而坐，使得每个人能与两边的人交谈，即在图10.10（a）中找哈密尔顿回路。经观察该回路是 。即按照图10.10（b）安排座位即可。,欧拉图,主要内容,哈密尔顿图,二部图及匹配,平面图,网络,图的示例分析,10.3 二部图及匹配,定义10.4 设无向图G=。如果存在V的划分 , ，使得 中的任何两个结点都不相邻（i=1,2），则称G为二部图， 和 称为G的互补结点子集。 显然，二部图没有自圈。与二部图的一条边关联的两个结点一定分属于两个互补结点子集。一般来说，二部图的互补结点子集的划分不是唯一的。如图10.11的二部图， 和 是它的互补结点子集， 和 也是它的互补结点子集。 图10.11 二部图,24,10.3 二部图及匹配,一个无向图如果能画成上面的样式，很容易判定它是二部图。有些图虽然表面上不是上面的样式，但经过改画就能成为上面的样式，仍可判定它是一个二部图，如图10.12中（a）可改画成图（b），图（c）可改画成图（d）。可以看出，它们仍是二部图。 图10.12,25,10.3 二部图及匹配,定理10.9 设G是阶大于1的无向图。G是二部图，当且仅当G的所有回路长度均为偶数。 定义10.5 设 和 是简单二部图G的互补结点子集，如果 中的每个结点与 中的每个结点相邻，则称G为完全二部图。 我们把互补结点子集分别包含m和n个结点的完全二部图记为 。图10.14画出了 的两个图示。 很重要，我们在讨论图的平面性时还要用到它。,26,10.3 二部图及匹配,二部图的主要应用是匹配，“匹配”是图论中的一个重要内容，它在所谓“人员分配问题”和“最优分配问题”等运筹学中的问题上