染色数 |
您所在的位置：网站首页 › 图染色问题的意义 › 染色数 |
染色数
在图论中，图染色问题是重要的研究课题之一，平面图染色有著名的四色定理，染色数（chromatic number）是对一个图的顶点进行染色，相邻的边不同色的前提下的最少所需颜色的数目。 这个页面主要介绍点染色问题，关于边染色问题参见边染色数、关于面染色问题或地图染色问题参见面染色数。 目录 1 定义 2 Brooks 定理 3 四色定理 4 其它性质 定义[]假设有顶点集不为空集的简单图 G {\displaystyle G} ，如果存在正整数 k {\displaystyle k} 以及一个映射 f : V ( G ) → { 1 , 2 , ⋯ , k } {\displaystyle f: V(G) \to \{ 1, 2, \cdots, k \}} ，满足 ∀ u v ∈ E ( G ) , f ( u ) ≠ f ( v ) {\displaystyle \forall uv \in E(G), \quad f(u) \ne f(v)} 我们就称 G {\displaystyle G} 是 k {\displaystyle k} 可染色的（ k {\displaystyle k} -colorable），如果 G {\displaystyle G} 是 k {\displaystyle k} 可染色的但不是 k − 1 {\displaystyle k - 1} 可染色的，我们就称 G {\displaystyle G} 的染色数是 k {\displaystyle k} ，记作 χ ( G ) = k . {\displaystyle \chi(G) = k.} 此时也称 G {\displaystyle G} 是 k {\displaystyle k} 染色的（ k {\displaystyle k} -chromatic）。上面我们假设 G {\displaystyle G} 是简单图是为了方便，如果有自环那么染色数是零，定义没有意义，有重边那么染色数和把所有重边视作对应的一条边时的图一致。 展开例子折叠例子以下是一些简单图类的染色数： χ ( G ) = 1 {\displaystyle \chi(G) = 1} 当且仅当 G {\displaystyle G} 是顶点集不为空的空图。 χ ( G ) = 2 {\displaystyle \chi(G) = 2} 当且仅当 G {\displaystyle G} 是二部图，例如，偶长圈以及树。 χ ( G ) = 3 {\displaystyle \chi(G) = 3} 的图没没有一个具体的等价刻画，一些例子有，奇长圈和奇数个顶点的轮图，Peterson 图等等。 偶数个顶点的轮图染色数是4. 完全图的染色数 χ ( K n ) = n − 1 , n > 0. {\displaystyle \chi(K_n) = n-1, n > 0.}Brooks 定理[] 关于点染色问题有著名的 Brooks 定理： 如果 G {\displaystyle G} 是连通的简单图，且不是完全图， G {\displaystyle G} 的最大度大于2，那么 G {\displaystyle G} 的点染色数小于等于最大度。 这个定理多适用于度比较平均的情形（尤其是正则图），这是可以给出一个很好的界，但是对于极不平均的情形（如星，点染色数是2），但是这个界可以任意大。 四色定理[]每一个简单可平面图都是四可染色的，这个四不能再改进。 这个定理最初先被证明六色和五色的情形，在很长时间内它一直是四色猜想，直到1976年首次被 Appel 和 Haken 证明，但是其证明不是纯手工的，部分图类借助计算机验证完成，这个定理目前（截至2022年）没有一个纯手工的证明。 其它性质[] 假设 G {\displaystyle G} 是 n {\displaystyle n} 个顶点的正则度为 d {\displaystyle d} 的简单图，那么 χ ( G ) ⩾ n n − d . {\displaystyle \chi(G) \geqslant \dfrac{n}{n-d}.} 不包含三角形面的简单可平面图是三点可染色的。 图论（学科代码：1107470，GB/T 13745—2009） 基本概念 无向图 ▪ 有向图 ▪ 二部图 ▪ 正则图 ▪ 度序列 ▪ 握手引理 ▪ 图的运算 ▪ 线图 ▪ 邻接矩阵和关联矩阵 ▪ 图的自同构群 ▪ 无限图 具体的图 完全图 ▪ 完全二部图 ▪ 完全多部图 ▪ Peterson 图 ▪ Kneser 图 ▪ 奇图 ▪ 理想图 ▪ 超立方图 ▪ 富勒烯图 ▪ 轮 ▪ Grotzsch 图 ▪ 通道 ▪ 圈 ▪ 路 ▪ 迹 树和连通性 连通图 ▪ 边连通度 ▪ 点连通度 ▪ 边空间 ▪ 树 ▪ 林 ▪ 生成树 ▪ Cayley 定理 ▪ Euler 图 ▪ Hamilton 图 ▪ Ore 定理 可平面图 可平面图 ▪ 图同胚 ▪ Kuratowski 定理 ▪ 外可平面图 ▪ 交叉数 ▪ 厚度 ▪ Euler 多面体公式 ▪ 对偶图 ▪ 曲面图 染色问题 点染色数 ▪ 染色多项式 ▪ Brooks 定理 ▪ 面染色数 ▪ 边染色数 ▪ Vizing 定理 ▪ Konig 边染色数定理 ▪ 四色定理 匹配问题 匹配 ▪ Hall 定理 ▪ Menger 定理 ▪ 网络流 ▪ 最大流-最小割定理 所在位置：数学（110）→ 运筹学（11074）→ 图论（1107470） |
，如果存在正整数
k
{\displaystyle k}
以及一个映射
f
:
V
(
G
)
→
{
1
,
2
,
⋯
,
k
}
{\displaystyle f: V(G) \to \{ 1, 2, \cdots, k \}}
，满足
我们就称
G
{\displaystyle G}
可染色的，我们就称
G
{\displaystyle G}
此时也称
G
{\displaystyle G}
当且仅当
G
{\displaystyle G}
当且仅当
G
{\displaystyle G}
的图没没有一个具体的等价刻画，一些例子有，奇长圈和奇数个顶点的轮图，Peterson 图等等。
偶数个顶点的轮图染色数是4.
完全图的染色数
χ
(
K
n
)
=
n
−
1
,
n
>
0.
{\displaystyle \chi(K_n) = n-1, n > 0.}
个顶点的正则度为
d
{\displaystyle d}
的简单图，那么
χ
(
G
)
⩾
n
n
−
d
.
{\displaystyle \chi(G) \geqslant \dfrac{n}{n-d}.}
不包含三角形面的简单可平面图是三点可染色的。
图论（学科代码：1107470，GB/T 13745—2009）
基本概念
无向图 ▪ 有向图 ▪ 二部图 ▪ 正则图 ▪ 度序列 ▪ 握手引理 ▪ 图的运算 ▪ 线图 ▪ 邻接矩阵和关联矩阵 ▪ 图的自同构群 ▪ 无限图
具体的图
完全图 ▪ 完全二部图 ▪ 完全多部图 ▪ Peterson 图 ▪ Kneser 图 ▪ 奇图 ▪ 理想图 ▪ 超立方图 ▪ 富勒烯图 ▪ 轮 ▪ Grotzsch 图 ▪ 通道 ▪ 圈 ▪ 路 ▪ 迹
树和连通性
连通图 ▪ 边连通度 ▪ 点连通度 ▪ 边空间 ▪ 树 ▪ 林 ▪ 生成树 ▪ Cayley 定理 ▪ Euler 图 ▪ Hamilton 图 ▪ Ore 定理
可平面图
可平面图 ▪ 图同胚 ▪ Kuratowski 定理 ▪ 外可平面图 ▪ 交叉数 ▪ 厚度 ▪ Euler 多面体公式 ▪ 对偶图 ▪ 曲面图
染色问题
点染色数 ▪ 染色多项式 ▪ Brooks 定理 ▪ 面染色数 ▪ 边染色数 ▪ Vizing 定理 ▪ Konig 边染色数定理 ▪ 四色定理
匹配问题
匹配 ▪ Hall 定理 ▪ Menger 定理 ▪ 网络流 ▪ 最大流-最小割定理
所在位置：数学（110）→ 运筹学（11074）→ 图论（1107470）
【本文地址】
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |