四色问题讲座：第十五讲 有关图论中的一些基本概念

雷明85639720

四色问题讲座：第十五讲  有关图论中的一些基本概念  
雷  明
在前些期的讲座中，我们用到了图论中的一些基本的概念，有的进行了解释，有的没有进行解释，现在在这里把所能想到的、已在讲座中提到了的统统再给大家讲解一遍，以便使一些不懂图论的朋友也能够看得明白。
首先说什么是“图”。由若干个“点”（图论中叫“顶点”）和某些点与点之间的“连线”（图论中叫“边”或“线”）构成的“图形”就叫做“图”。如铁路示意图，供电网络图，供水网络图和通信网络等等，其中的“点”就是城市或车站，工矿企业，机关单位和学校等，而其中的“线”就是铁路，电力线路，共水管线，通信线路等等。去掉图中顶点与边的具体含义，把顶点看成是不同的事物，把边看成是事物与事物之间的一种联系，这些网络就成了数学中的“图”。画图中各顶点在图纸上的相对位置，点的大小，以及边的长短和曲直都是无所谓的，都是可以改变的，关键的是要在有联系的两个事物的点间画上一条线。可以这样说，图是由许多实际问题经过抽象而得到，用顶点和连接这些顶点之间的线段（即边）共同构成的。图论，顾名思义，就是研究“图”的理论。客观世界里的若干事物（有限或无限）或社会上的若干现象，在某些事物与事物之间，现象与现象之间，或事物与现象之是有某种的联系或关系，研究这些联系或关系，从中找出某种规律，这就是图论所研究的内容。四色问题所研究的地图染色主要是指对行政区划地图的染色。
平面图：画在平面上，除了在顶点处有边与边相交叉外，其它任何地方都不会出现边与边相交叉情况的图。否则就是非平面图。
3—正则平面图：图中所有顶点都只连有三条边的平面图。地图就是3—正则的平面图。
极大平面图：图中所有面都是三边形的平面图。
对偶图：对偶图是一种图值函数，是把原图的面作新的顶点，把相邻各面的新顶点用新边连接起来所得到的新图，即是对偶图。极大平面图与3—正则平面图是互为对偶图的。极大平面图的顶点就是3—正则平面图（地图）中的面（区域）。
完全图：各顶点都相互有边相连的图是完全图。完全图有的是平面图，但多数都是非平面图。顶点数小于等于4完全图才是平面图。
同顶点数的完全图，极大平面图，非极大平面图的边数间的关系：完全图的边数e=v（v－1）/2＞极大平面图的边数e=3v－6＞非极大平面图的边数e＜3v－6。
色链：用两种颜色交替着色的一条道路。
道路：是一个顶点—边—顶点的序列。有直道路和圈（环形道路）两种。
相反链：两条链中的两种颜色均不同的链，如A—B链和C—D链就是相反链。
相邻链：两条链中的两种颜色有一种相同的链，如A—C链和A—D链就是相邻链。
连通链：在不相邻的两个围栏顶点间有一条链把该两个围栏顶点连接了起来，该链就叫连通链。否则就叫不连通链。不连通链是可以交换的，是可以从围栏顶点中空出颜色的，而连通链则不能交换，交换了也是空不出颜色的。
对角链：由不相邻的两个围栏顶点的颜色所构成的色链叫对角链。
邻角链：由相邻的两个围栏顶点的颜色所构成的色链叫邻角链。
环形链：该条链是一个闭合回路，该链一定是偶数顶点。没有构成闭合回路的链就叫直链。
轮形图（轮）：顾名思义，就是象车轮一样的图。有轮心顶点，有轮沿顶点，有轮幅边（边），象一个车轮一样。
轮构形：就是以轮心顶点为待着色顶点的构形。（讲座完）

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，

雷明85639720

，，，，，，，，