ài toán tô màu r t quen thu c v i t t c các b n. Mà bài toán đi n hình chính là bàiấ ộ ớ ấ ả ạ ể
toán 4 màu đ c phát bi u nh sau : M i b n đ trên m t ph ng đ u có th tô b ng 4ượ ể ư ọ ả ồ ặ ẳ ề ể ằ
màu sao cho không có hai n c láng gi ng nào l i b tô cùng 1 màu. V y chúng ta sướ ề ạ ị ậ ẽ
m r ng bài toán trên thành m t bài toán t ng quát mà h u h t chúng ta đ u đã quenở ộ ộ ổ ầ ế ề
thu c :ộ
Cho m t đ th vô h ng N đ nh ( N <= 200 ), m i đ nh đ c n i v i 1 s đ nh khácộ ồ ị ướ ỉ ỗ ỉ ượ ố ớ ố ỉ
b ng 1 cung n i tr c ti p duy nh t ( không có 2 đ nh nào có nhi u h n 1 đ ng n iằ ố ự ế ấ ỉ ề ơ ườ ố
tr c ti p ). Bài toán đ t ra là : Hãy tô màu các đ nh sao cho không có hai đ nh nào có 2ự ế ặ ỉ ỉ
màu gi ng nhau mà l i n i tr c ti p v i nhau v i s màu c n tô là ít nh t.ố ạ ố ự ế ớ ớ ố ầ ấ
Bài toán trên có r t nhi u cách gi i. Trong đó cách đ n gi n nh t đ gi i bài toánấ ề ả ơ ả ấ ể ả
trên là Duy t có ch n nhánh. Thu t toán trên khá hi u qu . Có th phát bi u qua cáchệ ặ ậ ệ ả ể ể
trên nh sau :ư
Procedure try(k : integer) ;
Var ok : boolean;
Begin
If ( k > N) then
Begin
Cap_nhat_min;
Exit;
End;
Ok := false;
For i := 1 to somau do
If To_duoc_mau(i,k) then
Begin
Ok := true;
Dat_trang_thai(i,k); { Ghi nhan i co mau k, va danh so cac
dinh ke voi i phai co mau khac i }
Try(k+1);
Tra_trang_thai(i,k);
end;
if (ok = false) {
inc(somau);
Dat_trang_thai(somau,k);
Try(k+1);
Tra_trang_thai(somau,k);
Dec(somau);
}
End;
Tuy nhiên v i d li u l n m t chút thì thu t toán Duy t s không t i u v m tớ ữ ệ ớ ộ ậ ệ ẽ ố ư ề ặ
th i gian. Do đó chúng ta s áp d ng thu t toán tham lam đ gi i bài toán trên.ờ ẽ ụ ậ ể ả
Thu t toán 1 : T t ng ch t nh phân r i tham lam: ậ ư ưở ặ ị ồ
Dau = 0;
Cuoi = N; { s màu t i đa có th tô }ố ố ể
While (cuoi > dau) do
Begin
Lim := (dau + cuoi ) div 2;
If (To_duoc) then cuoi = lim else dau = lim;
End;
Lim = cuoi; Chính là đáp án c n tìm.ầ
Trongth t c To_duoc b n áp d ng thu t toán tham lam . Có nhi u cách cho b n l aủ ụ ạ ụ ậ ề ạ ự
ch n. Sau đây là m t cách : T i m i b c b n tìm t p có nhi u đ nh nh t th a mãn vàọ ộ ạ ỗ ướ ạ ậ ề ỉ ấ ỏ
tô màu cho chúng. Mu n tìm nh v y m i l n b n tìm đ nh k v i ít đ nh nh t màố ư ậ ỗ ầ ạ ỉ ề ớ ỉ ấ
không k v i đ nh đã có trong t p đang xét ta c p nh t đ nh đó vào t p đ nh có th tôề ớ ỉ ậ ậ ậ ỉ ậ ỉ ể
màu. C làm nh v y, n u s t p tìm đ c > Lim thì s không To_duoc còn ng c l iứ ư ậ ế ố ậ ượ ẽ ượ ạ
s t p <= Lim thì có th To_duoc. Duy t ch n nhánh thì có th ra k t qu t i uố ậ ể ệ ặ ể ế ả ố ư
nh ng không đáp ng nhu c u v th i gian trong tr ng h p N l n. Còn làm theoư ư ầ ề ờ ườ ợ ớ
thu t toán tham lam th nh t thì k t qu s không t i u trong nhi u tr ng h p.ậ ứ ấ ế ả ẽ ố ư ề ườ ợ
Đ kh c ph c c 2 khuy t đi m c a 2 thu t toán trên, tôi xin đ a ra m t thu tể ắ ụ ả ế ể ủ ậ ư ộ ậ
toán d a trên t t ng tham lam, nh ng v i t t ng khá m i m , và thu t toán trênự ư ưở ư ớ ư ưở ớ ẻ ậ
t ng đ i chu n xác .ươ ố ẩ
D i đây là t t ng thu t toán: ướ ư ưở ậ
-Tr c h t ta đ nh nghĩa b c c a m t đ nh làs đ nh trên đ th ch a đ c tôướ ế ị ậ ủ ộ ỉ ố ỉ ồ ị ư ượ
m u mà đ nh này đ c n i tr c ti p v i đ nh đang xét b ng m t c nh n i tr cầ ỉ ượ ố ự ế ớ ỉ ằ ộ ạ ố ự
ti p. N u đ nh đó không đ c n i v i b t kỳ đ nh nào thì b c c a đ nh đó là 0ế ế ỉ ượ ố ớ ấ ỉ ậ ủ ỉ
-B c 1 : Tìm đ nh có b c cao nh t trên đ th ( g i là đ nh u )ướ ỉ ậ ấ ồ ị ọ ỉ
-B c 2 : Tăng s màu c n tô lên 1 và tô màu cho đ nh v a tìmướ ố ầ ỉ ừ
-B c 3 : Tìm đ nh v đ tô màu gi ng u th a mãn các đi u ki n sau : v đi đ nướ ỉ ể ố ỏ ề ệ ế
đ nh u thông qua duy nh t 1 đ nh w khác và v có s b c l n nh t. N u khôngỉ ấ ỉ ố ậ ớ ấ ế
tìm đ c đ nh nh v y ta s tìm đ nh v có s b c l n nh t mà không k v i u.ượ ỉ ư ậ ẽ ỉ ố ậ ớ ấ ề ớ
N u tìm đ c v th a mãn thì ta tô màu cho v chính là màu c a đ nh u. Sau đóế ượ ỏ ủ ỉ
nh p đ nh u và v vào làm 1 đ nh. T c : đ nh w k v i v thì cũng coi nh k v iậ ỉ ỉ ứ ỉ ể ớ ư ề ớ
u ( a[v,w] =1 a[u,w] =1 and a[w,u] = 1 )
-B c 4 : L p l i b c 3 cho đ n khi v = 0.ướ ậ ạ ướ ế
-B c 5 : L p l i b c 1 cho đ n khi tô h t m u các đ nh c a đ th .ướ ặ ạ ướ ế ế ầ ỉ ủ ồ ị
Sau đây là đo n ch ng trình mô t thu t toán trên :ạ ươ ả ậ
{$Q+,R+,B-,N+}
var
somau: integer; { L u tr s màu c n tô }ư ữ ố ầ
N : integer; { S đ nh c a đ th }ố ỉ ủ ồ ị
color : array[1..100] of integer; { M ng l u m u c a đ nh đ th , color [i] = 0ả ư ầ ủ ỉ ồ ị
nghĩa là đ nh i ch a đ c tô màu }ỉ ư ượ
a : array[1..100,1..100]of integer; { a[u,v] = 1 t c hai đ nh u và c có c nh n i,ứ ỉ ạ ố
a[u,v] = 0 t c hai đ nh không có c nh n i}ứ ỉ ạ ố
count : integer; { Đ m s đ nh đã tô màu ,Count = N ế ố ỉ ng ng ch ng trình }ừ ươ
function dinh_bac_max : integer; { Hàm tìm ra đ nh có b c l n nh t }ỉ ậ ớ ấ
var max,dem,i,j,u : integer;
begin
max := -1;{Vi co the co dinh co bac la 0}
for i :=1to N do
if color[i] = 0 then { Xét các đ nh ch a đ c tô màu đ tìm ra đ nh b c l nỉ ư ượ ể ỉ ậ ớ
nh t }ấ
begin
dem := 0;
for j :=1 to n do
if (color[j] = 0) and (a[i][j] = 1) then
inc(dem);
if (dem > max) then { C p nh t giá tr l n nh t }ậ ậ ị ớ ấ
begin
max := dem;
u := i;
end;
end;
dinh_bac_max := u;
end;
procedure tomau(u : integer);
begin
count := count + 1;
color[u] := somau;
end;
procedure tim_dinh_cung_mau(u : integer; var v : integer);
var i,j,k,max,dem : integer;