[讨论]图论专业术语简单介绍

雷明85639720

图论专业术语简单介绍
雷  明
（二○一三年五月二十八日）
（图见以上DOC文件）
1、图：图是一些“顶点”和顶点与顶点之间的、叫做“边”的联线所构成的集合（见附图）。顶点代表事物，边代表事物与事物间的联系。图是具有拓扑性质的，顶点无大小之分，边无长短、曲直之分，但顶点间的边，即事物与事物的联系关系是不能变的。图1 和图2看上去很不相同，但的却又是同一个图，因为它们的各顶点之间的相连关系是相同的。由某些边所围成的闭合区域叫做“面”，如图1中分别由顶点1、2、4和2、3、4所围成的区域就是面。
2、相邻与不相邻：两个有边相连的顶点叫相邻顶点，否则是不相邻顶点。图1 中顶点2 和3之间有边相连，是相邻的顶点，顶点5和6之间没有边相连，是不相邻的顶点。
3、同化：把不相邻的两个顶点凝结在一起的过程叫同化。例如把图1中的不相邻的顶点1 和5 凝结到了一起，这个过程就是同化，如图5。
4、团：图中在某些顶点间，两两顶点之间都有边相连的那些顶点和那些边构成的分子图叫做团。如图1 中顶点1、2、3或顶点2、3、4中，两两顶点间都有边相连；顶点2、3间，顶点3、6间都有边相连，也是两两顶点间都有边相连的，等等等等，这些都是图中的“团”，用Kn表示，n是团中两两相邻的顶点数。图中顶点数最多的团叫该图的最大团。图1 中的图的最大团的顶点数是3，其最大团就是K3，该 图的密度也是3。
5、完全图非完全图：一个图中所有的顶点都是两两均相邻的顶点，这样的图叫完全图。完全图也用Kn表示，下角n是完全图中的顶点数。图3就是一个完全图K5。
6、平面图与非平面图：一个图画在平面上，除了顶点处外，其他任何地方都不存在两条边相交叉的情况，这样的图叫平面图，否则就是非平面图。图1 图2都是平面图，图3 图4则是非平面图，因为你不可能把图3 和图4 画在平面上时不存在交叉边。
7、四色猜测：也叫四色问题，是说对平面图的顶点（或面）着色（或染色），使得相邻的顶点（或相邻的面，即有公共边界的区域）具有不同的颜色，猜测四种颜色就够用了。
8、球面与平面：球面与平面在拓扑学中是一回事，平面是球面，球面也是平面。其亏格都是0。从测地学上讲，在地球仪的北极点放一个光源，把地图投影到一个平面上，北极点就成了平面的无限远点，球面就变成了平面。平面是物殊的曲面。
9、多阶曲面：在一个球面上“焊”上n个“环柄”，这个曲面的亏格就是n，球面上没有“环柄”，即“环柄”数是0，则球面的亏格就是0，那么平面的亏格也就是0；球面上有一个环柄时，其亏格就是1，拓扑变形后就是一个轮胎面，也有叫环面的，这个曲面中间有一个空洞（如图13）；球面上有两个环柄时，其亏格就是2，拓扑变形后就是一个眼镜匡面，即“8”字形曲面，也有叫双环面的，这个曲面中间有两个空洞（如图14）；等等。
10、嵌入：一个图画到某个亏格的曲面上时，如果不存在交叉边，就说该图能嵌入到该亏格的曲面上。图1 就可嵌入到球面（平面）上，但图3 和图4 就不能嵌入到球面（平面）上，因为把图画在平面上时，总是存在有交叉边。
11、图的亏格：一个图所能嵌入的曲面的最小亏格就是该图的亏格。图1的能嵌入球面（平面），其亏格就就是0，而图3 和图4的亏格一定是大于0的，因为它们不能嵌入到球面（平面）上。
12、图的色数：给图的顶点着上不同的颜色，使相邻的顶点具有不同颜色时，图中所用颜色的最少数，就是图的着色数。
13、顶独立集：由图中不相邻顶点所够成的集合就是顶独立集。该集合中的各个顶点均是不相邻的。
14、最小顶独立集数：是一个图所能划分成的最少的顶独立集的个数。
15、同态、完全同态、最小完全同态、最小完全同态的顶点数：把图中不相邻的两个顶点同化在一起后所得到的图叫原图的一个同态（如图5，把1和5 同化在一起）；在这个同态的基础上再进行一次同化所得的图也是原图的一个同态（如图6和图7）；一个图经过一系列的同化后，一定可得到一个完全图，这就是原图的完全同态（如图6 和图7）；在一个图的所有完全同态中必有一个的顶点数是最少的，这就是原图的最小完全同态（如图6 和图7），这个顶点数就是图的最小完全同态的顶点数。
16、最小完全同态：由于同化的路线不同，最后可能产生不同顶点数的完全同态，如图9的4 个顶点的道路图，把1和3、2 和4 分别同化在一起时得到的是一个K2图（如图10），但若把1 和4 同化在一起时就得到一个K3图（如图11），K2图的顶点数少，K2图就是这个道路的最小完全同态，其最小完全同态的顶点数就是2。

