西安电子科技大学：《离散数学》课程教学课件（题解）第七章 图论 7-5 平面图

西安电子科技大学离散数学软件学院第四篇图论第6章图论第27-28课时6.1图的基本概念X→第29课时6.2路径与回路→第30课时6.3图的矩阵表示第31-32课时→6.4欧拉图与汉密尔顿图A6.5平面图第33课时第34课时A6.6图的着色6.7 树第35-36课时6.8图的应用第3738课时

西安电子科技大学 离散数学 软件学院 第四篇 图论 6.1 图的基本概念 第6章 图论 6.4 欧拉图与汉密尔顿图 6.2 路径与回路 6.5 平面图 第29课时 第33课时 第30课时 6.3 图的矩阵表示 第34课时 6.6 图的着色 第31－32课时 第35－36课时 6.7 树 第27－28课时 第37 －38课时 6.8 图的应用

西安电子科技大学平面图的定义$6.5.1软件学院家家务设G-是一个无向图，如果能够把图G图示在一平面图个平面上，使得任意两条边仅在端点处相交，则称G为平面图，这样的图示称为G的一个平面嵌入。4

西安电子科技大学 平面图的定义 软件学院 平面图 §6.5.1

西安电子科技大学平面图的定义$6.5.1软件学院例题判断下图是否是平面图解答：虽然图中有边在非端点处相交，但将其中两条边拉开后，该图可以图示在一个平面上使得任意两条边仅在端点处相交，因此它是平面图

西安电子科技大学 §6.5.1 平面图的定义 软件学院

西安电子科技大学平面图的定义$6.5.1软件学院乐【例题】判断K33是否是平面图。解答：K33无论如何画，总有边在非端点处相交，它是非平面图

西安电子科技大学 §6.5.1 平面图的定义 软件学院

西安电子科技大学S6.5.1平面图的定义软件学院家家【思考题】（五王子修路问题】传说欧洲有个国王生有五个儿子，在临死前留下遗嘱，将自己的士地分给了这五个儿子。五个子在各自的领地上分别修筑了宫殿，并且想在每两座宫殿间都修建一条直达的道路，并且要求任意两条道路都不交叉，问他们门的愿望能实现吗？

西安电子科技大学 §6.5.1 平面图的定义 软件学院

西安电子科技大学平面图的定义$6.5.1软件学院家设G是一连通平面图，由图G中的若干条边所包围面的区域，并且在该区域内不再包含图G中的边和结点，这样的区域称为图G的面。有限面：区域面积有限的面称为有限面，无限面：区域面积无限的面称为无限面

西安电子科技大学 软件学院 面 §6.5.1 平面图的定义

西安电子科技大学平面图的定义$6.5.1软件学院家家设是连通平面图G的一个面，包围面r的所有边面的边界构成的回路称为该面的边界。设r是连通平面图G的一个面，面r的边界回路长面的次数度称为该面的次数，记为deg(r)

西安电子科技大学 软件学院 面的边界 面的次数 §6.5.1 平面图的定义

西安电子科技大学平面图的定义$6.5.1软件学院【例题】求平面图G中的所有面的次数。Jf解答：平面图G中共有5个面，分别是图中i、r2、t3、4、rs所在区域，其中1是一个无限面，其余都是有限面。次数边界注解面deg(ri)+34rit((a,e), (e, d), (d,a))322r2t((a,b), (b, d), (d,a))432r3+((a,b), (b, c), (c,e), (e,a))-34r44((b,c), (c, c), (d,b)52rse《c,d)(d,e),（ef),(f,e)边(e,f)作为面r的边界被计算两次

西安电子科技大学 §6.5.1 平面图的定义 软件学院

西安电子科技大学$6.5.1平面图的定义软件学院家家家茶家案定理1设G-是一连通平面图，则图G中所有面的次数之和等于边数的两倍。+Z deg(r)=2|E|rEG

西安电子科技大学 §6.5.1 平面图的定义 软件学院

西安电子科技大学$6.5.2 区欧拉公式软件学院家教家茶家案定理！设有一个连通平面图G，它有n个结点，m条边和r个面，则有n-m+r=2成立。+证明：（采用归纳法：对边数m进行归纳）(i）当m=O时，连通图G是一个孤立结点，则有n=1，m=0,r=1，故n-m+r=2成立当m=1时有以下两种情况（如图所示）：OOn=1, m=0,r=1n=1, m=0, r=1均有n-m+r=2成立

西安电子科技大学 §6.5.2 欧拉公式 软件学院 证明：（采用归纳法：对边数m进行归纳） （i）当m=0时，连通图G是一个孤立结点，则有 n=1, m=0, r=1，故n-m+r=2成立。 当m=1时有以下两种情况（如图所示）： n=1, m=0, r=1 n=1, m=0, r=1 均有n-m+r=2成立