下载文档原格式
图的平面性与图的着色问题在图论中，图的平面性与图的着色问题是两个重要的研究方向。
图的平面性指的是一种特殊的图的布局方式，使得图的边不相交。
而图的着色问题是指如何给图的顶点进行染色，使得相邻的顶点颜色不相同。
本文将分别介绍图的平面性和图的着色问题，并对其进行详细讨论。
一、图的平面性（Planarity of Graphs）图的平面性是图论中一个经典的问题，研究的是如何将一个图画在平面上，使得图的边不相交。
具体而言，如果一个图可以被画在平面上，且不同边的交点只有顶点，那么我们称该图是一个平面图。
而对于不能在平面上画出来的图，则被称为非平面图。
定理1：一个图是平面图，当且仅当它不包含任何的子图同构于以下两种图之一：K5（五个没有共同边的顶点）或K3,3（六个节点，其中任意两个节点之间都有边相连但不交叉）。
这个定理被称为Kuratowski定理，它为我们判断一个图是否是平面图提供了一个有效的方法。
根据Kuratowski定理，我们可以使用该定理的逆否命题，即如果一个图中包含K5或K3,3，则该图一定是非平面图。
除了Kuratowski定理之外，还有一种判断图的平面性的方法，称为Euler公式。
Euler公式表达了平面图的顶点数、边数和面数之间的关系：V - E + F = 2其中V表示顶点数，E表示边数，F表示面数。
根据Euler公式，对于简单连接图（无环，无孤立点），如果它的顶点数大于等于3且边数大于等于3，且满足Euler公式，则该图是一个平面图。
二、图的着色问题（Graph Coloring）图的着色问题是指如何给一个图的顶点进行染色，使得相邻的顶点颜色不相同。
这里的相邻指的是有边相连的顶点。
在图论中，颜色通常表示为正整数，颜色数则表示为给定图所需的最小颜色数。
对于任意图G，G的最小颜色数被称为G的色数。
如果图G的色数为k，则称图G是可k着色的。
求解一个图的最小色数是一个复杂的问题，称为顶点着色问题（Vertex Coloring Problem），它是一个NP 完全问题。
17.1 平面图的基本概念一、平面图及平面嵌入定义17.1如果图G能以这样的方式画在曲面S上，即除顶点处外无边相交，则称G可嵌入曲面S.若G可嵌入平面，则称G是可平面图或平面图。
画出的无边相交的图称为G的平面嵌入。
无平面嵌入的图称为非平面图。
K1(平凡图)，K2，K3，K4都是平面图，其中，K1，K2，K3本身就已经是平面嵌入，K4的平面嵌入为图17.1中(4)所示。
K5－e (K5删除任意一条边)也是平面图，它的平面嵌入可表示为图17.1中(5).完全二部图K1,n(n≥1), K2,n(n≥2),也都是平面图，其中标准画法画出的K1,n已经是平面嵌入，K2,3的平面嵌入可由图17.1中(6)给出。
图17.1中(1)，(2)，(3)分别为K4, K5－e, K2,3的标准画法。
请观看演示动画：(1)变(4)(2)变(5)(3)变(6)图17.1下文中所谈平面图，有时是指平面嵌入，有时则不是，这要看是研究平面图什么性质而定，请读者根据上下文加以区分。
当然有时也特别指出平面嵌入。
现在就应该指出，在研究平面图理论中居重要地位的两个图，这就是完全图K5和完全二部图K3,3，它们都不是平面图(将由定理17.10的推论得到证明)。
还有两个非常显然的事实，用下面定理给出。
定理17.1若图G是平面图，则G的任何子图都是平面图。
由定理17.1立刻可知，K n(n≤4)和K1,n(n≥1)的所有子图都是平面图。
定理17.2若图G是非平面图，则G的任何母图也都是非平面图。
推论K(n≥5)和K3,n(n≥3)都是非平面图。
n本推论由K5，K3,3不是平面图及定理17.2得证。
还有一个明显的事实也用定理给出。
定理17.3设G是平面图，则在G中加平行边或环后所得图还是平面图。
本定理说明平行边和环不影响图的平面性，因而在研究一个图是否为平面图时可不考虑平行边和环。
二、平面图的面与次数定义17.2设G是平面图(且已是平面嵌入)，由G的边将G所在的平面划分成若干个区域，每个区域都称为G的一个面。
图论中的图的着色与染色问题在图论中，图的着色与染色问题是一类经典的问题。
图的着色是指给图的每个顶点赋予一个颜色，要求相邻的顶点不能有相同的颜色；而图的染色是指给图的边赋予一个颜色，要求相邻的边不能有相同的颜色。
一、图的顶点着色图的顶点着色问题是图论中的经典问题之一。
给定一个无向图，要求为每个顶点分配一个颜色，使得任意两个相邻的顶点颜色不同。
这个问题的本质是将相邻的顶点划分到不同的颜色集合中。
解决图的顶点着色问题有多种算法，其中较为简单和常用的是贪心算法。
贪心算法按照某种规则为图的顶点逐个着色，每次着色时选择当前可用颜色的最小编号。
贪心算法的时间复杂度为O(n^2)，其中n 为图的顶点数。
二、图的边染色图的边染色问题是另一个经典的图论问题。
给定一个无向图，要求给每条边分配一个颜色，使得任意两条相邻的边颜色不同。
这个问题的目标是将相邻的边划分到不同的颜色集合中。
解决图的边染色问题的算法有多种，其中常用的是基于回溯法和深度优先搜索的算法。
回溯法通过递归地尝试为每条边分配颜色，并根据约束条件进行回溯，直到找到可行的解或者穷尽所有可能。
深度优先搜索则通过遍历图的边，逐个给边染色，当发现某条边与相邻边颜色相同时，回溯到前一条边重新选择颜色。
三、特殊图的着色与染色问题除了一般的图的着色与染色问题，还存在一些特殊类型的图，对应着特殊的着色与染色问题。
1. 树的着色与染色：在树中，任意两个顶点之间都只有一条路径，因此树的着色与染色问题可以简化为树的边染色问题。
树的边染色问题可以使用贪心算法解决，每次为某条边选择一个未使用的颜色，直到所有边都被染色。
2. 平面图的着色与染色：平面图是指可以画在平面上，且任意两条边最多只有一个公共顶点的图。
平面图的着色与染色问题是在满足平面图约束条件下对图进行着色或染色。
对于平面图的着色与染色问题，使用四色定理可以得到解，即任何平面图最多只需要四种颜色来着色或染色。
四、应用领域图的着色与染色问题在实际应用中具有广泛的应用。
