第七章特殊图.

第七章特殊图引言7.1欧拉图7.2哈密尔顿图7.3二部图7.4平面图7.5无向树7.6根树7.7图的应用引言在第六章中，我们定义了图及图论中的基本概念。图实际上是一个抽象的系统，是从现实中各种各样的具体的系统出发，经过高度概括而形成的。在本章，我们将在第六章的基础上，进一步讨论一些结构特殊的图。这些图反映了某些特殊系统的最根本的系统特性，它们在物理学、化学、建筑学、电子学、人文学、系统科学、计算机科学等诸多学科中有着广泛的应用。图论中主要讨论欧拉图、哈密尔顿图、二部图、平面图、无向树和树等六种特殊图。7.1欧拉图一、问题的提出欧拉图的概念来源于欧洲一个古老的难题---哥尼斯堡七桥问题。哥尼斯堡（Konicberg）是东普鲁士的一座城，第二次世界大战后划归苏联，现名加里宁格勒，属俄罗斯。普雷格尔（Pregel）河流经这个城市，具体如下图（左）所示。其中A，B是河的两岸，C，D是河中的两个孤岛。C，D两岛与两岸以及彼此之间由七座桥连接。针对哥尼斯堡城的地理情况，有人提出了这样一个问题：能否从该城的某片陆地开始行走，要求不重复地通过每座桥一次，最后刚好回到出发点？显然，要解决这个问题，若问题有解，就必须确切指出一条满足要求的行走路线来，否则则要严格地证明这样的路线不存在。最终，这个问题被瑞典数学家欧拉（L.Euler）于1736年解决了。在他的著名的论文“哥尼斯堡七桥问题”中，把每片陆地抽象成一个点，每座桥抽象成一条边，得到上图（右）。由此，哥尼斯堡七桥问题就变为上图（右）中是否存在从一个点出发，不重复地经过每条边一次，最终回到出发点的回路的问题。除了哥尼斯堡七桥问题以外，还有许多问题，它们都可以抽象为判断一个图中是否存在不重复地经过每条边的的回路（通路）的问题。例如，一笔画问题，路线考察问题，最优化问题等都具有与哥尼斯堡七桥问题相类似的特点。这些特点，可以利用下面的定义来描述。二、定义1.欧拉通路：不重复地经过其中每条边的通路的图。2.欧拉回路：不重复地经过每条边的回路的图。3.半欧拉图：存在欧拉通路的图。4.欧拉图：存在欧拉回路的图。显然，欧拉图必然是半欧拉图，但半欧拉图不一定是欧拉图。例如，在下图中，（1）不是欧拉图，但是是半欧拉图；（2）和（3）既是欧拉图，也是半欧拉图；（4）既不是欧拉图，也不是半欧拉图。（1）（2）（3）（4）三、判定问题有了欧拉图的概念之后，哥尼斯堡七桥问题是否有解，就变成了上述右图是不是欧拉图的问题了。一个图形能否一笔画出，就看这个图形是不是半欧拉图了。为了解决欧拉图和半欧拉图的判定问题，经过研究，欧拉找到了相应的欧拉图和半欧拉图的充分必要条件。定理1对任何无向连通图G=V，E，有：（1）G是欧拉图，当且仅当G中每个结点的的度都是偶数；（2）G是半欧拉图，当且仅当G中每个结点的的度都是偶数，或者G中有且仅有两个度为奇数的结点。说明：定理1的结论只对无向连通图成立。例如，在下图中，由于（1）不是连通图，所以虽然其中每个点的度都是偶数，但它仍然不是欧拉图；由于（2）不是无向图，虽然其中每个点的度都是偶数，但它也不是半欧拉图。（1）（2）对于有向欧拉图的判定，也有类似定理1的结论。定理2对任何有向图G=V，E，有：（1）G是欧拉图，当且仅当它是弱连通的，而且其中每个结点的入度和出度都相同；（2）G是半欧拉图但不是欧拉图，当且仅当它是弱连通的，而且其中只有两个结点的入度与出度不同，同时在这两个结点中，一个结点的入度比出度大1，另一个结点的入度比出度小1。例如，在下图中，（2）和（4）是欧拉图，（1）是半欧拉图，（3）既不是欧拉图，也不是半欧拉图。（1）（2）（3）（4）7.2哈密尔顿图一、问题的提出1859年，英国数学家威廉·哈密尔顿（W.Hamilton）提出了一种“周游世界”问题，如图所示。图中共有20个结点，每个结点表示一个城市，两结点有边相连表示该两城市之间有交通可直达。现要求在图中寻找这样一种旅行路线，使经过每个城市一次，且每个城市只经过一次，最终刚好回到出发的城市。哈密尔顿证明了这样的旅行路线是存在的，具体的旅行次序见下图中各城市所标的序号。这个问题是由哈密尔顿提出的，所以又称为哈密尔顿回路问题。对哈密尔顿回路问题进行抽象，可得到一类特殊图----哈密尔顿图。二、定义1.哈密尔顿通路：不重复地经过图中每个结点的通路。2.哈密尔顿回路：不重复地经过图中每个结点的回路。3.哈密尔顿图：含有哈密尔顿回路的图。4.半哈密尔顿图：含有哈密尔顿通路的图。由于平行边和环的存在与否均不影响图中是否存在哈密尔顿回路（通路），而且非连通的无向图中必不存在哈密尔顿回路（通路），所以只须考虑简单连通图。三、判定问题虽然哈密尔顿图看起来与欧拉图很类似，但判断一个图是否是哈密尔顿图比判断是否是欧拉图要困难得多。事实上，到目前为止，还没有找到一个简明的条件作为一个图是哈密尔顿图的充分必要条件，寻找这种条件是图论中尚未解决的主要问题之一。虽然如此，目前还是得到了一些充分条件和一些必要条件，下面对它们作简单介绍。1.必要条件定理1若无向图G=V，E是哈密尔顿图，则对V的任意非空子集V1，都有P(G-V1)≤∣V1∣其中，p(G-V1)是从G中删除V1中的所有结点后，剩下的图G-V1的连通分支数。定理1给出了哈密尔顿图的一个必要条件，但它不是哈密尔顿图充分条件，我们常用它来判定一个图不是哈密尔顿图。例.在下图中，在(1)中令V1={1,7}，删除V1中的两个结点后得图(4)；此时，由于∣V1∣=2，p(G-V1)=3，p(G-V1)≤∣V1∣不成立，故(1)不是哈密尔顿图。在(2)中令V1={2}，删除V1中的一个结点后得图(5)；由于∣V1∣=1，p(G-V1)=2，显然p(G-V1)≤∣V1∣不成立，故(2)不是哈密尔顿图。(3)图称为彼得森图。不难看出，删除其中任意一个或两个结点，剩下的图仍连通；删除任意三个结点后，剩下的图至多被分成两个分支；删除任意四个结点后，剩下的图至多被分成三个分支；删除五个以上的结点后，剩下的图的结点数将小于等于5，其连通分支数自然不会超过5。所以，对彼得森图G=V,E来说，对V的任意非空子集V1，都有p(G-V1)≤∣V1∣，定理1的条件是满足的。但是，彼得森图是一个典型的非哈密尔顿图（用穷举法可证明其中不存在哈密尔顿回路）。2.充分条件定理2设G=V，E是结点个数n≥2的无向简单图，如果G中每对结点u,v都满足d(u)+d(v)≥n，则G是哈密尔顿图。定理3设G=V，E是结点个数n≥2的无向简单图，如果G中每对结点u,v都满足d(u)+d(v)≥n-1，则G是半哈密尔顿图。上述定理中的前提条件是不可少的。如下图中，(1)的每对结点u,v的度数之和都≥4，满足定理2中的条件，但(1)显然不是哈密尔顿图，这是因为该图不是无向图的缘故；而满足定理2的条件的图(2)也不是哈密尔顿图，则是因为它不是简单图的原因。另外，定理2给出的条件只是哈密尔顿图的充分条件，但不是必要条件。如下图，该图是哈密尔顿图，但它并不满足定理2的条件。利用哈密尔顿图的概念和结论，可以帮助我们解决实际中的许多问题。例.某次会议有20人参加，其中每个人都至少有10个朋友。当这20人围一圆桌入席时，要想使与每个人相邻的两位都是他的朋友，是否有可能？解：可能。首先构造图G，其中用一个结点代表一个参会人员，如果两人是朋友，就将代表此二人的结点用一条边连接。根据已知情况，G是个含有n=20个结点的无向简单图。又由于每个人都至少有10个朋友，所以G中每个结点的度都不小于10，从而任意两个结点的度数之和都不小于10+10=20。因此，G满足定理2的条件，它是个哈密尔顿图。设L是G中的任何一条哈密尔顿回路（必存在），然后按照各人在L中的次序来安排他们的座席，即可得到一种满足要求的入席方案。例.某学校要为七门课程安排考试。考试日程要求满足以下条件：所有课程须在连续的七天内完成；每天只能安排一门课程；同一位教师所担任的课程不能安排在连续的两天中。证明如果没有教师担任的课程数超过4门，则符合上述要求的考试日程总是可能的。证明：构造图G，其中每个结点对应一门考试课程，如果两个结点对应的考试课程是由不同的教师担任的，就将这两结点连一条边。因为每个教师所担任的课程都不超过4门，故每个结点的度都大于等于3，即任意两个结点的度数之和都大于等于6。由定理3知，G中必存在哈密尔顿通路。按这条哈密尔顿通路来安排，就可以得到符合要求的考试日程。7.3二部图一、问题的提出在现实生活和工作中，经常需要将两个集合中的对象进行搭配，这些搭配成对的对象可以是两类对象，也可以是同一类对象。比如，学校给教师安排课程、单位领导给其部属分派任务、民政部门给新婚夫妇登记结婚、航空旅行时飞机旅客与飞机座位的配对、舞会上某时刻的舞伴安排等，都面临搭配问题的解决。图论中从最基本的概念出发，逐步构造出二部图、匹配等描述和解决搭配问题的有效方法。二、定义1.二部图的概念定义：设G=V,E是无向简单图，如果能将结点集合V划分成V1和V2，并且使G中的每条边的两个端点，一个在V1中，另一个在V2中，则称G是个二部图，并称V1,V2是G的互补点集。二部图G=V，E有时记为G=V1,V2,E。例.在下面的图中，（1），（3），（4）是二部图，（2）不是二部图。请读者自己写出（1），（3），（4）的互补点集。（1）（2）（3）（4）一般，画一个二部图的图形时，常以分层的形式画出。如上例的图中，（1），（3），（4）分别画成图7.10中的（a），（b），（c）。（a）（b）（c）2.完全二部图定义：对二部图G=V1，V2，E，如果V1中每个结点都与V2中的所有结点相邻，则称G是完全二部图。特别地，如果V1和V2中分别含有n个结点和m个结点，则完全二部图G记为Kn,m。显然，Kn,m与Km,n互相是同构的。例.下图中给出了完全二部图K3,3和K2,3，其中K3,3在讨论平面图的时候非常有用。K3,3K2,3二、判定问题定理1对任何无向简单图G=V，E，有G是二部图当且仅当G中不含长度为奇数的回路。证明：先证充分性。设G是二部图，则它必可以按分层形式画出。因为从任何一个结点出发的通路要回到出发点，必须刚好经过偶数条边，所以G中的任何一条回路的长度都是偶数，亦即G中不含长度为奇数的回路。再证必要性（用反证法）。设G中不含长度为奇数的回路，则G中的任何一条回路的长度都是偶数。下面分两种情况来考虑：①如果G是连通图，则找出G中一条经过每个结点的回路L，在L上任取一个结点，将它放入V1中，然后沿着L向外依次取结点来考察。若考察的结点在V1或V2中已存在，就跳过它；若考察的结点在V1或V2中不存在，就将它放入V1或V2中（在确保同一集合中的点互不相连的前提下）。这样一直做下去，直到每个结点都已放入V1或V2中。此时的V1，V2就是G的互补点集。②如果G不是连通图，则G的每个连通分支中的每条回路的长度也都是偶数。在每个连通分支里，类似第一种情况的处理方法，将其中的结点可以逐个放入V1或V2中，并使V1，V2成为G的互补点集。综合①②，所以G是二部图。推论：任何一个图，如果它含有不是二部图的子图，则它必定不是二部图。三、匹配的概念1.一般无向图中的匹配定义1设有无向图G=V，E，若M是E的非空子集，且M中不存在相邻的边，则称M是G中的一个匹配。与M中的边关联的点称为M饱和点。有了匹配的概念以后，还可以进一步定义图中的特殊匹配。定义2设M是无向图G=V，E中的一个匹配，若往M中添加任何一条新边后，M就不是G中的匹配了，则称M是G中的一个极大匹配；G中含有的边数最多的匹配称为G中的一个最大匹配。若G中每个结点都是M饱和点，则称M是G中的一个完美匹配。例.在（1）中，{e1}，{e1，e7}，{e5}，{e4，e6}等都是图中的匹配，其中{e1}，{e1，e7}，{e4，e6}是极大匹配，{e1，e7}，{e4，e6}是最大匹配；图中不存在完美匹配。在（2）中，{e2，