拓扑图论基础：（一） 图的画法和交叉数
拓扑图论基础（一）
图的画法和交叉数
本系列笔记中所讨论的图是有限的、无向的、允许重边(multiedge)和环(loop)的．
由于本文涉及到图论和拓扑学两个数学分支，为了避免术语上的混淆（中文的无奈），我们称图的vertex为顶点，我们称点集拓扑中拓扑空间上的point为点．
-
二维流形
设\(\Gamma\)是一个豪斯多夫空间．如果\(\Gamma\)上的每一个点都有一个开邻域同胚于欧氏平面\(\mathbb{E}^2\)中的开圆盘，那么我们就说\(\Gamma\)是一个二维流形．
-
曲线·闭曲线·简单曲线·简单闭曲线
设\(\Gamma\)是一个二维流形，而\(f\)是一个从闭区间\([0,1]\)到\(\Gamma\)的连续映射．我们令\(A=f([0,1])\)．那么我们就说\(A\)是\(\Gamma\)上的一条曲线，其中\(f(0)\)和\(f(1)\)就是曲线\(A\)的端点；如果\(f\)是单射，那么\(A\)就是一条简单曲线；如果\(A\)的两个端点是重合的，那么\(A\)就是一条闭曲线；如果\(f\)在开区间\((0,1)\)上是单射并且\(A\)的两个端点重合，那么\(A\)就是一条简单闭曲线．
-
曲线段
设\(0\le a<b\le1\)．如果\(A\)不是闭曲线，那么，\(f([a,b])\)就是曲线\(A\)上从\(f(a)\)到\(f(b)\)的一个曲线段；如果\(A\)是闭曲线，那么，\(f([a,b])\)或\(f([0,a]\cup[b,1])\)就是曲线\(A\)上从\(f(a)\)到\(f(b)\)的一个曲线段．
-
曲面·闭曲面
如果二维流形\(\Gamma\)上任意两点间总有一条简单曲线连接，那么我们就说\(\Gamma\)是弧连通的．但是，二维流形未必都是弧连通的．在包含意义下极大的弧连通子集被称为区域．如果\(\Gamma\)中任意开覆盖都有有限子覆盖，则称\(\Gamma\)是紧致的．紧致的、弧连通的二维流形就是曲面．没有边界的曲面称为闭曲面．
欧氏平面是二维流形但不是曲面，因为它无界因而不紧致；莫比乌斯带是曲面但不是闭曲面，因为它有边界；球面、环面、射影平面、克莱因瓶都是常见的闭曲面．
-
欧拉亏格
根据著名的闭曲面的分类定理，我们知道：任何闭曲面总是可以通过给球面添加环柄和交叉帽来得到．
设闭曲面\(\Gamma\)是从球面添加\(h\)个环柄和\(c\)个交叉帽得到的．当且仅当\(c=0\)时，\(\Gamma\)才是可定向的曲面．令\(eg(\Gamma)=2h+c\)，我们称之为闭曲面\(\Gamma\)的欧拉亏格．一般所说的欧拉示性数是[\chi(\Gamma)=2-eg(\Gamma)，]在拓扑图论中通常回避这个参数．
众所周知，借助球极射影，可以将删除一点（北极）后的球面与欧氏平面建立同胚关系，所以，我们规定欧氏平面的欧拉亏格与球面相同，即\(eg(\mathbb{E}^2)=0\)．在以后的讨论中，我们简称欧氏平面为平面．
-
图的画法(drawing of a graph)
设\(\Gamma\)是一个闭曲面或平面，\(G\)是一个图．\(G\)的\(\Gamma\)-画法是由两个单射\(\varphi\)和\(\psi\)构成的有序对，记作\(D(\varphi,\psi)\)，简记作\(D\)．其中，\(\varphi\)将\(G\)的顶点映射为\(\Gamma\)的点，我们仍然称\(\varphi\)的像是\(D\)的顶点；而\(\psi\)将\(G\)的边映射为连接相应顶点的简单曲线（环被映射为简单闭曲线），我们仍然称\(\psi\)的像是\(D\)的边．\(D\)的顶点的全体记作\(V(D)\)，\(D\)的边的全体记作\(E(D)\)．设\(p\in \Gamma\)，\(e\in E(G)\)．
如果\(p\in \psi(e)\)且不是\(\psi(e)\)的端点，那么我们说\(\psi(e)\)穿过(pass through)点\(p\)．
-
图的正规画法(normal drawing of a graph)
如果\(G\)的\(\Gamma\)-画法\(D\)还满足：
* 任意边不穿过顶点，
* 任意两边不相切，
* 任意两边公共点有限，
* 任意三边不穿过同一点，
那么我们就说\(D\)是\(G\)的正规\(\Gamma\)-画法． -
交叉和交叉数(crossing and crossing number)
设\(D\)是图\(G\)的正规\(\Gamma\)-画法，\(e_1,e_2\in E(G)\)，\(p\in \Gamma\)．如果\(\psi(e_1),\psi(e_2)\)都穿过\(p\)，就说\(e_1\)和\(e_2\)在\(D\)上交叉于\(p\)，也说\(p\)是\(D\)的一个交叉．\(D\)上交叉的全体叫做\(D\)的交叉集，记作\(CR_{\Gamma}(D)\)．\(D\)上交叉的总数叫做\(D\)的交叉数，记作\(cr_{\Gamma}(D)\)．
设\(\mathcal{D}\)是\(G\)的所有正规\(\Gamma\)-画法的全体．定义\(G\)在\(\Gamma\)上的交叉数为
[cr_\Gamma(G)=\min_{D\in \mathcal{D}}cr_\Gamma(D).] -
图的交叉数问题
如果\(D\)是使得\(cr_\Gamma(D)=cr_\Gamma(G)\)的正规\(\Gamma\)-画法，那么我们就称\(D\)是\(G\)在\(\Gamma\)上的cr-最小画法．求图\(G\)在\(\Gamma\)上的交叉数和cr-最小画法的问题，就是图交叉数问题．
-
部分交叉数
设\(S\subseteq \Gamma\)，令\(CR_{\Gamma,D}(S)=CR_\Gamma(D)\cap S\)，令\(cr_{\Gamma,D}(S)=|CR_{\Gamma,D}(S)|\)．例如，在正规\(\Gamma\)-画法\(D\)上，边\(e\in E(D)\)上所包含的交叉的集合和个数，就可以分别记作：\(cr_{\Gamma,D}(e)\)和\(cr_{\Gamma,D}(e)\)．
-
注意
特别地，如果\(\Gamma\)是平面\(\mathbb{E}^2\)，那么，上述符号中的\(\Gamma\)通常省略；上述术语中的\(\Gamma\)通常换成“平面”．所以\(CR_{\mathbb{E}^2}(\cdot)\)和\(cr_{\mathbb{E}^2}(\cdot)\)一般也写成\(CR(\cdot)\)和\(cr(\cdot)\)．
-
注意
在图\(G\)的\(\Gamma\)-画法\(D\)中，由于图\(G\)的边被映射成了简单曲线或简单闭曲线，所以\(D\)的任何边不会和自己交叉．