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;

begin

max := 0; { Max ở đây phải gán là 0 , do nếu tồn tại v thì bậc lớn nhất của v phải > 0 }

for i := 1 to n do

if (color[i] = 0) and (a[u][i] = 0) then { Xét các đỉnh mà u không kề mà đi đến u qua duy nhất 1 đỉnh khác }

begin

dem := 0;

for j := 1 to n do

if (color[j] = 0) and (a[i][j] = 1 ) and (a[u][j] = 1) theninc(dem);

if (dem > max) then { Cập nhật giá trị max }

begin

max := dem;

v := i;

end;

end;

if (v > 0) then exit; { Nếu tồn tại v chưa tô màu đi đến được u thông qua duy nhất 1 đỉnh khác }

max := -1; { Ở đây max phải = 0 vì có thể tồn tại v mà bậc chỉ là 0 }

for i :=1 to n do

if (color[i] = 0) and (a[u][i] =0) then { Xét các đỉnh i không kề với u và chư được tô màu với số đỉnh 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;

v := i;

end;

end;

end;

procedure Nhapdinh(u,v : integer); { Nhập 2 đỉnh u và v coi như một đỉnh }

var i : integer;

begin

for i := 1 to n do

if a[v,i] = 1 then { Đỉnh i kề với đỉnh v thì coi như nó kề với đỉnh u }

begin

a[u,i] = 1;

a[i,u] = 1;

end;

end;

procedure To_Mau; { Thủ tục tô màu để tìm ra số màu ít nhất }

var u, v : integer;

begin

somau := 0;

repeat

somau := somau+1;

u := dinh_bac_max; { u là đỉnh có bậc lớn nhất }

tomau(u); { gán màu cho đỉnh u }

repeat

tim_dinh_cung_mau(u,v); { Tìm đỉnh v có thể tô màu giống mầu của u }

if (v > 0) then

begin

tomau(v); { Gán mầu cho đỉnh v }

nhap_dinh(u,v); { Nhập 2 đỉnh u,v coi như một đỉnh }

end;

until (v = 0);

until (count = n);

end;

Thuật toán trên chạy với tốc độ khá nhanh và rất hiệu quả. Độ chính xác của thuật toán trên là rất cao nếu không nói là thuật toán chuẩn. Trong trường hợp tồi tệ nhất cài đặt theo ma trận kề, độ phức tạp của thuật toán trên là O(n³).

Để cải tiến tốc độ cho thuật toán trên ta có thể sử dụng danh sách kề hoặc danh sách liên kết. Khi đó độ phức tạp thuật toán chỉ cỡ khoảng O(n²log(n)). Muốn cải tiến hơn nữa thì tại mỗi bước ta cập nhật số đỉnh kề của một đỉnh để tăng tốc độ của hàm tìm đỉnh max ( u )và đỉnh tô màu cùng với u ( v ) . Khi đó độ phức tạp thuật toán chỉ khoảng O(N²) .Tuy nhiên cài đặt khá rắc rối. Theo tôi cách tốt nhất là bạn cài đặt theo danh sách kề ( hoặc danh sách liên kết ) độ phức tạp là O(n²log(n));

Sau đây là một vài bài toán ứng dụng của thuật toán nêu trên:

Bai 1 :XẾP LỊCH THI

Một số trường đại học tổ chức học theo tín chỉ. Nếu sinh viên tích lũy đủ số chứng chỉ cho một số môn quy định của một ngành là có quyền nhận bằng tốt nghiệp của ngành đó. Đối với các đại học như thế, việc học và thi không tổ chứa theo lớp mà theo các môn học. Hàng năm nhà trường thông báo các môn sẽ học để sinh viên tự đăng ký học các môn học theo ngành mình chọn. Cuối năm nhà trường tổ chức thi cho các môn đã giảng trong năm. Mỗi môn thi trong một ngày nhưng trong một ngày có thể tổ chức thi nhiều môn. Do một sinh viên có thể đăng ký thi nhiều môn nên lịch thi cần phải bố trí để nếu có một sinh viên đăng ký thi hai môn nào đó thì các môn đó không được thi cùng ngày.

Yêu cầu : Hãy xếp lịch thi sao cho tổng số ngày thi càng ít càng tốt.

Input : LICHTHI.INP

+ M , N : lần lượt là số thí sinh và số môn học ( M <= 1000, N <= 100);

+ M dòng tiếp theo ghi thông tin về đăng ký thi của mỗi sinh viên, mỗi dòng gồm N số 0 hoặc số 1 cách nhau một dấu cách, số thứ j trong dòng thứ i là 1 nếu sinh viên thứ i đăng ký học và thi môn thứ j và bằng 0 nếu sinh viên thứ i không đăng ký thi môn thứ j.

Output : LICHTHI.OUT

+ Gồm N dòng mỗi dòng có một số tự nhiên. Số ở dòng thứ i là ngày thi tương ứng đối với môn thứ i.

Ví dụ :

Gợi ý : Tư tưởng thuật toán của bài toán trên là đưa về bài toán tô màu đồ thị.

Ta xây dựng đồ thị như sau :

+ Mỗi đỉnh của đồ thị là một môn học ( <= 100 )

+ Hai đỉnh của đồ thị được gọi là có cạnh nối nếu có một sinh viên tham gia học 2 môn đó.

Như vậy ta xây dựng được một đồ thị vô hướng N đỉnh, trong đó a[i,j] = 1 nếu có cạnh nối, a[i,j] = 0 nếu không có cạnh nối.

Sau khi xây dựng được đồ thị trên ta áp dụng thuật toán trên . Ta sẽ tìm ra được kết quả ( số ngày ít nhất cần tổ chức thi ).

School@net