欧拉公式证明课件

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