高等数学-离散数学及其应用--第十一章几种特殊的图介绍.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 次数的性质 定理17.4 平面图各面次数之和等于边数的两倍. 证 对每一条边e, 若e在两个面的公共边界上, 则在计算这两 个面的次数时, e各提供1. 而当e只在某一个面的边界上出现 时, 它必在该面的边界上出现两次, 从而在计算该面的次数时, e提供2． * 极大平面图 定义11.8 G为简单平面图, 若在G的任意两个不相邻的顶点 之间加一条边所得图为非平面图, 则称G为极大平面图. 例如, K5,K33删去一条边后是极大平面图 K1, K2, K3, K4都是极大平面图. 定理11.10 设G为n(n?3)阶简单连通的平面图, G为极大平面图当且仅当G的每个面的次数均为3. 证 现只证必要性. 各面次数都大于或等于3. 假如deg(Ri)=s?4, 若v1与v3不相邻, 则在Ri内加边(v1,v3)不 破坏平面性, 与G是极大平面图矛盾, 因 而v1与v3必相邻, 且边(v1,v3)必在Ri外部. 同样地, v2与v4也相邻且边(v2,v4)在Ri的 外部. 于是, (v1,v3)与(v2,v4)相交于Ri的外 部, 与G是平面图矛盾. * 例 是否是极大平面图? 定理的应用 只有(3)为极大平面图 (1) (2) (3) * 极小非平面图 定义11.9 若在非平面图G中任意删除一条边, 所得图为平面图, 则称G为极小非平面图. K5, K3,3都是极小非平面图 极小非平面图必为简单图 * 欧拉公式 定理11.11 设G为n阶m条边r个面的连通平面图, 则 n?m+r=2 证 对m做归纳证明. m=0时, G为平凡图, n=1,m=0,r=1,成立. 设m=k(k?0)时结论成立. 当m=k+1时, 分两者情况讨论: (1) G中有一个1度顶点v, 令G? =G?v, 仍是连通的, n? =n?1, m? =m?1=k, r? =r. 由归纳假设, n??m? +r? =2. 于是 n?m+r = (n? +1)?(m? +1)+r? = n? ?m? +r? = 2 (2) G中没有1度顶点, 则每一条边都在某两个面的公共边界 上. 任取一条边e, 令G? =G?e, 仍连通且n? =n, m? =m?1=k, r? =r?1. 由归纳假设, n? ?m? +r? =2. 于是 n?m+r = n? ?(m? +1)+(r? +1) = n? ?m? +r? = 2 * 欧拉公式的推广 推论 对于有k个连通分支的平面图G, 有 n ? m + r = k+1 其中n, m, r分别为G的顶点数, 边数和面数. 证 设G的连通分支为G1,G2,…,Gk, 由欧拉公式 ni ? mi + ri = 2, i=1,2,…,k. G的面数 . 于是， 整理得 n ? m + r = k+1 * 解得 与欧拉公式有关的定理 定理11.12 设G为连通的平面图, 每个面的次数至少为l?3，则 证 由定理11.9及欧拉公式, 定理11.13 K5, K3,3都是非平面图. 证 假设K5是平面图, K5无环和平行边, 每个面的次数均大于等 于3. 应该有 矛盾. * 证(续) 假设K3,3是平面图, K3,3中最短圈的长度为4, 每个面的次数均大于等于4. 应该有 矛盾. 定理11.14 设G为n(n?3)阶m条边的极大平面图, 则m=3n?6. 证 极大平面图是连通图, 由欧拉公式得 r = 2+m?n. 又由定理11.10的必要性, G的每个面的次数均为3, 所以2m=3r. 得m=3n?6． 推论 设G是n(n?3)阶m条边的简单平面图, 则 m?3n?6 与欧拉公式有关的定理 * 如果简单连通平面图G的每个面的次数都等于3, 则G为极大平面图. 证 由定理11.9, 2m=3r