Sáng kiến kinh nghiệm Ứng dụng lý thuyết đồ thị trong việc dạy bồi dưỡng học sinh giỏi Tin học 11

 trại.
 Mỗi dòng trong R dòng sau gồm C kí tự. Tất cả các kí tự này biểu diễn các vị trí có hàng rào, cừu và chó sói trong trại.
Kết quả: Ghi ra file SOICUU.OUT chỉ một dòng gồm 2 con số: Số cừu và số sói còn lại trong trại. Ví dụ:
SOICUU.INP
SOICUU.INP
SOICUU.INP
6 6
. . . # . .
. # # v# .
#v . # . #
# . o # . #
. # # # . #
. . . # # #
8 8
. # # # # # # .
. . . o . . . #
# . # # # # . #
# . # v . # . #
# . # . o # o #
# o . # # . . #
# . v . . v . #
. # # # # # # . 

9 12
.###.#####..
#.oo#...#v#.
#..o#.#.#.#.
#..##o#...#.
#.#v#o###.#.
#..#v#....#.
#...v#v####.
.####.#vv.o#
.......####.
SOICUU.OUT
SOICUU.OUT
SOICUU.OUT
0 2
3 1
3 5
Cách giải : Sử dụng thuật toán tìm kiếm các miền liên thông. Trong mỗi miền liên thông đếm số cừu và số sói trong đó. Nếu số cừu lớn hơn số sói thì coi như số sói còn lại trong miền này bằng 0, nếu ngược lại thì số cừu còn lại trong miền này bằng 0. Khi tìm tới ô nào thì xoá ô đó bằng cách gán kí tự ‘#’ trên ô đó.
3. Đường đi ngắn nhất trên đồ thị.
Bài toán: Cho đồ thị vô hướng, có trọng số không âm. Hãy tìm đường đi cơ bản (không có đỉnh lặp lại) ngắn nhất từ đỉnh xuất phát x đến đỉnh đích y (y≠x).
Có nhiều thuật toán để giải bài toán đặt ra, tuy nhiên trong đề tài này tôi chỉ đề cập tới thuật toán có nhiều ứng dụng và rất hiệu quả, đó là thuật toán Dijkstra.
3.1. Tổ chức dữ liệu:
 Mảng A(N, N) thể hiện ma trận trọng số. Mảng V(N) là nhãn độ dài đường đi ngắn nhất: V[i] là độ dài đường đi ngắn nhất từ đỉnh xuất phát x tới đỉnh i. D(N) là mảng đánh dấu đỉnh đã có nhãn tối ưu. Gán cho D[i]=True khi v[i] đã là độ dài tối ưu của đường đi từ x tới i, khi đó đỉnh i được gọi là đỉnh đã cố định nhãn. D[i]=false khi v[i] chưa đạt giá trị tối ưu, khi đó đỉnh i được gọi là đỉnh tự do. Mảng TR(N) với ý nghĩa nếu TR[i]:=j thì đỉnh j là đỉnh ngay trước đỉnh i trên hành trình ngắn nhất.
3.2. Thuật toán.
B1: Khởi trị
Khởi trị nhãn đường đi ngắn nhất từ đỉnh x tới đỉnh i là V[i]:=A[x,i] (nếu không có đường đi trực tiếp từ x tới i thì A[x,i] bằng vô cùng). Lưu lại đỉnh trước khi tới i trên hành trình ngắn nhất là Tr[i]:=x
Đánh dấu mọi đỉnh i là tự do (nhãn V[i] chưa tối ưu) bằng cách gán D[i]:=false
Khởi trị nhãn đỉnh x là V[x]:=0; D[x]:=True (nhãn của đỉnh x đã tối ưu).
B2: (Vòng lặp vô hạn)
B2.1. Tìm đỉnh i0 tự do có nhãn V[i0] nhỏ nhất.
B2.2. Nếu không tìm được i0 (i0=0), hoặc i0=y thì thoát khỏi vòng lặp còn không thì:
+ Đánh dấu i0 đã được cố định nhãn: D[i0]:=true;
+ Sửa nhãn cho các đỉnh j tự do kề với i0 theo công thức V[j]=Min{V[j], V[i0]+A[i0,j]}
+ Nếu V[j]=V[i0]+A[i0,j] thì lưu vết đỉnh trước j là i0: Tr[j]:=i0
B3: Tìm và ghi kết quả
V[y] là độ dài đường đi ngắn nhất từ đỉnh x đến y. Lần ngược mảng Tr để tìm hành trình này.
Một số lưu ý: 
+ Nếu khỏi lặp vô hạn với i0=0 thì không tồn tại đường đi ngắn nhất từ x đến y.
+ Nếu B2 chỉ cho thực hiện lặp k lần thì nhãn của mỗi đỉnh i sau khi thoát khỏi vòng lặp chính là độ dài đường đi ngắn nhất từ x tới i qua k đỉnh.
+ Mỗi lần sửa nhãn có thêm một đỉnh được cố định nhãn. Do đó số bước lặp của B2 trong thuật toán trên tối đa là N.
Chương trình tìm đường đi ngắn nhất trên đồ thị theo thuật toán của Dijkstra.
Const fi=’dijkstra.inp’;
 fo=’dijkstra.out’;
	 Max=100;
	 Vc=100*50*maxint
