壽区域( region):不含顶点与边的极大连通曲 面,R 外部区域( exterior region):面积无限的区 域R0 区域边界( boundary of region):R与R 关联的边和顶点构成的子图 面(face):区域及其边界 面的次数( degree):deg(R)=边界长度 《集合论与图论》第23讲
《集合论与图论》第23讲 11 面 区域(region):不含顶点与边的极大连通曲 面, R 外部区域(exterior region): 面积无限的区 域, R0 区域边界(boundary of region): 与R 关联的边和顶点构成的子图 面(face): 区域及其边界 面的次数(degree): deg( R )=边界长度 ∂R
定理 定理112=1deg(R)=2m.# 婚定理113任何平面嵌入的内部面都可以 在另一种平面嵌入下成为外部面 证明:平面嵌入→球面嵌入→把该面旋 转到北极→平面嵌入.# 《集合论与图论》第23讲
《集合论与图论》第23讲 12 定理 定理11.2: Σri=1deg(Ri)=2m. # 定理11.3: 任何平面嵌入的内部面都可以 在另一种平面嵌入下成为外部面 证明: 平面嵌入Æ 球面嵌入Æ 把该面旋 转到北极 Æ 平面嵌入. #
极大(maxm)平面图 极大平面图:是平面图,但是在任意两个 不相邻顶点之间加边就是非平面图 鼙定理14:(3阶简单连通平面图是极大 平面图台→ VR, deg(R)=3 证明:(=)简单图→deg(R)≥3, 极大平面图→deg(R)≤3 (=)R,degR)=3→不能加边而不交叉.# 秦极小非平面图:是非平面图,但是删除任 意边就是平面图 《集合论与图论》第23讲 13
《集合论与图论》第23讲 13 极大(maximal)平面图 极大平面图: 是平面图, 但是在任意两个 不相邻顶点之间加边就是非平面图 定理11.4: n(≥3)阶简单连通平面图是极大 平面图⇔∀R,deg( R )=3 证明: (⇒)简单图⇒deg( R )≥3, 极大平面图⇒deg( R )≤3 (⇐)∀R,deg(R )=3⇒不能加边而不交叉. # 极小非平面图:是非平面图, 但是删除任 意1边就是平面图
欧拉公式 秦欧拉公式:设G是连通平面图,则 n-m+r=2 其中r是G的面数 秦例:∩=7,m=11=6:7-11+6=2.# 《集合论与图论》第23讲
《集合论与图论》第23讲 14 欧拉公式 欧拉公式: 设G是连通平面图, 则 n-m+r=2 其中r是G的面数. 例: n=7,m=11,r=6: 7-11+6=2. #
欧拉公式(推广形式) 秦欧拉公式:设G是平面图,则 n-m+r=1+ 其中是G的面数,p是G的连通分支数 证明:(破圈法)任选一个回路,删除回路上1 边,m=m-1,这边分隔的2个面合并r=-1, 所以n-m+r=n-m+r.到最后无回路时是 森林,m”=np,r”=1,即n-m+r=n m”+r'=1+p.# 《集合论与图论》第23讲 15
《集合论与图论》第23讲 15 欧拉公式(推广形式) 欧拉公式: 设G是平面图, 则 n-m+r=1+p 其中r是G的面数, p是G的连通分支数 证明:(破圈法)任选一个回路,删除回路上1 边,m’=m-1,这边分隔的2个面合并,r’=r-1, 所以n-m+r=n-m’+r’. 到最后无回路时是 森林, m’’=n-p, r’’=1, 即n-m+r=nm’’+r’’=1+p. #