图论-染色、二部图匹配问题

1染色、二部图匹配与指派问题2四色问题(FourColorProblem)3着色(coloring)着色:给图的某类元素(点,边,面)中每个指定1种颜色,使得相邻元素有不同颜色点着色,边着色,面着色4着色(例)边着色点着色面着色[着色]

图G=(V,E)的一个k

顶点着色指用k种颜色对G的各顶点的一种分配方案。若着色使得相邻顶点的颜色都不同，则称该着色正常，或称G存在一个正常的

k

顶点着色（或称一个

k着色）。此时称G为k-可着色的。[色数]

使G=(V,E)k-可着色的最小k

值称为G的色数，记为

(G)。若

(G)=k，称G为

k

色图。色数[例]

三色图色数7色数(chromaticnumber)k-色图:可k-着色,但不可(k-1)-着色色数:着色所需最少颜色数点色数

(G),边色数

’(G),面色数*(G)例:(G)=2,’(G)=4,*(G)=3

[特殊图的色数]①零图：

(G)=1②完全图Kn：(G)=n若一个图的每一对不同顶点恰有一条边相连则称为完全图。③G是一条回路：(G)=2若|V|是偶数

(G)=3若|V|是奇数④(G)=2的充要条件是:(a)|E|

1；(b)G中不存在边数为奇数的回路。（此时G为二部图）⑤

若G1、G2为G的两个连通分支，则

(G)=max{(G1),(G2)}色数[Hajós猜想]

若G是k

色图,则G包含Kk

的一个同胚图。(1961)[四色定理]

任何平面图都是4-可着色的。如果在平面上划出一些邻接的有限区域，那么可以用四种颜色来给这些区域染色，使得每两个邻接区域染的颜色都不一样；另一个通俗的说法是：每个地图都可以用不多于四种颜色来染色，而且没有两个邻接的区域颜色相同。被称为邻接的两个区域是指它们有一段公共的边界，而不仅仅是一个公共的交点。色数[例]

如图，求(G)。色数 (G)=min{(K5),(K4),(K3)}=(K3)=3色数K5K4K4K3图的着色包括对边、顶点和平面区域的着色。本章主要讨论简单图的顶点着色。[例]

6种化学制品，某些不能放在同一仓库。用矩阵表示,例如(a,b)=1表示a和b不能放在同一仓库。问：最少需要几个仓库？图的着色[解]以该矩阵为邻接矩阵构造图如上所示。给图的顶点染色使得相邻点具有不同颜色，最少需要3种颜色。图的着色acbdefDefinition对于简单无向图G=(V,E),V划分为V1和V2,任意边关联的两个节点中一个在V1中,一个在V2中,则称G为二部图.完全二部图：V1中的每个顶点均与V2中的所有顶点相邻。二部图V1和V2称为互补节点集合,一般不唯一:

匹配Def设G=(V,E)是任意简单无向图.若

M

E且中任何两条边都不相邻,则称M为G的一个匹配(matching)或边独立集,M中每条边的两个节点在M中匹配.{ab,fh,id}{ab,fi,cd,hj}{af,bg,ch,di,ej}(a)边数最多的匹配称为最大匹配(maximummatching),其中的边数称为匹配数.(b)所有节点都与M中的某边关联的匹配称为完美匹配(perfectmatching).(c)在二部图G=(V,E)中,V1和V2为互补节点集.若M为G的一个最大匹配且|M|=min{|V1|,|V2|},则称M为G的一个完备匹配(completematching).当|V1|≤

|V2|,M也称为G的一个从V1到V2的完备匹配.19匹配与指派问题-完备匹配某公司准备安排n个职员x1,x2,…,xn从事n项工作y1,…,yn,每个职员能胜任其中一项或几项工作试问:能否把所有职员都安排一项他所胜任的工作?这个问题称为人员安排问题

20匹配与指派问题-完备匹配21匹配与指派问题-最大权完