资源描述：
《可以在它的边互不相交的条件下画在平面上.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、11.3平面图定义11.3.1设图G=(V,E)，若G可以在它的边互不相交的条件下画在平面上，则称G为平面图，或称G为可嵌入平面的。例平面图在图G的边(v1,v2)上插入一个顶点u是指：删去G的边(v1,v2)，然后添加一个新的顶点u以及新的边(v1,u)和(u,v2)。在图G的某些边上插入若干个顶点后得到图G1，则称G1是G的一个剖分。图GG的剖分库拉托斯基(Kuratowski)定理定理11.3.1图G为平面图的充要条件是G的任何子图都不含有K3,3或K5及其的剖分。定义11.3.2设G为平
2、面图，则G把平面划分成若干个连通区域，称这种连通区域为G的一个面，记作f。该连通区域的边界称为f的边界。而f的边界作为G中的圈，其长度称为f的度，记作d(f)。并记G的面的集合为F，于是平面图G可表示为G=(V,E,F)。平面图G中无界的面称为G的外部面，而其余的面称为G的内部面，例如，在图所表示的平面图G中，有7个顶点，9条边和4个面。其中f1为G的外部面，f2,f3,f4为内部面，各个面的度分别为d(f1)=7,d(f2)=3,d(f3)=3而d(f4)=5。注意，图G的边(3,4)作为面f
3、1的边界在计算长度时要计数2次。同样，对于面f4边界的边(2,7)也计数2次。f1f2f3f41273456定理11.3.2设平面图G=(V,E,F)是连通的，则定理11.3.3设平面图G=(V,E,F)是连通的，则
4、V
5、-
6、E
7、+
8、F
9、=2推论11.3.1设平面图G=(V,E,F)，且
10、V
11、≥3，则
12、E
13、≤3
14、V
15、-6证只需对连通的平面图证明即可。设G为连通的平面图，则G的每个面都至少由3条边围城，即d(f)≥3，于是Sd(f)≥3
16、F
17、。再由定理11.3.2可知，2
18、E
19、≥3
20、F
21、，结合欧拉
22、公式
23、V
24、-
25、E
26、+
27、F
28、=2可得
29、E
30、≤3
31、V
32、-6。推论11.3.2设平面图G=(V,E,F)，且对于G的每个面都有d(f)≥4，则
33、E
34、≤2
35、V
36、-4。例11.3.2证明完全二分图K3,3和完全图K5不是平面图。证反证法因为在完全图K5=(V,E,F)中，
37、V
38、=5，
39、E
40、=10，不满足推论11.3.1中的公式。对于完全二分图K3,3=(V,E,F)有，
41、V
42、=6，
43、E
44、=9，不满足推论11.3.2中的公式。定理11.3.4设G=(V,E,F)是连通的平面图，且
45、V
46、≥3，则存在顶点v，使
47、d(v)≤5。证反证法。假设对连通的平面图G中每个顶点v，都有d(v)≥6，则由图的边数与顶点的度数之和的关系公式Sd(v)=2
48、E
49、以及
50、V
51、≥3，得2
52、E
53、≥6
54、V
55、也即
56、E
57、≥3
58、V
59、>3
60、V
61、-6，与推论11.3.1的结论矛盾。
