文档介绍：第十一章 平面图
1
图中的边不要交叉
实际中的很多问题都涉及到一个图中的边是否会交叉的问题。例如：单面印刷电路板，集成电路的布线，交通设计问题；等等。
由此便抽象出平面图的概念：没有交叉 (这里当然不是指在端点处的相互邻接）的边的图。
一个有交叉的边的图能不能转换成与之同构的平面图，显然是人们所关注的问题。
本章就是介绍平面图以及平面图的性质。
2
§ 平面图的概念
3
平面图
：设G是平面上由有限个点及以这些点为端点的有限连续曲线所组成的图形，如果G中任意两条线最多只在它们的端点处相交，称G为平面图。
例1，⑴图不是平面图， ⑵和⑶是平面图。
⑴
⑵
⑶
4
可平面图
上例中的图⑴虽然不是平面图，但是却和图⑵和图⑶是同构的，这样的图称为可平面图。
可平面图：如果一个图G与一个平面图H同构，称G是可平面图；而称H是G的一个平面嵌入。
上例中的图⑴是可平面图，图⑵和图⑶是图⑴的两个平面嵌入。
5
平面图的面
：设G是一个平面图，平面被G的边所围成的区域称为面，这些边称为该面的边界；其中有限区域对应的面称为内部面，无限区域对应的面称为外部面(用f0表示)。
用G(p, q, r)表示一个p个顶点，q条边以及r个面的平面图。
一个面 f 所包含的边数称为 f 的次数，记为d( f ) ，若边为割边，则计算两次。
6
计算下图中各面的次数：
d( f0 ) = 3 ;
d( f1 ) = 5 。
2
4
3
1
f1
f0
(a)
f1
f0
(b)
f2
d( f0 ) = 8 ;
d( f1 ) = 3 ;
d( f2 ) = 3 .
7
面的总次数为边数的两倍
：对任何平面图G(p, q, r) ,有
d( fi ) =2q , (i =1 , 2 , ,r).
证明：由于G的每条非割边恰属于两个面，所以，在计算这两个面的次数时，该边计算两次，而割边只属于一个面，但由规定也计算了两次，故上式成立，即所有面的总次数为边数的两倍。
对比：d( vi ) =2q，(i =1 , 2 , , p)，即所有顶点的总度数为边数的二倍。
8
平面图的同构
：设G和H是两个平面图。如果并且 f 是G中一个由途径uvwu围成的面当且仅当(u)(v) (w)(u)围成H的一个面 f ’ , 则称G与H同构。有时可省略。
例1中图⑵与图⑶就是平面图同构。
9
图的同构与平面图的同构
如果两个图是平面图同构，则必是两个同构的图。可是两个同构的图不一定是平面图同构。
例1中图⑴与图⑵和图⑶是同构的图，但图⑴却不是平面图，因而不可能和它们平面图同构。
下面两个平面图是图同构，但不是平面图同构：
G
1
2
3
4
5
H
1’
2’
3’
4’
5’
6
6’
10