Type m1=array[1..max, 1..max] of longint;
	 m2=array	[1..max] of longint;
	 m3=array[1..max] of byte;
Var a:m1;{ma tran trong so}
	V:m2; {nhan do dai duong di ngan nhat}
	t, d:m3; {t: ghi nhan dinh truoc cua 1 dinh, d:danh dau dinh co nhan toi uu}
	m:integer;
	n,x,y:byte;
 (*===============================*)
Procedure Doctep;
Var f:text;
 k.w:integer;
	i,j:byte;
Begin
Assign(f, fi);reset(f);
Fillchar(a,sizeof(a),0); {mang A la ma tran trong so}
Readln(f, n, m, x, y);{so dinh, so canh, dinh xuat phat, dinh dich}
For k:=1 to m do
 Begin
 Readln(f, i, j, w);{canh (i,j) co trong so la w}
 a[i,j]:=w; a[j,i]:=w;
 end;
 close(f);
end;
(*===============================*)
Procedure khoitao; {khoi tao 1 so bien va mang can thiet}
Var i,j:byte;
Begin
 For i:=1 to n do
 For j:=1 to n do
 If a[i,j]=0 then a[i,j]:=vc;
 Fillchar(d, sizeof(d), 0); {cac dinh chua co nhan toi uu goi la cac dinh con tu do}
For i :=1 to n do v[i]:=a[x, i];
v[x]:=0;
fillchar(t, sizeof(t),0) ; {mang t dung de luu dinh truoc dinh hien tai}
end ;
(*===============================*)
Function tim_vmin:byte;{tim dinh tu do co nhan do dai duong di nho nhat}
Var li, i:byte;
	P:longint;
Begin
Li:=0;
P:=vc;{khoi tri gia tri nho nhat can tim trong cac nhan v[i] voi i la dinh tu do}
For i:=1 to n do
If d[i]=0 then {i la dinh tu do}
If v[i]<p then
 Begin
 P:=v[i];
 Li:=i;
 End;
 Tim_vmin:=li;
End;
(*===============================*)
Procedure SuaNhan(j); {sua lai nhan cac dinh j tu do, ke voi dinh i}
Var i:byte;
Begin
 d[i]:=1;
 for j:=1 to n do
 if d[j]= 0 then {j la dinh tu do}
 if (a[i,j]>0) and (a[i,j]vc) then {dieu kien j la dinh ke cua i}
 if v[j]> v[i]+a[i,j] then {dieu kien co the sua nhan}
 begin
 v[j]:=v[i]+a[i,j]; {sua nhan}
 t[j]:=i; {dinh ngay truoc dinh j trong hanh trinh ngan nhat la dinh i}
 end;
end;
(*===============================*)
Procedure Dijkstra;
Var i:byte;
Begin
 Khoitao;
 Repeat
 i:=tim_vmin;{dinh tu do co dinh nho nhat}
 If i=0 then break;
 SuaNhan(i);
 Until (d[y]>0);
End;
(*===============================*)
Procedure Ghiketqua;
Var f:text;
 i,j:byte;
 kq:m3;
Begin
 assign(f, fo); rewrite(f);
 if v[y]=vc then {khong co duong di tu x den y}
 begin
 writeln(f,-1);
 close(f);
 halt;
 end;
 writeln(f, v[y]); {do dai duong di ngan nhat tu x den y la v[y]}
 i :=y ; {lan nguoc hanh trinh ngan nhat bat dau tu y ve x}
 j :=0 ;
 repeat
 inc(j) ;
 kq[j]:=i; {luu hanh trinh nguoc vao mang kq}
 i:=t[i];
 until i=0; {dieu kien da ghi nhan xong dinh ngay truoc dinh x}
 for i:=j downto 1 do writeln(f, kq[i]); {dua ra hanh trinh ngan nhat}
 close(f);
