图论图的着色PPT教案.pptx

图论图的着色

2

第七章 图的着色

一、图的边着色

二、图的顶点着色

主要内容

三、与色数有关的几类图和完美图

四、色多项式

3

( 二 ) 、几类特殊图的边色数

( 三 ) 、边着色的应用

4

现实生活中很多问题，可以模型为所谓的边着色问题来处理。例如排课表问题。

1

2

m

｝, Y= ｛ y

1

2

n

｝,x

j

间连p

如果每个匹配中的边用同一种颜色染色，不同匹配中的边用不同颜色染色，则问题转化为在 G 中给每条边染色，相邻边染不同色，至少需要的颜色数。

5

这就需要我们研究所谓的边着色问题。