可以在它的边互不相交的条件下画在平面上

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,11,.3,平面图,定义,11.3.1,设图,G,=(,V,E,),，,若,G,可以在它的边互不相交的条件下画在平面上，则称,G,为平面图，或称,G,为可嵌入平面的。,例 平面图,在图,G,的边,(,v,1,v,2,),上插入一个顶点,u,是指：删去,G,的边,(,v,1,v,2,)，,然后添加一个新的顶点,u,以及新的边,(,v,1,u,),和,(,u,v,2,)。,在图,G,的某些边上插入若干个顶点后得到图,G,1,，,则称,G,1,是,G,的一个剖分。,图,G,G,的剖分,库拉托斯基,(,Kuratowski,),定理,定理,11.3.1,图,G,为平面图的充要条件是,G,的任何子图都不含有,K,3,3,或,K,5,及其,的剖分。,定义,11.3.2,设,G,为平面图，则,G,把平面划分成若干个连通区域，称这种连通区域为,G,的一个面,，记作,f,。,该连通区域的边界称为,f,的边界,。而,f,的边界作为,G,中的圈，其长度称为,f,的度,，记作,d,(,f,)。,并记,G,的面的集合为,F,，,于是平面图,G,可表示为,G,=(,V,E,F,),。,平面图,G,中无界的面称为,G,的外部面,，而其余的面称为,G,的内部面,，,例如，在图所表示的平面图,G,中，有,7,个顶点，,9,条边和,4,个面。其中,f,1,为,G,的外部面，,f,2,f,3,f,4,为内部面，各个面的度分别为,d,(,f,1,)=7,d,(,f,2,)=3,d,(,f,3,)=3,而,d,(,f,4,)=5,。,注意，图,G,的边,(3,4),作为面,f,1,的边界在计算长度时要计数,2,次。同样，对于面,f,4,边界的边,(2,7),也计数,2,次。,f,1,f,2,f,3,f,4,1,2,7,3,4,5,6,定理,11.3.2,设平面图,G,=(,V,E,F,),是连通的，则,定理,11.3.3,设平面图,G,=(,V,E,F,),是连通的，则,|,V,|-|,E,|+|,F,|,=,2,推论,11.3.1,设平面图,G,=(,V,E,F,)，,且,|,V,|,3,，,则,|,E,|,3,|,V,|,-,6,证 只需对连通的平面图证明即可。设,G,为连通的平面图，则,G,的每个面都至少由,3,条边围城，即,d,(,f,),3,，,于是,S,d,(,f,),3,|,F,|,。,再由定理,11.3.2,可知，,2,|,E,|,3,|,F,|,，,结合欧拉公式,|,V,|-|,E,|+|,F,|,=,2,可得,|,E,|,3,|,V,|,-,6,。,推论,11.3.2,设平面图,G,=(,V,E,F,)，,且对于,G,的每个面都有,d,(,f,),4,，,则,|,E,|,2,|,V,|,-,4,。,例,11.3.2,证明完全二分图,K,3,3,和完全图,K,5,不是平面图。,证 反证法 因为在完全图,K,5,=(,V,E,F,),中，,|,V,|,=,5,，,|,E,|,=,10，,不满足推论,11.3.1,中的公式。,对于完全二分图,K,3,3,=(,V,E,F,),有，,|,V,|,=,6,，,|,E,|,=,9,，,不满足推论,11.3.2,中的公式。,定理,11.3.4,设,G,=(,V,E,F,),是连通的平面图，且,|,V,|,3,，,则存在顶点,v,，,使,d,(,v,),5,。,证 反证法。假设对连通的平面图,G,中每个顶点,v,，,都有,d,(,v,),6,，,则由图的边数与顶点的度数之和的关系公式,S,d,(,v,),=,2,|,E,|,以及,|,V,|,3,，,得,2,|,E,|,6,|,V,|,也即,|,E,|,3,|,V,|,3,|,V,|,-,6,，,与推论,11.3.1,的结论矛盾。,