个顶点m条边的无向连通平面图.ppt

图论—平面图 离散数学 平面图 如果能把一个图在平面上画成除端点外，任何两边都不相交， 则称此图为可平面的， 或称平面图。 平面图示例 平面图示例 非平面图示例 非平面图示例 区域 平面图的边把平面图划分成的块 例如 平面图将平面划分成4个区域 R1、R2、R3是有限区域 R4是无限区域 欧拉公式 设图G是无向连通平面图， 它具有n个顶点，m条边和r个区域， 则 n - m + r = 2 欧拉公式证明 用归纳法，对边数进行归纳。 当图中仅有一条边时，有两种结构， 一是有两个邻接点和一条关联这两顶点的边， 易知n=2，m=1，r=1(仅有一个无限区域)，所以欧拉公式n-m+r=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)中原有的两点中添加一条边，增加一个区域 构成图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- 6≥m 推论证明 由于G是简单图，因此G中每一个区域至少由3条边围成， 若G中有r个区域，围成r个区域总边数为2m(因为每条边都作为两个相邻区域的公共边，被计算了两次)。 所以有 2m≥3r 或　r ≤ 2m/3 代入欧拉公式后得 　　　　n - m+ 2m/3 ≥ 2 从而得到 3n－6≥m 示例1 证明K3,3是非平面图 证明 由于K3,3是完全二部图，因此每条回路由偶数条边组成， 而K3,3又是简单图，所以如果K3,3是平面图，其每一个区域至少由4条边围成， 于是有 2m≥4r 或 r≤m/2　。 代入欧拉公式后可得 2n－4≥m。 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个顶点(n≥11)，m条边，显然其补图~G 有n个顶点、(n-1)n/2-m条边。 用反证法，设补图~G也是平面图， 则有 3n – 6 ≥ (n-1)n/2-m 图G是连通简单平面图，所以有 3n – 6 ≥ m 证明（续） 由此可得 6n－12≥ (n-1)n/2 　　 整理后得 n2 - 13n+24≤0 或 n2 - 13n+22≤0 (n - 11)(n - 2)0 由此可得n11，这和假设n≥11矛盾，证毕。 二度同构 如果两个图是由同一个图的边上插入一些新的顶点(它一定是2度点)而得到的， 则称这两个图是二度同构的。 二度同构 库拉托夫斯基定理 一个图是平面图的充分必要条件是 该图不包含二度同构于K5或K3,3的子图。 非平面图证明例2 证明所示图是非平面图。 证明　把图中的边ED删去后，所得的子图就是K3,3 ，所以此图是非平面图。 非平面图证明例3　 证明彼得逊图是非平面图。 非平面图证明例3　 证明　把DE和FH删去， 与K3,3是二度同构的， 所以彼得逊图是非平面图。 * 北京工业大学软件学院 张丽 离散数学 * R1 R2 R3 R4 A B C D E F A B C D E F D C I A B F H E G J A B C D E F G H I J H A F I D C B E G J