欧拉公式证明课件

图论—平面图离散数学图论—平面图离散数学1平面图如果能把一个图在平面上画成除端点外，任何两边都不相交，则称此图为可平面的，或称平面图。平面图如果能把一个图在平面上画成除端点外，任何两边都不相交，2平面图示例平面图示例3平面图示例平面图示例4非平面图示例非平面图示例5非平面图示例非平面图示例6区域平面图的边把平面图划分成的块例如平面图将平面划分成4个区域R1、R2、R3是有限区域R4是无限区域R1R2R3R4区域平面图的边把平面图划分成的块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-6≥m欧拉公式推论设图G是具有n(≥3)个顶点、m条边的无向连通平15推论证明由于G是简单图，因此G中每一个区域至少由3条边围成，若G中有r个区域，围成r个区域总边数为2m(因为每条边都作为两个相邻区域的公共边，被计算了两次)。所以有 2m≥3r或r≤2m/3代入欧拉公式后得n-m+2m/3≥2从而得到3n－6≥m推论证明由于G是简单图，因此G中每一个区域至少由3条边围成，16示例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不是平面图。示例1证明K3,3是非平面图17证明证明具有5个顶点的无向完全图K5是非平面图证明因为在K5中顶点数n=5，边数m=10，3n–6=9<m，不满足平面图的必要条件，所以K5是非平面图。证明证明具有5个顶点的无向完全图K5是非平面图18平面图例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平面图例1设G是至少有11个顶点的无向简单连通平面图，证明G19证明（续）由此可得 6n－12≥(n-1)n/2

整理后得 n2-13n+24≤0或 n2-13n+22≤0 (n

-11)(n

-2)<0由此可得n<11，这和假设n≥11矛盾，证毕。证明（续）由此可得20二度同构如果两个图是由同一个图的边上插入一些新的顶点(它一定是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图论—平面图离散数学图论—平面图离散数学27平面图如果能把一个图在平面上画成除端点外，任何两边都不相交，则称此图为可平面的，或称平面图。平面图如果能把一个图在平面上画成除端点外，任何两边都不相交，28平面图示例平面图示例29平面图示例平面图示例30非平面图示例非平面图示例31非平面图示例非平面图示例32区域平面图的边把平面图划分成的块例如平面图将平面划分成4个区域R1、R2、R3是有限区域R4是无限区域R1R2R3R4区域平面图的边把平面图划分成的块R1R2R3R433欧拉公式设图G是无向连通平面图，它具有n个顶点，m条边和r个区域，则

n-m+r=2欧拉公式设图G是无向连通平面图，34欧拉公式证明用归纳法，对边数进行归纳。当图中仅有一条边时，有两种结构，一是有两个邻接点和一条关联这两顶点的边，易知n=2，m=1，r=1(仅有一个无限区域)，所以欧拉公式n-m+r=2成立；另一种是由一条自由回路构成的图，这时n=1，m=1，r=2，所以欧拉公式成立。欧拉公式证明用归纳法，对边数进行归纳。35欧拉公式证明（续）设当连通平面图具有m条边时，欧拉公式成立。一个具有m+1条边的连通平面图，删去一条边后，仍然是平面图。把具有m+1条边的连通平面图看作是由含m条边的连通平面图添加一条边后构成的。欧拉公式证明（续）设当连通平面图具有m条边时，欧拉公式成立。36欧拉公式证明（续）可能有三种不同的结构。欧拉公式证明（续）可能有三种不同的结构。37欧拉公式证明（续）把具有n个顶点，m条边和r个区域的连通平面图记作G(n,m,r)。在G(n,m,r)中原有的两点中添加一条边，增加一个区域构成图G(n,m+1,r+1),欧拉公式成立欧拉公式证明（续）把具有n个顶点，m条边和r个区域的连通平面38欧拉公式证明（续）把具有n个顶点，m条边和r个区域的连通平面图记作G(n,m,r)。在G(n,m,r)中原有的两点中添加一条边，增加一个区域构成图G(n,m+1,r+1),欧拉公式成立欧拉公式证明（续）把具有n个顶点，m条边和r个区域的连通平面39欧拉公式证明（续）把具有n个顶点，m条边和r个区域的连通平面图记作G(n,m,r)。在G(n,m,r)中添加一条边后，增加了一个顶点但没增加区域数构成图G(n+1,m+1,r)，欧拉公式仍然成立证毕。欧拉公式证明（续）把具有n个顶点，m条边和r个区域的连通平面40欧拉公式推论设图G是具有n(≥3)个顶点、m条边的无向连通平面图，则 3n-6≥m欧拉公式推论设图G是具有n(≥3)个顶点、m条边的无向连通平41推论证明由于G是简单图，因此G中每一个区域至少由3条边围成，若G中有r个区域，围成r个区域总边数为2m(因为每条边都作为两个相邻区域的公共边，被计算了两次)。所以有 2m≥3r或r≤2m/3代入欧拉公式后得n-m+2m/3≥2从而得到3n－6≥m推论证明由于G是简单图，因此G中每一个区域至少由3条边围成，42示例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不是平面图。示例1证明K3,3是非平面图43证明证明具有5个顶点的无向完全图K5是非平面图证明因为在K5中顶点数n=5，边数m=10，3n–6=9<m，不满足平面图的必要条件，所以K5是非平面图。证明证明具有5个顶点的无向完全图K5是非平面图44平面图例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平面图例1设G是至少有11个顶点的无向简单连通平面图，证明G45证明（续）由此可得 6n－12≥(n-1)n/2

整理后得 n2-13n+24≤0或 n2-13n+22≤0 (n

-11)(n

-2)<0由此可得n<11，这和假设n≥11矛盾，证毕。证明（续）由此可得46二度同构如果两个图是由同一个图的边上插入一些新的顶点(它一定是2度点)而得到的，则称这两个图是二度同构的。二度同构如果两个图是由同一个图的边上插入一些新的顶点(它一定47二度同构二度同构48库拉托夫斯基定理一个图是平面图的充分必要条件是该图不包含二度同构于K5或K3,3的子图。库拉托夫斯基定理一个图是平面图的充分必要条件是49非平面图证明例2证明所示图是非平面图。证明把图中的边ED删去后，所得的子图就是K3,3，所以此图是非平面图。ABCDE