第八章 几种特殊的图

1、第八章 几种特殊的图8.1二部图 无向图G = <V，E>称为二部图，如果有非空集合X，Y使XY = V，XY = Æ，且对每一eÎE，e = (x, y)，xÎX，yÎY。此时常用<X，Y，E>表示二部图G。若对X中任一x及Y中任一y恰有一边(x, y)ÎE，, 则称G为完全二部图。当|X| = m，|Y| = n时，完全二部图G记为Km,n。 图8.1中（a），（b）为二部图，（c）为完全二部图K3,3，(d), (e)不是二部图。 二部图的下列特征性是重要的。 至少有两个顶点的无向图G为二部图的充分必要条件是G不存

2、在奇数长度的回路。证明：必要性。设图G为二部图，记G=<V1,V2,E>,设v1,v2,v3,vk,v1是一个回路，不妨设v1V1,由二部图的定义知，vk是偶数，路经长度为偶数，所以，G不存在奇数长度的回路。充分性：（1）先设G是连通的，v1是任意一个顶点。记 V1=x|v1到x的路经的长度是偶数V2=x|v1到x的路经的长度是奇数下证V1,V2是V的分类，且每一条边一个端点在V1另一个端点在V2中。匹配 设G = <V,E>为无向图，E*ÍE。称E*为G的一个匹配，如果E*中任何两条边都没有公共端点。如果E*中再增加一条边就不是匹配了，则称E*为极大匹配。边

3、数最多的匹配称为最大匹配。最大匹配中的元素（边）数叫匹配数，记为。 设若v与M中的某一条边关联，则称v是M的饱和点，若G中每个顶点都是M的饱和点，则称M是G的完美匹配。 图8.2中各图的粗线表示匹配中的边（简称匹配边）。（b）中匹配是最大的。         （a） （b） 注意：最大匹配总是存在但未必唯一。此外，完美匹配必定是最大的，但反之则不然。为讨论最大匹配的求法及完全匹配的存在条件，需要下列术语。 设G = <V1，V2，E>是一个二部图，M为G的一个最大匹配，若，则称M为G的一个完备匹配。此时若，则称V1到V2的

4、完备匹配，如果这时,M为G的完美匹配，(hall定理) 设G = <V1，V2，E>是一个二部图，G中存在V1到V2的完备匹配的充要条件是V1中任意k（k=1,2, ）个顶点至少邻接V2的k个顶点。 设G = <V1，V2，E>是一个二部图，如果（1）V1中的每个顶点至少关联t(t>0)条边；（2）V2中的每个顶点至多关联t(t>0)条边，则G中存在V1到V2的完备匹配。8.2欧拉图 给定图G=<V，E>，通过G中的每一条边一次且恰好一次的通路(回路)，称为欧拉通路(欧拉回路)。存在欧拉通路的图称为半欧拉图，存在欧拉回路的图称为欧拉图。哥尼斯堡七

5、桥问题: 这是否是一个欧拉图?一笔画问题。 设G是无向连通图，则G是半欧拉图G中只有零个或两个奇数度顶点。 设G是无向连通图，则G是欧拉图G中没有奇数度顶点。连通有向图G=<V，E>存在欧拉路径G中除两个顶点之外其余每个结点的入度等于出度，且这两个顶点中一个顶点出度比入度大1，另一个顶点的入度比出度大1。连通有向图G=<V，E>是欧拉图G中每个结点的入度等于出度。K5是欧拉图。例8.2.4 下列图形能否一笔画成?8.3哈密尔顿图哈密尔顿周游世界问题：1856年，著名的爱尔兰数学家Hamilton设计了一个游戏：给定世界上20个城市，用一个代表地球的十二面体的20个顶点分

6、别代表这20个城市。从某一个顶点出发，沿着十二面体的棱，经过每个顶点恰好一次，最后回到出发点。设无向图通过G中的每个顶点一次且恰好一次的通路(回路)，称为哈密尔顿通路(哈密尔顿回路)。存在哈密尔顿通路的图称为半哈密尔顿图。存在哈密尔顿回路的图称为哈密尔顿图。图形是哈密尔顿图吗？无向完全图Kn(n3)是哈密尔顿图。哈密尔顿图问题尽管在形式上与欧拉图问题极其相似，但至今还未得到关于哈密尔顿图的简明的充要条件，这属于图论中尚未解决的难题之一。下面分别介绍判定哈密尔顿图的一个充分条件和一个必要条件。设G=<V，E>是哈密尔顿图，V1是V的任一非空真子集，则p(G- V1)| V1|其中p(

7、G- V1)是从G中删去V1中的顶点及以G中所有以V1中的顶点为端点的边所得图的连通分支数。 证明：可用有名的彼得森图说明上述条件仅为必要条件而不是充分条件。设无向简单图G=<V，E>，若任两个不相邻的结点u，vV， deg(u)+deg(v)n-1，则G是半哈密尔顿图。设无向简单图G=<V，E>，n3，若任两个不相邻的结点u，vV， deg(u)+deg(v)n，则G是哈密尔顿图。某地有5个风景点，若每个风景区均有两条道路与其它景点相通，问游客可否经过每个景点恰好一次游完5个景点?8.4平面图设一个无向图G=<V，E>。若能把它画在平面上，且除V中的顶点之

8、外，任意两条边均不相交，则称该图为平面图。画出的没有边相交的图叫G的平面嵌入（平图）。平面图的例子。A B C D E有些图表面上看上去有边交叉，但经过改画后，就可使边不交叉，则这样的图实际上是平面图。但有些图，无论怎样改画都避免不了边的交叉，这样的图就是非平面图。两个典型的非平面图: （库拉图斯基图）。判别平面图的一种直观方法:(1)若一个图无基本回路，则它是一个平面图; 否则从有基本回路的图找出一个长度尽可能大且边不相交的基本回路;(2)将图中那些交叉的边，适当放置在已选定的基本回路内侧或外侧。若最后能避免边的交叉，则该图是平面图，否则它是非平面图。设G是一个(连通)平面图，若由G的若干条

9、边组成的回路所界定的区域内不含G的任何边和顶点，则称这样的区域为G的一个（有限）面。面积无限的面叫无限面。包围这个面f的各条边所构成的回路，称为该面的边界，它的长度称为面f的次数，记为deg(f)。用F表示G中所有面的集合。求下列平面图的面、面的次数。 a b c d e f若G=<V，E>是平面图，则deg (f)=2|E|。设G=<V，E，F>是连通平面图，则n-m+f=2。设G=<V，E，F>是连通平面图，|V|=n，|E|=m，每个面的次数至少为l(l3)，则m(n-2)。设G=<V，E，F>是连通的简单平面图，|V|=n，|E|=m，且n 3，则m 3n-6。设G=<V，E，F>是连通的简单平面图，|V|=n，|E|=m，则G中至少有一个顶点的度数不超过5。若图G1与G2同构或图G2可由图G1中的一些边上适当插入度为2 的结点或涂抹掉2度的结点合并相邻边后得到，则称G1与G2同胚。若图G中相邻顶点u,v的初等收缩为（1）删除边(u,v),(2)用W代替(u,v),(3)W关联u,v关联的一切边（除（u,v）. 一个图G是平面图óG中不含同胚于K3，3或K5的子图。一个图G是平