图着色问题
图色数
有两个相关的术语:
和图中其他对象的关系
色数和团数(clique number)
团(英語:)是一个图中两两相邻的顶点构成的集合。最大团是一个图中顶点最多的团,它的定点数被称为的团数,记为。和满足如下关系:
色数和独立数(independence number)
独立集(英語:)是一个图中两两不相邻的顶点所构成的集合。最大独立集是一个图中顶点最多的独立集,它的定点数被称为的独立数,记为。和满足如下关系:
色多项式
色多项式(英語:)是将一个图G进行t-着色的方法数,记作P(G, t)。P(G, t)是关于t的多项式,假设G的阶数为n,则P(G, t)满足如下性质:
首项系数为1;
n-1次项系数等于-|E(G)|;
0次项系数等于0;
各项系数正负交替;
一次项系数不为零当且仅当G连通。
色多项式包含了G是否能进行t-着色的信息,即可以根据色多项式确定G的色数。二者具有如下关系:
下表给出了部分图的色多项式:
三角形 K3 | |
完全图 Kn | |
n个顶点的树 | |
环 Cn | |
佩特森图 |
參考來源
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.