1、图论平面图,离散数学,平面图,如果能把一个图在平面上画成除端点外，任何两边都不相交，则称此图为可平面的，或称平面图。,平面图示例,平面图示例,非平面图示例,非平面图示例,区域,平面图的边把平面图划分成的块例如平面图将平面划分成4个区域R1、R2、R3是有限区域R4是无限区域,欧拉公式,设图G是无向连通平面图，它具有n个顶点，m条边和r个区域，则 n - m + r = 2,欧拉公式证明,用归纳法，对边数进行归纳。当图中仅有一条边时，有两种结构， 一是有两个邻接点和一条关联这两顶点的边， 易知n=2，m=1，r=1(仅有一个无限区域)，所以欧拉公式n-m+r=2成立； 另一种是由一条自由回路构成
2、的图，这时n=1，m=1，r=2，所以欧拉公式成立。,欧拉公式证明（续）,设当连通平面图具有m条边时，欧拉公式成立。一个具有m+1条边的连通平面图，删去一条边后，仍然是平面图。把具有m+1条边的连通平面图看作是由含m条边的连通平面图添加一条边后构成的。,欧拉公式证明（续）,可能有三种不同的结构。,欧拉公式证明（续）,把具有n个顶点，m条边和r个区域的连通平面图记作G(n,m,r)。在G(n,m,r)中原有的两点中添加一条边，增加一个区域构成图G(n,m+1,r+1),欧拉公式成立,欧拉公式证明（续）,把具有n个顶点，m条边和r个区域的连通平面图记作G(n,m,r)。在G(n,m,r)中原有的两
3、点中添加一条边，增加一个区域构成图G(n,m+1,r+1),欧拉公式成立,欧拉公式证明（续）,把具有n个顶点，m条边和r个区域的连通平面图记作G(n,m,r)。在G(n,m,r)中添加一条边后，增加了一个顶点但没增加区域数构成图G(n+1,m+1,r)，欧拉公式仍然成立证毕。,欧拉公式推论,设图G是具有n(3)个顶点、m条边的无向连通平面图，则3n- 6m,推论证明,由于G是简单图，因此G中每一个区域至少由3条边围成，若G中有r个区域，围成r个区域总边数为2m(因为每条边都作为两个相邻区域的公共边，被计算了两次)。所以有2m3r 或r 2m/3代入欧拉公式后得n - m+ 2m/3 2 从而得
4、到 3n6m,示例1,证明K3,3是非平面图证明 由于K3,3是完全二部图，因此每条回路由偶数条边组成， 而K3,3又是简单图，所以如果K3,3是平面图，其每一个区域至少由4条边围成， 于是有 2m4r 或 rm/2。 代入欧拉公式后可得 2n4m。 K3,3中，n=6，m=9，不满足上述不等式， 所以K3,3不是平面图。,证明,证明具有5个顶点的无向完全图K5是非平面图 证明 因为在K5中顶点数n=5，边数m=10，3n 6 = 9m，不满足平面图的必要条件，所以K5是非平面图。,平面图例1,设G是至少有11个顶点的无向简单连通平面图，证明G的补图G一定是非平面图。证明设图G有n个顶点(n1
5、1)，m条边，显然其补图G 有n个顶点、(n-1)n/2-m条边。 用反证法，设补图G也是平面图， 则有3n 6 (n-1)n/2-m 图G是连通简单平面图，所以有3n 6 m,证明（续）,由此可得6n12 (n-1)n/2 整理后得n2 - 13n+240或n2 - 13n+220(n - 11)(n - 2)0由此可得n11，这和假设n11矛盾，证毕。,二度同构,如果两个图是由同一个图的边上插入一些新的顶点(它一定是2度点)而得到的，则称这两个图是二度同构的。,二度同构,库拉托夫斯基定理,一个图是平面图的充分必要条件是 该图不包含二度同构于K5或K3,3的子图。,非平面图证明例2,证明所示图是非平面图。证明把图中的边ED删去后，所得的子图就是K3,3 ，所以此图是非平面图。,非平面图证明例3,证明彼得逊图是非平面图。,非平面图证明例3,证明把DE和FH删去， 与K3,3是二度同构的， 所以彼得逊图是非平面图。,
