图论—平面图离散数学北京工业大学软件学院张丽离散数学平面图 如果能把一个图在平面上画成除端点外，任何两边都不相交， 则称此图为可平面的， 或称平面图。北京工业大学软件学院张丽离散数学平面图示例北京工业大学软件学院张丽离散数学平面图示例北京工业大学软件学院张丽离散数学非平面图示例北京工业大学软件学院张丽离散数学非平面图示例北京工业大学软件学院张丽离散数学区域 平面图的边把平面图划分成的块 例如 平面图将平面划分成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=9<m，不满足平面图的必要条件，所以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由此可得n<11，这和假设n≥11矛盾，证毕。北京工业大学软件学院张丽离散数学二度同构 如果两个图是由同一个图的边上插入一些新的顶点(它一定是2度点)而得到的， 则称这两个图是二度同构的。北京工业大学软件学院张丽离散数学二度同构北京工业大学软件学院张丽离散数学库拉托夫斯基定理 一个图是平面图的充分必要条件是该图不包含二度同构于K5或K3,3的子图。北京工业大学软件学院张丽离散数学非平面图证明例2 证明所示图是非平面图。 证明 把图中的边ED删去后，所得的子图就是K3,3，所以此图是非平面图。北京工业大学软件学院张丽离散数学非平面图证明例3 证明彼得逊图是非平面图。北京工业大学软件学院张丽离散数学非平面图证明例3 证明 把DE和FH删去，与K3,3是二度同构的，所以彼得逊图是非平面图。
本文档为【欧拉公式证明】，请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑，
图片更改请在作品中右键图片并更换，文字修改请直接点击文字进行修改，也可以新增和删除文档中的内容。
该文档来自用户分享，如有侵权行为请发邮件ishare@vip.sina.com联系网站客服，我们会及时删除。
[版权声明] 本站所有资料为用户分享产生，若发现您的权利被侵害，请联系客服邮件isharekefu@iask.cn，我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权，请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传，仅限个人学习分享使用，禁止用于任何广告和商用目的。
浙公网安备 33021202002483