着色
色数
- k -着色 —— 用k个颜色上色的
- 色数 —— 最少需要的颜色数
- k -色图 —— 最少需要的色 的图
- χ(……) —— 相应 色数
性质
- χ(G)
点色数
=1 —— 为零图全是孤立点
- χ(Kn)=n
- χ(G)=2 —— G为非零图二部图
二部图:一个图的点集可以分为2个互不相交的点集A,B的并,并且在G中的每一条边的2个端点,其中一个在A,另一个在B。
- G可2 -着色 —— G是二部图 —— G中无奇圈
χ(G)的上界、Brooks定理
色多项式
例
边着色、Vizing定理
例
当然,这道题出现在边着色下方,所以用到 边着色 的建模,但是实际上自己想的话挺难想到的🥠🥠🥠
练习
求色多项式
有点看不懂,尽量看看吧,实在不会也无所谓了
第3题
这题不难,但是主要是当2个图组合在一起时,用乘法缔结起来
递推公式用 加法
8题
前2问
看看就行了,有点概念即可,不必强求了
证明题
看看就行文章来源:https://www.toymoban.com/news/detail-530140.html
14
文章来源地址https://www.toymoban.com/news/detail-530140.html
到了这里,关于离散数学·图的着色的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!