Theorem 9.1 (The Euler Identity)If G is a connected plane graph of order n,size m and having r regions,then n-m +r=2. 证明要点: 1,树是满足欧拉公式 2,反证法:如果除树外,欧拉公式不成立 2.1找一个边最少的图 如果我们用归纳 2.1.1必定存在回路 法证明该定理, 2.2去除回路上一条边,构造新图 该如何归纳? 2.2.1新图有n个点,m-1条边,r-1个区域 2.3新图满足欧拉公式(原图是最小的) 2.3.1n-(m-1)+(r-1)=2 2.3.2n-m+r=2 2.4矛盾 3,欧拉公式满足
证明要点: 1,树是满足欧拉公式 2,反证法:如果除树外,欧拉公式不成立 2.1 找一个边最少的图 2.1.1 必定存在回路 2.2 去除回路上一条边,构造新图 2.2.1 新图有n个点,m-1条边,r-1个区域 2.3 新图满足欧拉公式(原图是最小的) 2.3.1 n-(m-1)+(r-1) = 2 2.3.2 n-m+r=2 2.4 矛盾 3,欧拉公式满足 如果我们用归纳 法证明该定理, 该如何归纳?
简单连通平面图的必要条件 ■欧拉公式的推论:若G是简单连通平面图(≥3),则 m≤3n-6。 口证明:至少3个顶点的简单图G中,面的最小边数是3, ∴.3r≤2m,根据欧拉公式:3r=3m+6-3n,∴.3m+6-3n<2m,即: m≤3n-6。 ■K不是平面图:在K中,n=5,m=10,3n-6=9。 平面图中,边数是有上限的。请问,这个界是否紧致?
简单连通平面图的必要条件 ◼ 欧拉公式的推论:若G是简单连通平面图(n3), 则 m3n-6。 ❑ 证明:至少3个顶点的简单图G中,面的最小边数是3, 3r2m, 根据欧拉公式:3r=3m+6-3n, 3m+6-3n2m, 即: m3n-6。 ◼ K5不是平面图:在K5中,n=5,m=10, 3n-6=9。 平面图中,边数是有上限的。请问,这个界是否紧致?