end;
BEGIN
Doctep;
Khoitao;
Dijkstra;
Ghiketqua;
END.
Một số ví dụ áp dụng.
Nhiều bài toán thực tế quan trọng có thể dẫn về bài toán tìm đường đi ngắn nhất trên đồ thị. Các bài toán dễ nhận thấy nhất là: chọn một hành trình đi tiết kiệm nhất, lập lịch thi công các công đoạn trong một công trình thi công lớn, bài toán lựa chọn đường truyền tin với chi phí nhỏ nhất trong mạng thông tin, bài toán tìm đường đi của Robot.Hiện nay có rất nhiều phương pháp để giải các bài toán như vậy. Thế nhưng, thông thường các thuật toán được xây dựng dựa trên cơ sở lý thuyết đồ thị tỏ ra là các thuật toán có hiệu quả cao nhất. Sau đây xin đưa ra vài ví dụ minh họa cho điều này 
(Dưới đây tôi đưa ra 2 ví dụ về hai bài toán khó mà giải theo thuật toán tìm đường đi ngắn nhất hiệu quả)
Ví dụ 1: Chọn xâu
Cho một số nguyên k (0=<k<=255) và N xâu kí tự có độ dài L (N nguyên, 0<N<=100, L<=255) là S1, S2,...,SN đôi một khác nhau chỉ gồm các chữ cái thường. Hãy tìm xâu H nhỏ nhất thỏa mãn tính chất sau đây : tồn tại k vị trí khác nhau trên xâu H là vị trí xuất hiện của một trong các xâu S1, S2,..., SN (p là vị trí xuất hiện của xâu S trong H nếu hàm Copy(H, p, L))=S).
Dữ liệu vào : File XAU.INP :
Dòng đầu tiên ghi N, L, K.
N dòng tiếp theo : dòng thứ i ghi xâu Si
Kết quả : Ghi ra file XAU.OUT :
Dòng đầu ghi độ dài nhỏ nhất.
Dòng thứ 2 ghi xâu H thỏa mãn bài toán
K dòng tiếp theo, mỗi dòng thể hiện một vị trí xuất hiện gồm 2 số u, p cho biết xâu Su xuất hiện tại vị trí p trên H.
VD : 
XAU.INP
XAU.OUT
2 10 2
aaaaaaaxyz
xyzabcdefg
17
aaaaaaaxyzabcdefg
1 1
2 8
Cách giải : Đây là một bài toán khó. Nếu chúng ta giải theo cách thông thường sẽ rất phức tạp, chương trình sẽ rất dài và dễ sai khi thử các bộ test khác nhau.
Cách giải theo lý thuyết đồ thị như sau :
Trước hết xây dựng đồ thị : Mỗi đỉnh là một xâu trong các xâu S1, S2,..., SN. Để tìm trọng số cung (i, j) là a[i,j] ta làm như sau : Đặt phần cuối của Si trung với phần đầu của Sj sao cho đoạn trùng nhau của chúng dài nhất. Khi đó độ dài đoạn còn lại của Sj không trùng với Si được chọn là a[i,j]. Ví dụ : Si=’bcyaabaaaab’ và Sj=’aabaaaabhk’ thì đoạn không trùng nhau ngắn nhất của Sj là ‘bhk’ do đó a[i,j]=3. Bài toán trở thành tìm đường đi ngắn nhất qua k đỉnh (độ dài đường đi này chính là độ dài xâu H). Để giải bài toán này, có thể tiến hành xây dựng nhãn F cho mỗi đỉnh, đó là độ dài đường đi ngắn nhất qua k đỉnh và kết thúc tại mỗi đỉnh đó. Ban đầu xét các đường chỉ gồm 1 đỉnh, đương nhiên nhãn mỗi đỉnh là độ dài xâu tương ứng với đỉnh đó. Giả sử các đỉnh đã có nhãn ở bước trước là độ dài đường đi ngắn nhất gồm t đỉnh (t<k), để xây dựng nhãn các đỉnh ở bước trước là độ dài đường đi ngắn nhất gồm t+1 đỉnh thì cần sửa lại nhãn các đỉnh đó ở bước trước (qua t đỉnh) bằng công thức :
"j : F[j]bước t+1 :=Min{F[i]bước t+a[i,j] | "i} 
Ví dụ 2: K đường đi ngắn nhất.
Vùng đất X có N thành phố (4≤N≤300) được đánh số từ 1 đến N. Giữa 2 thành phố có thể có đường nối trực tiếp hoặc không. Các con đường này được đánh số từ 1 đến M (1≤M<2000). Ban lãnh đạo thể dục thể thao vùng X tổ chức cuộc chạy đua tiếp sức “thông minh” theo quy luật sau:
+ Thành phố xuất phát là thành phố 1, thành phố đích là thành phố N.
+ Mỗi đội thi đấu có K người dự thi. Lần lượt từng người chạy từ thành phố 1 về thành phố N.
+ Khi người thứ 1 đến được thành phố N thì người thứ 2 mới bắt đầu rời khỏi thành phố 1,, người thứ i đến thành phố N thì người thứ i+1 mới bắt đầu rời khỏi thành phố 1,, (i<k). Người thứ K về tới đích tại thời điểm nào thì thời điểm đó được coi là thời điểm về đích của toàn đội.
+ Đường chạy của các đội viên không được giống nhau hoàn toàn.
+ Có thể chạy lại đoạn đường đã chạy.
Hãy viết chương trình tính thời gian nhỏ nhất để một đội hoàn thành cuộc chạy đua tiếp sức nêu trên nếu các vận động viên có tốc độ chạy như nhau.
Dữ liệu vào: File văn bản PATHK.INP
Dòng đầu tiên ghi 3 số K, N, M
M dòng tiếp theo, mỗi dòng chứa 3 số nguyên i, j, w thể hiện một đường đi trực tiếp giữa 2 thành phố i và j mất thời gian chạy là w (đơn vị thời gian, 1≤w≤9000).
Kết quả: Ghi ra file văn bản PATHK.OUT:
Dòng thứ 1 chứa 1 số nguyên duy nhất là thời gian chạy nhỏ nhất của một đội.
K dòng tiếp theo, mỗi dòng thể hiện hành trình chạy của một vận động viên trong đội là dãy số hiệu các thành phố liên tiếp trên hành trình đó.
Cách giải: Ta xem vùng đất X là một đồ thị vô hướng gồm N đỉnh. Đường nối giữa 2 thành phố thể hiện cạnh của đồ thị.
Lúc đó bài toán được giải theo thuật toán Dijkstra cải tiến như sau:
Gọi L[i,j] là độ dài đường đi thứ j trong k đường đi ngắn nhất từ đỉnh 1 đến đỉnh i (i=1, 2, , N; j=1, 2,, k). Khởi tạo L[i,j] bằng vô cùng với mọi i, j, L[1,1] bằng 0.
Mỗi lần tìm một cặp (ii,jj) chưa đánh dấu có nhãn L[ii,jj] nhỏ nhất.
Từ (ii,jj) sửa nhãn cho (i,j) nếu các đỉnh i kề với đỉnh ii: đường ngắn nhất thứ j tới đỉnh i sẽ thành đường ngắn nhất thứ j+1 tới i nếu L[ii,jj]+ C[ii,i] > L[i,j] (*) và đường ngắn nhất thứ j tới i sẽ thành đường đi qua ii trước, rồi tới i. Do đó khi điều kiện (*) xẩy ra thì L[i,j+s]:=L[i,j+s-1] với mọi s=1 đến k-j và L[i,j]:=L[ii,jj]+C[ii,i].
Tương tự cập nhật lại vết đường đi của các cặp (i,j).
Đánh dấu cặp (ii,jj) đã cố định nhãn.
Quá trình lặp cho đến khi không còn cặp (i,j) nào chưa cố định nhãn hoặc cặp (n,k) đã được cố định nhãn.
Lưu ý: Vì chúng ta lưu trữ đồ thị bằng ma trận kề nên bài toán chỉ chạy được với số đỉnh và số cạnh không lớn lắm.
IV. HIỆU QUẢ CỦA SÁNG KIẾN KINH NGHIỆM.
Tôi đã nghiên cứu đề tài này trong mấy năm gần đây nhưng rất tiếc mới vận dụng dạy cho học sinh lớp 11 tham gia bồi dưỡng học sinh giỏi Tin học trong học kỳ II năm học 2010-2011.
Sau khi tìm hiểu, nghiên cứu và vận dụng đề tài này vào công tác dạy học cho đội tuyển học sinh giỏi 11, tôi thấy kết quả thu được khả quan hơn nhiều so với cách làm củ. Cụ thể:
Khi chưa áp dụng đề tài: Tôi mới tham gia dạy bồi dương HSG 3 năm gần đây và kết quả như sau:
Năm 2008-2009, có 2 học sinh dự thi HSG 11, có 1 học sinh đạt giải 3, 1 học sinh không đạt giải. 
Năm 2009-2010, có 2 học sinh tham gia dự thi 11, có 1 học sinh đạt giải khuyến khích, 1 học sinh không đạt giải, 
Sau khi áp dụng đề tài: Đề tài này mới chỉ áp dụng cho học sinh khối 11 năm học 2010-2011.
Kết quả HSG 11 học kỳ II vào tháng 4 năm học 2010-2011 như sau : 1 học sinh đạt giải nhì (16 điểm) và 1 học sinh đạt giải 3 (14 điểm) – Đứng thứ 2 toàn tỉnh.
Đề tài này đã vận dụng hiệu quả đội tuyển học sinh giỏi 11 và sẽ tiếp tục được vận dụng để bồi dưỡng cho học sinh giỏi tin học 12 vào tháng 12 năm 2011. Tin rằng với sự hỗ trợ của phương pháp này đội tuyển học sinh giỏi 12 trong tháng 12 tới cũng sẽ thu được kết quả khả quan.
KẾT LUẬN
Ứng dụng lý thuyết đồ thị vào dạy học bồi dưỡng HSG Tin học tại các trường THPT có ý nghĩa rất quan trọng trong việc nâng cao chất lượng, hiệu quả dạy học, qua đó giúp học sinh nhận thức đúng đắn vai trò, vị trí của môn học. Hơn nữa việc ứng dụng lý thuyết đồ thị tạo được hứng thú học tập cho học sinh, phát huy tính tích cực, chủ động, nhằm phát triển tư duy sáng tạo và năng lực giải quyết vấn đề trong thực tiển cuộc sống. Đề tài này đã giúp bản thân tôi tìm hiểu sâu hơn kiến thức về lý thuyết đồ thị và giúp học sinh tìm hiểu thêm một luồng kiến thức mới để làm phong phú ý tưởng thuật toán của mình, tạo nền tảng cơ bản và bàn đạp để tiến xa hơn về con đường lập trình. Xã hội càng phát triển càng đặt ra nhiều yêu cầu mới, do đó các bài toán đặt ra hiện nay ngày càng thiên về khuynh hướng giải bằng lý thuyết đồ thị. 
Lý thuyết đồ thị là một lĩnh vực rộng, gồm nhiều mảng kiến thức, đề tài của tôi mới chỉ đề cấp đến một số nội dung cơ bản có thể áp dụng một cách hiệu quả cho học sinh Tin học 11 tham gia bồi dưỡng HSG đó là: vận dụng các thuật toán tìm kiếm trên đồ thị, thuật toán tìm các thành phần liên thông, thuật toán Dijkstra tìm đường đi ngắn nhất trên đồ thị để giải các bài toán thực tế đặt ra một cách hiệu quả. Còn nhiều kiến thức về đồ thị có thể áp dụng để bồi dưỡng cho học sinh, chẳng hạn như vận dụng kiến thức về cây, cây khung, cây khung ngắn nhất ; chu trình, chu trình Euler và chu trình Hamilton ; đồ thị hai phía, cặp ghép...
Tuy nhiên, nếu chỉ vận dụng lý thuyết đồ thị thì chưa đủ, để thành công trong việc bồi dưỡng học sinh giỏi cần phải biết kết hợp nhiều phương pháp khác nhau, chẳng hạn như giải bài toán theo đệ quy, đệ quy quay lui, quy hoạch động.... Các bài toán đặt ra ngày càng đa dạng thì các thuật toán xây dựng cũng phải đa dạng. Mức độ thành công của việc vận dụng lý thuyết đồ thị vào bồi dưỡng học sinh giỏi này phụ thuộc nhiều vào từng kiểu bài và từng đối tượng học sinh.
Tuy đã rất cố gắng tìm hiểu, nghiên cứu và vận dụng lý thuyết đồ thị vào dạy học đội tuyển học sinh giỏi tin học 11 để qua đó giúp học sinh bổ sung thêm sự hiểu biết của mình về tin học nói chung và lập trình nói riêng và để phục vụ cho thi học sinh giỏi đạt kết quả tốt hơn nhưng không thể tránh khỏi những thiếu sót nhất định. Kính mong Hội đồng khoa học và bạn bè đồng nghiệp góp ý, bổ sung để đề tài hoàn thiện hơn.
Xin chân thành cảm ơn !