复旦大学：《离散数学——集合与图论》PPT课件（赵一鸣）23/30

◆对于简单图来讲,它的每个内部面至少 要由三条边围成,每条边最多为两个面 的边界。 ◆定理6.1:若连通平面图G有n个顶点,e条 边和个面,则ne+2-称为欧拉公式 ◆证明:对边数进行归纳证明:对于一条边 的连通平面图, 第一个n=2,f=1,e=1,n-e+f=2,成立 第二个n=1,f=2,e=1,n-e+f=2成立

 对于简单图来讲，它的每个内部面至少 要由三条边围成，每条边最多为两个面 的边界。  定理6.1：若连通平面图G有n个顶点,e条 边和f个面,则n-e+f=2---称为欧拉公式  证明：对边数进行归纳证明: 对于一条边 的连通平面图, 第一个n=2,f=1,e=1,n-e+f=2,成立 第二个n=1,f=2,e=1,n-e+f=2,成立

◆假设对于一切m-1条边的连通平面图,欧拉 公式均成立。现考察m条边的连通平面图。 (1)若G有一个度数为1的顶点,则删去该顶 点及其关联边,便得到一个连通平面图G 删去度数为1的顶点不影响连通 性。而且度数为1的顶点不在回 路上,因此不会增加和减少回 路数。因此面数不变

 假设对于一切m-1条边的连通平面图, 欧拉 公式均成立。现考察m条边的连通平面图。  (1)若G有一个度数为1的顶点, 则删去该顶 点及其关联边, 便得到一个连通平面图G'。 删去度数为1的顶点不影响连通 性。而且度数为1的顶点不在回 路上，因此不会增加和减少回 路数。因此面数不变

Q'名没有度数为顶点则删去同 上的一条边不影响连通性,因此得到 个连通平面图G

 (2)若G中没有度数为1的顶点,则删去一个 有界面边界上的任一条边,因为删去回路 上的一条边不影响连通性，因此得到一 个连通平面图G

◆对于平面图,嵌如平面的画法可以有多 种,但不管怎样,面数总是相等的。必 须强调的是:欧拉公式只适用于连通平 面图, ◆即任何一个连通平面图一定满足欧拉公 式, 不满足欧拉公式的连通图一定不是平面 ◆但是面数确定是比较困难的

 对于平面图，嵌如平面的画法可以有多 种，但不管怎样，面数总是相等的。必 须强调的是：欧拉公式只适用于连通平 面图，  即任何一个连通平面图一定满足欧拉公 式，  不满足欧拉公式的连通图一定不是平面 图。  但是面数确定是比较困难的

◆推论61:若G是n3的平面简单图,则e≤3n-6 证明显然只要对连通平面简单图证明即可。 c设G是n3的连通平面简单图G的每个面由 条或更多条边围成因此边的总数s大于或等于 3f这里边的总数包括重复计算在内) 即s≥3f s=4+3+3+6=16 另一方面,因为每条边至多是两个 面的公共边,也就是说每条边至多 被计算两次,即s2e

 推论 6.1：若G是n3的平面简单图, 则e3n-6。  证明:显然只要对连通平面简单图证明即可。  设G 是n3的连通平面简单图,G的每个面由三 条或更多条边围成,因此边的总数s大于或等于 3f(这里边的总数包括重复计算在内)。  即s3f s=4+3+3+6=16 另一方面, 因为每条边至多是两个 面的公共边, 也就是说每条边至多 被计算两次,即s2e

◆由此定理我们可以证明K是非平面图, ◆因为K是连通的, ◆n=5,e=10, ◆若K是平面图,则由推论应该有es3n-6 ◆即10≤3*5-6=9, ◆矛盾,所以K不是平面图。 在这里要注意:对于n≥3的平面简单图, 定成立e≤3n-6。 ◆若e>3n-6,则一定不是平面图。 ◆但对于简单图,即使满足e≤3n-6,也不一定 是平面图。 ◆例如,K3,m=6e-9,3n6=36-6=12>9=e, 成立,但K3不是平面图

 由此定理我们可以证明K5是非平面图,  因为K5是连通的，  n=5,e=10，  若K5是平面图，则由推论应该有e3n-6  即103*5-6=9,  矛盾，所以K5不是平面图。  在这里要注意：对于n3的平面简单图, 一 定成立e3n-6。  若e>3n-6,则一定不是平面图。  但对于简单图，即使满足e3n-6，也不一定 是平面图。  例如，K3,3，n=6,e=9, 3n-6=3*6-6=12>9=e， 成立，但K3,3不是平面图

◆推论6:若平面图的每个面由四条或更 多条边围成,则e≤2n-4 ◆证明:因为每个面由四条或更多条边围 成,因此边的总数s大于或等于4f;即 s≥4f ◆证明K3不是平面图

 推论 6.2：若平面图的每个面由四条或更 多条边围成, 则e2n-4  证明：因为每个面由四条或更多条边围 成，因此边的总数s大于或等于4f，即 s4f  证明K3,3不是平面图

定理62:在平面简单图G中至少存在一个顶 点wo,使得d(vo≤5 证明:用反证法证明。 假设一个平面简单图的所有顶点度数大于5。 即d(v)≥6。 又由欧拉公式推论61有3n6≥e, 所以6n-12≥2e=∑()26n 这是不可能的。 因此平面简单图中至少有一个顶点v,它的度 数d(vo)≤5

定理 6.2:在平面简单图 G 中至少存在一个顶 点 v0,使得 d(v0 ) 5。 证明：用反证法证明。 假设一个平面简单图的所有顶点度数大于 5。 即 d(v)6。 又由欧拉公式推论 6.1 有 3n-6e, 所以 6n-122e= d v n v V  ( )  6  这是不可能的。 因此平面简单图中至少有一个顶点 v0,它的度 数 d(v0 )5

例:小于30条边的连通平面简单图中存 在顶点度数不超过4的顶点。 证明:若所有顶点度数都大于4,即G中 所有顶点度数都≥5

 例：小于30条边的连通平面简单图中存 在顶点度数不超过4的顶点。  证明：若所有顶点度数都大于4，即G中 所有顶点度数都5

◆二、平面图的特征 ◆找出一个图是平面图的充分必要条件的 研究曾经持续了几十年,直到1930年库 拉托斯基( Kuratowski)给出了平面图的 一个非常简洁的特征

 二、平面图的特征  找出一个图是平面图的充分必要条件的 研究曾经持续了几十年, 直到 1930 年库 拉托斯基 (Kuratowski) 给出了平面图的 一个非常简洁的特征