17、环：一个顶点上有一条边从该顶点出发，后又回到了该顶点，这样的边叫做环。如图12 中左图的顶点1上的一个园圈边就是环。
18、平行边：两个顶点间有两条以上的边时，这些边就叫平行边。如图12中右图顶点2 和3 间有两条边，这就是平行边。
19、单纯图与多重图：没有环与平行边存在的图叫做单纯图（如图1等），否则叫多重图（如图12中的每一个图都是多重图）。
20、连能通图与非连通图：在图中从任何一个顶点可以到达图中的其它所有顶点的图叫连通图（如图1 等），否则就是非连通图（如图12，左图中的顶点1 就不可能到达右图中的顶点2 和3 等）。
21、向上、向下取整：0.6向下取整时是0，向上取整时是1。
22、图的色数：一个图的最小完全同态有多少个顶点，着色时就得用多少种颜色。如图1 的最小完全同态是图6或图7，只有三个顶点，着色时只用了红、兰、黑3 种颜色，后然连同已着颜色，按同化时的相反方向返回到原图时，图1 着色就完成了，如图8。图1 的色数就是3。
    23、地图图的对偶图：地图是一个特殊的平面图，它的每一个顶点都连有三条边，这就是平时人们所说的“三不管地区”，这种图叫做三度正则图。对地图（平面图）的染色是对其面上的染色。把地图中每个区域的中心城市用一个顶点表示，把相邻区域的中心城市对应的顶点用线（边）连接起来，所得到的图就是地图的对偶图。地图的对偶图也是一个特殊的平面图，这个对偶图（平面图）的每一个面均是三边形面，这种图叫做极大图。可见对地图的面的染色就相当于对地图的对偶图的顶点着色，这就把一个地理问题变成了一个数学问题。同时，研究图的顶点着色比研究面的染色要方便得多，直观得多。这就是对偶图的好处。
24、从多阶区面上图的欧拉公式到多阶曲面上图的着色定理：可以从适合于任意亏格的多阶曲面上图的欧拉公式直接推导出多阶曲面上图的着色公式，这就是多阶曲面上图的着色定理。见笔者的《4—CC的证明——从欧拉公式到着色定理》一文，已发表在《数学中国》网上，网址是：
http://www.mathchina.com/cgi-bin/topic.cgi?forum=12&topic=3289&show=0，也可见“雷明的博客”，网址是：
http://blog.sina.com.cn/leiming1946。
25、多彩的着色定理：着色不光有平面（球面）上的图的着色问题，还有多阶曲面上图的着色问题。在每一种曲面亏格下，都存在一个着色色数的界（上界），这个界就是多阶曲面上图的着色定理。在于亏格为0 的平面（球面）上，有四色定理，在于亏格为1 的环面（轮胎面）上有七色定理，在亏格为2的双环面（眼镜匡面）上有八色定理，……，等等等等。非常的美丽。
雷  明
二○一三年五月二十八日