大连理工chapter7(图论)(2008426)(4)

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,离散数学（图论）,Discrete Mathematics,9/13/2024,1,第八章 几类重要的图,图是一类非常广泛的数学模型,在现实中的许多问题,如电网络问题,交通网络问题,运输的优化问题,社会,学中某类关系的研究,都可以用这类数学模型研究和,处理。在计算机科学的许多领域,如开关理论与逻辑,设计, 人工智能, 形式语言, 计算机图形,操作系统,编译程序, 信息检索等方面图和图的理论也有很多,重要的应用。,9/13/2024,2,在图8.1.1画出了哥尼斯堡城图，城的四块陆地部分,以,A,，,B,，,C,和,D,标记。欧拉巧妙地把哥尼斯堡城图,化为图8.1.2所示图,G,，他把陆地设为图,G,中的结点，,把桥画成相应地联结陆地即结点的边。,8.1欧拉图与哈密尔顿图,9/13/2024,3,定义8.1.1 图,G,中的一圈(或回路)，若它通,G,中的每一,条边(或弧)恰好一次，则称该圈(或回路)为欧拉圈(或,回路)，具有这种圈(或回路)的图称为欧拉无向(或有,向)图。,定理8.1.1 给定连通无向图,G,，,G,有欧拉圈,iff,G,中每个,结点都是偶度结点。,8.1欧拉图与哈密尔顿图,9/13/2024,4,例8.1.1 已知图,G,= 如图8.1.3(,a,)所示，试用,定理8.1.1所用证明方法构造欧拉圈。,8.1欧拉图与哈密尔顿图,9/13/2024,5,定义8.1.2 图,G,中的一条链(或路)，若它通过,G,中的每,条边(或弧)恰好一次，则称该链(或路)为欧拉链(或路)。,定理8.1.2 给定连通无向图,G,=,u,v,V,且,u,v,u,与,v,间存在欧拉链,iff,G,中仅有,u,和,v,为奇度结点。,8.1欧拉图与哈密尔顿图,9/13/2024,6,与欧拉圈和链 ( 或回路和路 ) 非常类似的问题是哈密,尔顿圈和链(或回路和路)的问题。,1859年, 爱尔兰数学家哈密尔顿 (W.R.Hamilton)首先,提出 “环球周游”问题。他用一个正十二面体的 20 个,顶点代表世界上20个大城市, 这个正十二面体同构于,一个平面图, 要求旅游者能否找到沿着正十二面体的,棱, 从某个顶点(即城市)出发，经过每个顶点(即每座,城市) 恰好一次，然后回到出发顶点？ 这便是著名的,哈密尔顿问题。,8.1欧拉图与哈密尔顿图,9/13/2024,7,按图8.1.4(,c,)中所给的编号进行旅游，便是哈密尔顿,问题的解。,8.1欧拉图与哈密尔顿图,9/13/2024,8,定义8.1.3 图,G,中的一圈(或回路)，若它通过,G,中每个,结点恰好一次，则该圈(或回路)称为哈密尔顿圈(或,回路)，具有哈密尔顿圈(或回路)的图称为哈密尔顿,无向(或有向)图。,由该定义可知，完全图必是哈密尔顿图。,定义8.1.4 图,G,中的一链(或路)，若它通过,G,中的每个,结点恰好一次，则该链(或路)称为哈密尔顿链(或路)。,8.1欧拉图与哈密尔顿图,9/13/2024,9,定理8.1.5 若连通图,G,=是哈密尔顿图，,S,是,V,的任意真子集，则(,G,-,S,)|,S,|。,本定理给出是哈密尔顿图的一个必要条件，但这个,条件又不便于使用，因为它要求对,G,的结点集合的,所有真子集进行验证。尽管如此，利用它还可以证,明某些图不是哈密尔顿图。,8.1欧拉图与哈密尔顿图,9/13/2024,10,例8.1.2 图8.1.5所示图,G,=, 若,S,=,v,2,v,6,，则,G,-,S,是3个连通分图，因此(,G,-,S,)|,S,|，从而,G,不,是哈密尔顿图。,8.1欧拉图与哈密尔顿图,9/13/2024,11,在图8.1.6所示彼得森(,Petersen,)图,G,=中，,V,的任意真子集,S,，总有(,G,-,S,)|,S,|。,但是，可以证明图,G,不是哈密尔顿图。,8.1欧拉图与哈密尔顿图,9/13/2024,12,下面给出图,G,是哈密尔顿图的充分条件，这个结果是,于1960年,Ore,研究得到的。,定理8.1.6 设,G,= 是 |,V,|=,n,3 阶简单图。,若,u,v,V,有,d,(,u,)+,d,(,v,),n,-1,则,G,中存在一条哈密尔顿,链。若,d,(,u,)+,d,(,v,),n,，则,G,是哈密尔顿图。,推论 给定简单图,G,=，若|,V,|3，,|,V,|/2，,则,G,是哈密尔顿图。,8.1欧拉图与哈密尔顿图,9/13/2024,13,定义8.2.1 给定简单无向图,G,=, 且,V,=,V,1,V,2,，,V,1,V,2,=,。若,V,1,和,V,2,的诱导子图和都是,零图， 则称,G,是二部图或偶图， 并将二部图记作,G,=，并称,V,1,，,V,2,是,V,的划分。,在一个二部图,G,=中,若|,V,1,| =,m,，|,V,2,| =,n,，,且对任意的,u,V,1,，,v,V,2,均有,u,v,E,，则称,G,为,完全二部图，记为,K,m,n,。,8.2二部图,9/13/2024,14,例8.2.1 图8.2.1中(a)为一般二部图, (b)是 K,3,3,，,(c)是K,2,3,。,8.2二部图,9/13/2024,15,定理8.2.1 简单图,G,为二部图,iff,G,中所有基本圈的,长度为偶数。,8.2二部图,9/13/2024,16,定义8.2.2,给定简单无向图,G,=, 若,M,E,且,M,中,任意两条边都是不邻接的，则子集,M,称为,G,的一个,匹配,或,对集, 并把,M,中的边所关联的两个结点称为在,M,下是匹配的。,令,M,是,G,的一个匹配, 若结点,v,与,M,中的边关联,则称,v,是,M,饱和的；否则，称,v,是,M,不饱和的；,若,G,中每个结点都是,M,饱和的, 则称,M,是,完全匹配,。,如果,G,中没有匹配,M,1,使|,M,1,|,M,|,则称,M,是最大匹配。,8.2二部图,9/13/2024,17,例8.2.2 图8.2.2中,(,a,)的一个最大匹配是 ,v,1,v,2, ,v,3,v,9, ,v,5,v,6, ,v,7,v,8, ；,(,b,)的一个完全匹配是 ,v,1,v,2, ,v,3,v,4, ,v,5,v,6, ,v,7,v,8, 。,8.2二部图,9/13/2024,18,定义8.2.3,令,M,是图,G,=中的一个匹配。,若存在一个链, 它是由,E,-,M,和,M,中的边交替构成,则称该链是,G,中的,M,交错链；,若,M,交错链的始结点和终结点都是,M,不饱和的,则称该链为,M,增广链；,特别地, 若,M,交错链的始结点也是它的终结点而,形成圈, 则称该圈为,M,交错圈。,8.2二部图,9/13/2024,19,例如, 在图8.2.2(,a,)中,M,v,3,，,v,5,，,v,6,，,v,7,。,v,9,v,3,v,5,v,6,v,7,是,M,交错链；,v,9,v,3,v,5,v,6,v,7,v,8,是,M,增广链；,v,3,v,5,v,6,v,7,v,3,是,M,交错圈，,8.2二部图,9/13/2024,20,在匹配理论中，人们特别关心的是最大匹配。,Berge在1957年给出了一个图中的一个匹配为最大,匹配的充要条件。,在证明这一结论时, 将要用到两个集合的对称差的,概念:,给定两个集合,S,和,T, S,与,T,的对称差, 记为,S,T,其定义为,S,T,=(,S,T,)-(,S,T,),8.2二部图,9/13/2024,21,在图8.2.3(a)中有两个匹配 M,1,和 M，其中,M,1,= v,1, v,7,，v,2, v,8,，v,3, v,9,，v,5, v,6, ,M = v,1, v,7,，v,3, v,6,，v,4, v,8, ,(b)表示图,8.2二部图,9/13/2024,22,引理8.2.1,设,M,1,和,M,2,是图,G,中的两个匹配, 则在,中, 每个分图或是交错链, 或是交错圈。,定理8.2.2,(Berge，1957) 图,G,的一个匹配,M,是个,最大匹配,iff G,中不含有,M,增广链。,8.2二部图,9/13/2024,23,1935年, Hall 给出图论中著名的Hall婚配定理。,定理8.2.3 给定二部图,G,=,G,中存在使,V,1,中每个结点饱和的匹配,iff,对任意,S,V,1,有, |,N,(,S,)|,S,| (2),其中,N,(,S,)表示与,S,中结点邻接的所有结点集合。,推论 若,G,=是二部图, 且对于任意,v,V,1,或,V,2,有,d,(,v,)=,k,0，则,G,有一个完全匹配。,8.2二部图,9/13/2024,24,下面给出寻找图,G,= 中任意一个匹配,M,的称为,Hungarian方法的算法。,(1) 若,V,1,中每个结点是,M,饱和的, 停止。否则, 令,v,是,V,1,中,M,不饱和结点，作,S,=,v,和,T,=,.,(2) 若,N,(,S,)=,T,因为|,T,|=|,S,|-1, 则 |,N,(,S,)|,S,|，由,Hall,定理知，,不存在使,V,1,中每个结点都是饱和的匹配，停止，否则，,令,y,N,(,S,)-,T,。,(3) 若,y,是,M,饱和的,令,y,z,M,作,S,S,z,和,T,T,y,并转到(2); 否则, 令,C,M,是以,v,为始结点和,y,为终结点的,M,增广链，作,M,M,E,(,C,M,)并转到(1)。其中,E,(,C,M,),表示,C,M,中所有边的集合。,8.2二部图,9/13/2024,25,例8.2.3 有四名教师张振、王兴、李忠和赵华，可分,派他们教四门课程:数学、物理、电工和计算机导论。,张振懂物理和电工; 王兴懂数学和计算机导论; 李忠,懂数学、物理和电工;赵华只懂电工。问应如何分派，,才不会使任何人去讲他不懂的课程而又不存在有的,课程无人教？,8.2二部图,9/13/2024,26,定义8.3.1,一个无圈的连通图，称为,树,。,由定义可知，树是个简单图，即它无环和无平行边。,在树中，度为1的结点称为,叶,或,悬挂结点,；,度数大于的结点称为内结点或,分枝结点,；,而与叶或悬挂结点所关联的边，称为叶边或悬挂边。,若图中的每个连通分图是树，则称该图为,森林,。,8.3 树,9/13/2024,27,定理8.3.1 树,T,中任两个结点间恰有一条链。,定理8.3.2 若图,G,中每对结点间有且仅有一条链，,则,G,为树。,定理8.3.3 具有,n,个结点的树中有,n,-1条边，即树,T,=中，|,E,|=|,V,|-1。,8.3 树,9/13/2024,28,注意，具有,n,个结点和恰有,n,-1条边的图未必是树，,但有下面两个定理：,定理8.3.4 给定连通图,G,=，若 |,E,| = |,V,|-1，,则,G,是树。,定理8.3.5 给定图,G,=, |,E,|=|,V,|-1 且,G,中无圈，,则,G,是树。,8.3 树,9/13/2024,29,连通无圈完全刻划了树，这是树的一个特性；树还有,另外一个重要性质是：它以最少的边使结点可达或连,通。这便导出下面的最小连通的概念：,定义8.3.2 给定连通图,G,=，若对任意,e,E,，,均使,G,-,e,不连通，则称连通图,G,是最小连通的。,8.3 树,9/13/2024,30,显然最小连通图不可能有圈。因为删去圈中的一条,边后仍使图连通。于是最小连通图是树。反之如果,一个连通图,G,不是最小连通的, 则必存在,G,中一条边,e,i,，使,G,-,e,i,连通。所以,e,i,位于一圈中,这意味着,G,不是,树。故可得到下面定理：,定理8.3.6 图,G,是树,iff G,是最小连通的。,8.3 树,9/13/2024,31,给定图,G,=，,G,是树的等价定义是：,G,是连通且无圈;,G,是连通且|,E,|=|,V,|-1;,G,是无圈且|,E,|=|,V,|-1;,G,中每对结点间恰有一条链;,G,是最小连通图.,8.3 树,9/13/2024,32,定理8.3.7 给定树,T,=，若|,V,|2，则,T,中至少,存在两个悬挂结点。,8.3 树,9/13/2024,33,对于一些图，它本身未必是树，但它的子图是树。,一个图可能有多个子图是树，其中很重要的一类树,是生成树。,定义8.3.3 给定图,G,=。若,G,的生成子图,T,是树,则称,T,是,G,的生成树。,T,中的边称为枝，是,G,中的边但,不为,T,中的边称为弦。,8.3 树,9/13/2024,34,图8.3.4所示的图,G,=，,T,1,和,T,2,是它的生成树。,8.3 树,9/13/2024,35,定理8.3.8 图,G,= 有生成树,T,= ,iff,G,是连通的。,8.3 树,9/13/2024,36,下面讨论利用生成树来讨论加权图的最小连接问题。,设,G,=是加权的连通图，对任意边,e,E,，,其权,w,(,e,)0。令,T,=是,G,的一棵加权,生成树，其所有枝上的权的总和，称为树,T,的权，,记为,w,(,T,)。,一般说来，对于,G,的不同生成树,T,，,w,(,T,)也是不同的。,可以知道，其中必有一个最小者，而这正是人们最,为感兴趣的。,8.3 树,9/13/2024,37,定义8.3.4 给定连通加权图,G,= ，,T,0,=是,G,的加权生成树,w,(,T,0,)为,T,0,的权。若对,G,的任意加权生成树,T,均有,w,(,T,0,),w,(,T,)，则称,T,0,是,G,的最小生成树。,8.3 树,9/13/2024,38,下面给出一种求最小生成树的方法Kruskal算法,(1956)，它的本质是树生成过程，因此得名避圈法。,定理8.3.11 设,G,是有,n,个结点的连通图,下面算法产生,的是最小生成树。,(1) 选取具有尽可能小的权的边,e,1,；假定,i,n,-1和已选,取边为,e,1,，,e,2,，,e,i,。,(2) 在,G,中选取不同于,e,1,e,2,e,i,的边,e,i,+1,使,e,1,e,2,e,i,+1,的诱导子图无圈且,e,i,+1,是满足此条件的权尽可能小,的边。重复作下去直至选出边,e,1,e,2,e,n,-1,为止。,8.3 树,9/13/2024,39,例8.3.4 给出世界上六大城市伦敦、莫斯科、纽约、,巴黎、北京和东京之间的航空距离(以哩为单位)如下:,Lo,Me,Ny,Pa,Pe,To,Lo,0 5558 3469 214 5074 5959,Me,0 2090 5725 7753 7035,Ny,0 3636 6844 6757,Pa,0 5120 6053,Pe,0 1307,To,0,8.3 树,9/13/2024,40,定义8.3.5 给定加权连通图,G,=, 对任意,e,E,均有,w,(,e,)0，及,u,，,v,V,。连接,u,和,v,的链,C,0,：,u,=,x,1,，,x,2,，,x,k,=,v,其链长记为,l,(,v,)或,l,(,C,0,)，,等于 , 如果对,G,中连接,u,与,v,的任何链,C,均有,l,(,C,0,),l,(,C,)，,则称,C,0,是,G,中连接,u,和,v,的最短链 .,8.3 树,9/13/2024,41,现在给出一种求从已知结点到另外一个结点的最短链,的方法G.Dantzig算法,其本质也是一种树生长过程。,定理8.3.12 设有,n,个结点的加权连通图,G,=，,x,0,V,。依下面算法得到,G,的一棵生成树,T,，使得在,T,中连接,x,0,与,x,x,0,的每一条基本链是,G,中连接,x,0,与,x,的,最短链。,8.3 树,9/13/2024,42,令,X,0,=,x,0,和,l,(,x,0,)=0,(1) 选取,x,1,，连接,x,0,与,x,1,使,w,(,x,0,，,x,1,)尽可能地小。令,l,(,x,1,)=,w,(,x,0,x,1,)，,X,1,=,x,0,x,1,和,E,1,=,x,0,x,1,。,(2) 假设已确定结点集,X,k,=,x,0,，,x,1,，,x,k,和边集,E,k,。对于,x,i,X,k,选取,y,i,X,k,，使得,x,i,y,i,E,且,w,(,x,i,y,i,)尽可能地小。选取,x,p,X,k,，使得对于,i,=0,1,k,有,l,(,x,p,)+,w,(,x,p,y,p,),l,(,x,i,)+,w,(,x,i,y,i,)，,令,x,k,+1,=,y,p,和,l,(,x,k,+1,)=,l,(,x,p,)+,w,(,x,p,y,p,)，再令,X,k,+1,=,x,0,x,1,x,k,x,k,+1,和,E,k,+1,=,E,k,x,p,x,k,+1,。,(3) 重复(2)，直到,X,n,-1,=,x,0,，,x,1,，,x,n,-1,和,E,n,-1,为止。,8.3 树,9/13/2024,43,例 8.3.5 图8.3.8给定加权连通图,G,=，其中,V,= ,v,1,，,v,2,，,v,3,，,v,4,，,v,5,，,v,6,，,E,=,v,1,v,2,v,1,v,5,v,2,v,3,v,2,v,6,v,2,v,5,v,3,v,4,v,3,v,6,v,4,v,5,v,4,v,6,v,5,v,6,W,=3,1,2,1,3,2,3,4,1,2。求生成树。,8.3 树,9/13/2024,44,定义8.3.6 如果一个有向图的基础图是一棵树，则该,有向图称为,有向树,。其图形表示法常采用倒置树表示,之，且为方便计，有时略去边之方向。,例如，图8.3.10所示的图是一棵有向树。,8.3 树,9/13/2024,45,定义8.3.7 给定一个有向树，若只有一个结点的入度,是零，其余结点的入度都是1，则称该树为,有根树,。,在有根树中，入度为零的结点称为根或根结点;,出度为零的结点称为叶或叶结点；,出度不为零的结点称为分枝结点或内结点。,例如，在图8.3.10所示的有向树中，,v,0,是根,v,1,，,v,2,，,v,6,，,v,7,都是分枝结点，余下结点都是叶。,8.3 树,9/13/2024,46,定义8.3.8 在有根树中，从根到某个结点的路长即该,路中的弧数，称为该结点的级。其中结点的级的最大,者，称为有根树的树高。,有根树的根结点的级是零；,任何结点的级，等于从根到该结点的距离。,例如，在图8.3.10所示的有根树中，有两个结点的级,是1，五个结点的级是2，三个结点的级是3。,8.3 树,9/13/2024,47,定义8.3.9 在一棵有根树中，在每一级的结点都指定,某种次序，称树为,有序树,。,例如，图8.3.11与图8.3.10表示两棵不同的有序树。,8.3 树,9/13/2024,48,为表示结点间的关系，有时借用家族中的术语。,令,u,是有向树中的分枝结点，若从,u,到,v,有一条弧或说,u,与,v,是邻接的，则结点,v,称为结点,u,的“儿子”，或称,u,是,v,的“父亲”；,若从,u,到,w,有一条路，称,u,是,w,的“祖先”，或称,w,是,u,的,“子孙”，同一个分枝结点的儿子称为“兄弟”。,8.3 树,9/13/2024,49,定义8.3.10 在有根树中，若每一个结点的出度都小于,或等于,m,，则称该树为,m,叉树。若每一个结点的出度,恰好等于,m,或等于0，则称这种树为完全,m,叉树。,若所有的叶结点的级相同，则称正则,m,叉树。,定义8.3.11 在,m,叉树中，如果对任何结点的,m,个(或少,于,m,个)儿子都分别指定好,m,个不同的确定位置，则称,该树为,位置,m,叉树,。,8.3 树,9/13/2024,50,当,m,=2时得到常用的二叉树、完全二叉树和正则二叉树。,例如, (,a,)给出一棵二叉树,而且是正则二叉树; (,b,)是一棵,完全二叉树;(,c,)是二叉树中的一个结点的各个儿子的所,有可能的四种排列。(,d,)与(,a,)都是二叉树，它们都是同一,的有序树，但却是不同的位置树。,8.3 树,9/13/2024,51,在位置二叉树中,每个结点可用字符表0,1上的字符串,惟一地表示。串中的字符个数称为串的长度。,结点,v,的任何一个儿子所对应的串的前缀是,v,所对应的,串；任何一个叶结点的串不能放置在其它结点的串的,前面, 这树是位置二叉树的0-1串表示或称哈夫曼编码。,对应于叶结点串的集合形成一个,前缀码,或,哈夫曼编码,。,例如，000，001，01，10，110，111是前缀码.,因为它正是图8.3.12(,b,)中树的叶结点0-1串表示的集合。,8.3 树,9/13/2024,52,定理8.3.13 任何一个前缀码都对应一棵位置二叉树的0-1串表示，即哈夫曼编码对应一棵哈夫曼编码树。,8.3 树,9/13/2024,53,例如，图8.3.13给出了与前缀码000，001，01，1对,应的完全二叉树。其中(,a,)是高度为3的正则二叉树，,对应前缀码中串的结点用方框标记，(,b,)是经删剪后,得到的对应二叉树。,8.3 树,9/13/2024,54,二叉树的一个重要应用就是最优树问题。,给定一组数,w,1,，,w,2,，,w,n,。令一棵二叉树有,n,个,叶结点，并对它们分别指派,w,1,，,w,2,，,w,n,作为权，,则该二叉树称为加权二叉树。,8.3 树,9/13/2024,55,定义8.3.12 在权分别为,w,1,，,w,2,，,w,n,的加权二叉树,T,中, 若权是,w,i,的叶结点,其级为,L,(,w,i,), 则称,为加权二叉树,T,的权，并记为,w,(,T,)。,已知,w,1,，,w,2,，,w,n,为权，,T,0,为加权二叉树，其权为,w,(,T,0,)，如果对任意加权二叉树,T,，它的权是,w,(,T,)，均,有,w,(,T,0,),w,(,T,)，则称,T,0,是最优树或Huffman树。,8.3 树,9/13/2024,56,定理8.3.14 设,T,为加权,w,1,w,2,w,n,且,w,1,w,2,w,n,的最优树，则,(1) 加权,w,1,和,w,2,的叶结点,v,w,1,和,v,w,2,是兄弟。,(2) 以叶结点,v,w,1,和,v,w,2,为儿子的分枝结点，它是所有,分枝结点的级最高者。,8.3 树,9/13/2024,57,定理8.3.15 设,T,为加权,w,1,，,w,2,，,w,n,且,w,1,w,2,w,n,的最优树，若将以加权,w,1,和,w,2,的,叶结点为儿子的分枝结点改为加权,w,1,+,w,2,的叶结点,而得到一棵新树,T,1,，则,T,1,是最优树。,8.3 树,9/13/2024,58,根据上述两个定理，求一棵有,n,个权的最优树，可简化,为求一棵有,n,-1个权的最优树，而这又可简化为求一棵,有,n,-2个权的最优树，依此类推。,具体作法是：,首先找出两个最小的权值，设,w,1,和,w,2,;,然后对,n,-1个权,w,1,+,w,2,，,w,3,，,w,n,求作一棵最优树，,并且将这棵树中的结,w,1,+,w,2,代之以,w,1,w,2,;,依此类推。,8.3 树,9/13/2024,59,例8.3.6 设有一组数2，2，2，3，4，6，6，7，9，12，13，求相应的最优树。,8.3 树,9/13/2024,60,在一些实际问题中，要涉及到图的平面性的研究，,比如大家都知道的印刷线路板的布线问题。近些,年来，大规模集成电路的发展，进一步促进了图,的平面性的研究。,定义8.5.1 一个无向图,G,=,如果能把它画在,平面上，且除,V,中的结点外, 任意两条边均不相交,则称该图,G,为平面图。,8.5 平面图,9/13/2024,61,例如，图8.5.1中(,a,)与(,b,)都是平面图，而(,c,)和(,d,)都,不是平面图。,8.5 平面图,9/13/2024,62,下面给出一种判别平面图的直观方法。,根据平面图的定义，无圈的图显然是平面图。故研究,图的平面性问题，只需要限制有圈的一类图即可。,判别方法是：,(1) 对于有圈的图找出一个长度尽可能大的且边不相交,的基本圈。,(2) 将图中那些相交于非结点的边，适当放置在已选定,的基本圈内侧或外侧，若能避免除结点之外边的相,交，则该图是平面图；否则，便是非平面图。,8.5 平面图,9/13/2024,63,在图论中，称,K,3,3,和,K,5,是库拉托夫斯基图。这是因为,波兰数学家库拉托夫斯基(K.Kuratowski)于1930年给,出了的判别平面图充要条件曾用到这两个图。,定义8.5.2 若图,G,2,可由图,G,1,中的一些边上适当插入或,涂抹度为2的有限个结点后而得到，则称,G,1,与,G,2,同胚。,8.5 平面图,9/13/2024,64,定理8.5.1 (平面图判定定理) 一个图,G,是平面图,iff,G,中不含同胚于,K,3,3,或,K,5,的子图，或,G,不含由边收缩,成,K,3,3,或,K,5,的子图。,8.5 平面图,9/13/2024,65,下面介绍平面图中的重要的欧拉公式。,定义8.5.3 设,G,为一平面图，若由,G,的一条或多条边所,界定的区域内部不含图,G,的结点和边，这样的区域称,为,G,的一个面，记为,f,。包围这个区域的各条边所构成,的圈，称为该面,f,的边界，其圈的长度，称为该面,f,的,度，记为,d,(,f,)。,为强调平面图,G,中含有面这个元素，今后把平面图表,为,G,=，其中,F,是,G,中所有面的集合。,8.5 平面图,9/13/2024,66,定理8.5.2 令,G,=是连通平面图，则,定理8.5.3 设,G,=是连通平面图，则,|,V,|-|,E,|+|,F,|=2。,这便是著名的欧拉公式。,8.5 平面图,9/13/2024,67,推论1 给定连通简单平面图,G,=。,若|,V,|3，则|,E,|3|,V,|-6。,推论2 设,G,=是一个连通简单平面图，,若|,V,|3，则存在,v,V,，使得,d,(,v,)5。,推论3 给定连通简单平面图,G,=。,若对于每个面,f,F,，有,d,(,f,)4，则,|,E,|2|,V,|-4,推论4 完全图,K,n,是平面图,iff n,4。,推论5 完全二部图,K,m,n,是平面图,iff m,2或,n,2。,8.5 平面图,9/13/2024,68,