拓扑图论基础：（二）图的嵌入和拓扑图
拓扑图论基础（二）
图的嵌入和拓扑图
拓扑图·平面图
设\(\Gamma\)是一个闭曲面或平面，\(G\)是一个图，\(D\)是\(G\)的一个正规\(\Gamma\)-画法．如果\(D\)没有交叉，我们就说\(D\)是\(G\)的一个\(\Gamma\)–嵌入，也说\(G\)通过\(D\)嵌入到\(\Gamma\)上．当\(\Gamma\)是平面时，我们称\(\Gamma\)-嵌入为平面嵌入．称能嵌入平面的图为可平面图．如果固定图\(G\)的\(\Gamma\)-嵌入\(D\)，并将\(G\)与\(D\)等同看待，那么\(G\)的顶点和边分别可以看成\(\Gamma\)上的相应点和相应简单（闭）曲线，此时我们称\(G\)为\(\Gamma\)上的拓扑图；特别地，如果\(\Gamma\)是平面，那么就称拓扑图\(G\)为平面图．
注意
可平面图和平面图是不同的．一个可平面图可能有多种平面嵌入，而平面图则固定了一种平面嵌入；一个可平面图本质上仍然是由顶点集和边集构成的有序二元组，而平面图实际上是一种拓扑图，它是由顶点集、边集和面集构成的有序三元组\(G(V,E,F)\)．
拓扑图的面
设\(G\)是\(\Gamma\)上的一个拓扑图．我们称\[\Gamma\setminus\bigcup_{e\in E(G)}e\]的区域（即极大弧连通子集）为\(G\)的面．\(G\)的面集用\(F(G)\)或\(F\)表示，面数用\(f(G)\)表示．
设\(f\in F(G)\)．\(f\)的边界记作\(\partial(f)\)．\(\partial(f)\)可以看作\(G\)的一个拓扑子图，但未必是连通图．实际上，当且仅当\(G\)连通时，\(G\)的每个面的边界才都是连通图．
如果\(\partial(f)\)只有一个连通分支，那么\(\partial(f)\)显然是一条闭游走(closed walk)，我们称之为\(f\)的边界闭游走；\(f\)的边界闭游走的长度称为\(f\)的度，记作\(\deg(f)\)．
\(\deg(f)\)不一定等于\(f\)所关联的边数．这是因为：如果\(f\)关联了割边\(e\)，那么\(e\)两侧都是\(f\)，这导致\(e\)在\(\partial(f)\)中会出现两次．但这并不影响握手定理的成立．
（面边）握手定理
如果\(G\)是平面图，那么\[\sum_{f\in F(G)}\deg(f)=2e(G).\]
面圈
如果\(\partial(f)\)是一个圈，那么我们称这个圈是一个面圈(facial cycle)．同样因为\(f\)可能关联割边，所以边界闭游走不一定是圈，除非\(G\)是2-连通的．
Whitney定理
Whitney定理 除\(K_1\)和\(K_2\)外，\(2\)-连通的平面图的每个面的边界都是圈．\(\blacksquare\)
Whitney定理的推论 无环\(3\)-连通的平面图的任何顶点的邻域都会构成一个圈．\(\blacksquare\)
一般来讲，如果\(G\)有一个\(\Gamma\)-嵌入，使得每个面都同胚于圆盘，则称这个嵌入是一个2-腔胞嵌入．什么图在什么闭曲面上会有2-腔胞嵌入，这是拓扑图论的一个重要研究课题，此处不便展开．
Eular-Poinare公式
关于顶点、边、面三者之间的数量关系有著名的Eular-Poinare公式：
Eular-Poinare公式 如果\(\Gamma\)上拓扑图\(G\)是连通的，那么\(v(G)-e(G)+f(G)=2-eg(\Gamma)\)．\(\blacksquare\)
将Eular-Poinare公式限制在平面图上使用（此时一般称为Eular公式）可以得到如下两个常用推论．
Eular公式的推论1 如果\(G\)是至少\(3\)个顶点的简单可平面图，那么\(e(G)\le 3v(G)-6\)，其中等号成立当且仅当\(G\)的每个平面嵌入都是三角剖分（即每个面的边界都是\(3\)-圈的平面嵌入）．\(\blacksquare\)
Eular公式的推论2 每个简单可平面图最小度都不超过\(5\)．\(\blacksquare\)