图的着色
图的边着色
相关概念
-
正常边着色
- 对G的边进行染色，相邻边染不同颜色（G不能有自环）
- 用k种颜色对图G进行正常边着色，则称G是k边可着色的
- 其实是边集合的一种划分
-
边色数
- 对G进行正常边着色的最少颜色数，记为χ‘(G)
-
色组
- 相同颜色的边集
-
π
- 一种边着色方案
-
u缺i色
- 设点u关联的边的着色没有用到色i，则称u缺i色
特殊图的边色数
-
完全二部图
-
定理1：χ’(K,m,n)=△
- 证明：很显然，因为完全二部图嘛，所以最大度的点必须要有n个颜色(n>m)
-
-
二部图
-
定理2：G是二部图，则χ'(G)=△
- 证明：数学归纳法
- 其实也是必须要有这个方法
-
-
简单图
-
引理：简单图，x，y不相邻，π是G的一个正常k边着色，对π，x，y以及x相邻点均至少缺少一种颜色，则G+xy是k边可着色
-
- 就不证明了
-
定理3：若G是简单图，则其边色数χ'(G)=△或△+1
- 证明：最大度的话显然，因为最大度的点显然要最大度种颜色才能正常染色，只要证明≤最大度+1就行，用数学归纳法，然后减边时用引理来证明
- 最大度是第一类图，最大度+1是第二类图
-
-
最大度点只有一个，或两个相邻
-
定理4：G是简单图且最大度大于0，若G中只有一个最大度点或恰有两个相邻的最大度点，则χ'(G)=△
- 减去最大度点和其邻接点的一条边，然后用引理来证明
-
-
顶点数和边数有关系
- 定理5：设图G是简单图，若顶点数n=2k+1且边数m>k△，则χ'(G)=△+1
-
奇数阶正则简单图
-
χ‘(G)=△+1
- 由定理5可证
-
注意，奇数阶哦
-
-
无环有重边图
- 无环图G中边的最大重数为μ，则χ‘(G)≤△+μ
图的顶点着色
基本概念
-
正常点着色
- 每个顶点着色，且相邻顶点着不同颜色
-
点色数χ(G)
- 和边色数的区别在于少一点
-
色组
- 也叫点独立集
-
顶点着色时有重边无影响
点色数的结论
-
定理1：对任意的图G，有χ(G)≤△+1
- 最大度+1,1是自己
G的△(G)+1正常点着色算法
- 从第一个点开始，每次都给i点标号为i的邻接顶点里未使用的最小色号，如此一直下去
定理2：若G是连通的简单图，并且它既不是奇圈，又不是完全图，则χ(G)≤△
五色定理
- 定理4：每个平面图都是5可着色的
-
根据平面图和其对偶图的关系，上面定理等价与每个平面图是5可顶点正常着色的
-
有一个事实，连通的平面图最小度≤5
- 可以反证，很容易推出其边数是≥3n的，超出了平面图边数的上界
-
临界图与完美图
临界图
-
对于图G的任意真子图H，都有χ(H)≤χ(G)
- 点色数为k的临界图称为k临界图
-
定理1：临界图的性质
- k色图均有k临界子图
- 每个临界图均为简单连通图
- 若G是k临界图，则δ≥k-1
-
推论：每个k色图至少有k个度不小于k-1的顶点
- 废话
-
临界图没有割点
-
不含三角形的k色图
- 这有什么用···
- 对任意正整数k，存在不含三角形的k色图
完美图
-
团
- 顶点子集S导出的子图是完全图，则S是G的一个团
- 简单图G的最大团包含的顶点数为G的团数，记为cl(G)
- 显然，χ(G)≥cl(G)
-
完美图
- 设G是一个图，若对G的每个点导出子图H，均有χ(H)=cl(H)，则称G为完美图
-
独立集
- G中互不邻接的顶点作成的子集称为G的一个点独立集
- G中含顶点数最多的点独立集称为G的最大独立集，其包含的顶点数称为独立数，α(G)
-
独立数的完美图
- 这里不想看了，估计不考
色多项式
概念
-
色多项式
- 给定图G和颜色数k，Pk(G)的值是所有正常顶点着色的方式数，Pk(G)是k的多项式
-
k<χ(G)时，Pk(G)=0
- χ(G)=min{k|Pk(G)≥1}
-
图G为空图，则Pk(G)=k^n
- Pk(Kn)=k(k-1)...(k-N+1)
色多项式的求法
-
递推计数法
-
定理1：G为简单图，则对任意e∈E(G)有：Pk(G)=Pk(G-e)-Pk(G·e)
- 和生成树那个很像
- 移项，然后变成加法的话更好理解
-
推论：设G是简单图，e=uv是G的一条边，且d(u)=1，则Pk(G)=(k-1)Pk(G-u)
- 很简单，因为u有k-1中颜色涂法
- 悬挂的公式
-
使用分析
- 当图G的边数较少时，使用减边递推法
-
当图G的边数较多时，使用加边递推法
- 有可能变成完全图
-
-
理想子图计数法
-
基本概念
-
设H是图G的生成子图，若H的每个连通分支均为完全图，则称H是G的一个理想子图，用Nr(G)表示G的具有r个分支的理想子图的个数
- 这个只能观察枚举
-
设qr(G)表示将简单图G的顶点集合V划分为r个不同色组的划分个数，则qr(G)=Nr(G的补图)
- 一句话解释，很多色组，总的色组的划分个数和图G补图的具有r个分支的理想子图个数相等
- 一个色组中的点但是一个独立集，其子图全是孤立点，所以其补图是完全图，也就是理想子图
-
-
理想子图计数法
-
具体的算法
- 先求出补图，然后求出补图的ri，之后再写出伴随多项式，然后带入，最终得到结果
- 进行改进，在求ri时，分开求，直接求分支的ri，然后得出分支的伴随多项式，之后再相乘，最终就能得到最终的结果
-
-
记得结果合并同类项
-
色多项式的性质
- 非同构但是可以有相同的色多项式