由于最终得到的阶数最小的完全图为K3,故(G)=3。对该K3的3个顶点分别染色1,2, 3。然后反向操作,每次相当于将先前粘合起来的点分开,分出来的两点与原来的点染相同 的颜色。这样得到G的一个顶点3正常染色如下。 规范染色法(极大独立集法) 设q={,F2,…,V}是图G的点k染色。若V是G的极大独立集,V2是G\1的极 大独立集,V是GU2)的极大独立集,……,一般地,V是GU的极大独立集 (i=2,3,…k),则称q是图G的规范k染色( canonical k-colouring) 定理6.43图G是顶点可k正常染色的当且仅当G存在规范k染色。 证明:充分性是显然的。 必要性:设{1,H2…V}是图G的一个顶点正常k染色,则V,2…,V都是G的独立集。 若V不是G的极大独立集,则可从\V中调一些顶点进入H,使V扩大成G的极大独立 集V,V2,V3,…,V变成V2,Ⅳ3,…,V()。然后考虑V2)。若它不是G\V的极大独 立集,则可从V\(WU2)中调一些顶点进入V2,将其扩充成G\F的极大独立集 r2,V2,3,…,VA变成2),32,…,2。如此类推,最后可得图G的规范k染色 V,2…,F3。证毕。 规范染色法基本思想:求G的极大点独立集V1,将其顶点都染上色1;再求G\H1的极大点 独立集V2,将其顶点都染上色2;如此类推,直至染完所有顶点。 规范染色法步骤: 输入:图G及其邻接矩阵,输出:G的顶点正常色划分(独立集划分):V1H2,…,Vk 第0步.S=V,i:=1 第1步.任取x∈S,V:={x},7:=(S-{x})∩N(x),转下步。 第2步.若T=φ,输出V,并令S=S一V,转第4步;否则,转第3步。 第3步.任取y∈T,V=V∩{y},T=(7-{y})∩N(y),转第2步。 第4步.若S=φ,停止;否则,令i:=i+1,转第1步。11 由于最终得到的阶数最小的完全图为 K3 ，故 χ(G) = 3。对该 K3 的 3 个顶点分别染色 1，2， 3。然后反向操作，每次相当于将先前粘合起来的点分开，分出来的两点与原来的点染相同 的颜色。这样得到 G 的一个顶点 3 正常染色如下。 z 规范染色法（极大独立集法） 设 { , , , } ϕ = V1 V2 " Vk 是图 G 的点 k 染色。若V1是 G 的极大独立集，V2 是 1 G \V 的极 大独立集，V3 是 \ ( ) G V1 ∪V2 的极大独立集，……，一般地，Vi 是 ∪ 1 1 \ − = i j G Vj 的极大独立集 （i = 2,3,"k ），则称ϕ 是图 G 的规范 k 染色（canonical k-colouring）. 定理 6.4.3 图 G 是顶点可 k 正常染色的当且仅当 G 存在规范 k 染色。 证明：充分性是显然的。 必要性：设{ , , , } V1 V2 " Vk 是图 G 的一个顶点正常 k 染色，则V V Vk , , , 1 2 " 都是 G 的独立集。 若V1不是 G 的极大独立集，则可从 1 V \V 中调一些顶点进入V1，使V1扩大成 G 的极大独立 集 (1) V1 ，V V Vk , , , 2 3 " 变成 (1) (1) 3 (1) 2 , , , V V " Vk 。然后考虑 (1) V2 。若它不是 (1) 1 G \V 的极大独 立集，则可从 \ ( ) (1) 2 (1) V V1 ∪V 中调一些顶点进入 (1) V2 ，将其扩充成 (1) 1 G \V 的极大独立集 (2) V2 ， (1) (1) 3 (1) 2 , , , V V " Vk 变成 (2) (2) 3 (2) 2 , , , V V " Vk 。如此类推，最后可得图 G 的规范 k 染色 (2) ( ) 2 (1) 1 , , , k V V " Vk 。 证毕。 规范染色法基本思想：求 G 的极大点独立集V1，将其顶点都染上色 1；再求 1 G \V 的极大点 独立集V2 ，将其顶点都染上色 2；如此类推，直至染完所有顶点。 规范染色法步骤： 输入：图 G 及其邻接矩阵，输出：G 的顶点正常色划分（独立集划分）： 1 2 ,,, VV V " k 。 第 0 步. S V= ，i : 1 = . 第 1 步. 任取 x ∈ S ， { }, ( { }) ( ) V x T S x Nx i ： ： = =− ∩ ，转下步。 第 2 步. 若T = φ ，输出Vi ，并令 i S SV = − ，转第 4 步；否则，转第 3 步。 第 3 步. 任取 y ∈T ， { }, ( { }) ( ) V V y T T y Ny i i = =− ∩ ∩ ，转第 2 步。 第 4 步. 若 S = φ ，停止；否则，令i i : 1 = + ，转第 1 步。 1 2 3 3 1