Những thuật toán hiệu quả trên đồ thị có hướng phi chu trình
Ngô Quốc Hoàn
Đồ thị là một lĩnh vực quan trọng trongtoán học rời rạc và có nhiều ứng dụng trong việc
giải các bài toántin học cũng như trong cuộc sống. Đồ thị có hướng phi chu trình làmột
trường hợp đặc biệt của đồ thị. Trong bài viết này chúng tôixin trình bày với các bạn
những thuật toán hết sức hiệu quả trênđồ thị có hướng phi chu trình và những bài toán
ứng dụng rất lýthú.
Trước hết ta xét một thuật toánquan trọng sau:
1. Thuật toán đánh số
Định lý: Giả sử G là đồ thị có hướngphi chu trình, khi đó các đỉnh của nó có thể đánh số
sao cho mỗicung của đồ thị chỉ hướng từ đỉnh có chỉ số nhỏ hơn đến đỉnhcó chỉ số lớn
hơn, nghĩa là mỗi cung của nó có thể biểu diễn dướidạng (v[i], v[j]) trong đó i < j.
+ các v[i] là số hiệu cũ của đỉnh, i là số hiệu mới
của đỉnh saukhi được đánh số
+ Đồ thị ở hình bên các đỉnh đãđược đánh số thoả mãn điều kiện nêu trong định lý.
- Để chứng minh định lý ta có thuật toán đánh số cácđỉnh của đồ thị thỏa mãn điều kiện
định lý như sau:
Thuật toán: ta tìm tất cả các đỉnh không có cung đi vào (gọi tắt làđỉnh trọc) lần lượt đánh
số các đỉnh này theo thứ tự tuỳ ý, sauđó xoá các đỉnh trọc vừađánh số và các cung đi ra
từnó khỏi đồ thị, sau đó ta làm lại như trên đối với các đỉnh trọcmới cho đến khi tất cả các
đỉnh được đánh số.
Thuật toán được mô tả trong thủ tụctựa pascal sau:
ProcedureNumbering;
(* đầu vào:đồ thị có hứng G=(V,E) với n đỉnh không chứa chu trình được cho bởidanh
sáchkề ke(v), v thuộc V.
đầu ra: là mảng chỉ số CS, sao cho mỗi cung đêù có dạng(CS[u], CS[v] ) trong đó
u < v.*)
BEGIN
For v thuộc V do Vao[v]:=0;
(* tính bậc vào của đỉnhv *)
For u thuộc V do

Procedurecritical_path;
(* thủ tục tìmđường đi ngắn nhất từ đỉnhnguồn đến tất cả các đỉnh còn lại.
đầu vào: đồ thị G=(V,E), trong đó V = { v[1], v[2],..,v[n].
Với mỗi cung (v[i],v[j] ) thuộc V thì i < j.
đồ thị đượccho bởi ma trận trọng số [ a[i,j] ]
đầu ra: khoảng cách từv[1] đến cả các đỉnh còn lại được ghi trong mảng
D[v[i]] , i = 2 , 3,..,n
Truoc[v[i]] ghi nhận đỉnh đi trước v[i] trên đường đi từ v[1] đến v[i] *)
BEGIN
(* khởi tạo *)
For j :=2 to n do d[v[j]] :=a[v[1],v[j]];
D[v[1]] := 0;
For i:=1 to n �1 do
For j :=i+1 to n do
If (v[i],v[j] ) thuộcE then
Begin
If d[v[j]]>d[v[i]]+ a[v[i],v[j]] then
Begin
D[v[j]]:=d[v[i]] + a[v[i],v[j]];
Truoc[v[j]]:=v[i];
End;
End;
END ;
Ta thấy bản thuật toán trên là quyhoạch động với công thứcquy hoạch động là
D[v[j]] = min( d[v[j]] , d[v[i]] + a[v[i],v[j]] ).
Nhận xét:
+ trong thủ tục trên mỗicung của đồ thị phải xét quađúng một lần do đó độ phức tạp của
thuật toán chỉ có 0(m).
+ thủ tục trênchỉ cho phép tìm đườn đi ngắn nhất, vậy để tìm được đường đi dài nhất
ta phải đổidấu toàn bộ trọng số trên cung, hoặc đổi chiều bất đẳng thức trongthủ tục.

đoạn cuối cùng đượcthực hiên xong. Vậy thực chất bài toán tìm thời điểm ngắn nhất
hoànthành các công việc chính là bài toán tìm đường đi dài nhất từđỉnh 0 đến đỉnh n+1 trên
đồ thị G, do đó ta có thể áp dụng thuậttoán tìm đường đi dài nhấttrên đồ thị có hướng phi
chu trình nêu ở phần trên để giải bàitoán này. Có lẽ để cài đặt bài này thì không có gì là
khó do vậytôi để cho các bạn tự cài đặt cũng là giúp các bạn phần nào hiểurõ thêm về thuật
toán.
Bài toán 2: Mua vé tàu hoả:
Tuyến đường sắt từ A đến B đi qua một số nhà ga. Tuyếnđường có thể biểu diễn bởi một
đoạn thẳng, các nhà ga là các điểmtrên nó, các nhà ga sẽ được đánh số từ 1 đến n bắt đầu
từ nhàga A đến B (n là số lượng nhà ga). Giá vé đi giữa hai nhà ga phụthuộc vào khoảng
cách giữa chúng, cụ thể cách tính giá vé đượccho bởi bảng sau:
Trong đó 1≤L1 < L2 <L3 ≤10
9
, 1 ≤C1 < C2 < C3≤ 10
9
Vé đi từ nhà ga này đến nhà ga khácchỉ có thể đặt mua nếu khoảng cách giữa chúng không
vượt quá L3. Nếukhoảng cách giữa hai nhà ga lớn hơn L3 thì ta phải mua một số vé.
Yêu cầu: tìm cách đặt mua vé để đi lạigiữa hai nhà ga cho trước với chi phí mua vé là nhỏ
nhất.
Dữ liệu: vào từ file Rticket.inp:
- Dòng đầu tiên ghi các sốnguyên L1, L2, L3, C1, C2, C3.
- Dòng thứ 2 ghi số N (2 ≤ N ≤8000).
- Dòng thứ 3 ghi hai số nguyên S, T làchỉ số của hai nhà ga mà ta cần tìm cách đặt mua vé
với chi phí nhỏnhất.
- Dòng thứ i trong số N-1 dòng tiếptheo ghi số nguyên là khoảng cách từ nhà ga A (ga 1)
đến nhà ga i (i = 2 , 3.. N)
Kết quả: ghi ra file Rticket.out chi phí nhỏ nhất tìm được:
Ví dụ:
Xét bài toán:
Việc đi lại(chi phí) từ S đến T tương đương với từ T đến S. Do vậy nếu sốhiệu S > T thì ta

readln(f,s,t);
a[1]:= 0;
for i:=2 to n do readln(f,a[i]);
close(f);
if s > t then
begin
tg := s; s :=t; t := tg;
end;
end;
function cp(u,v :byte):longint;
var k:longint;
begin
k := a[v] - a[u];
if k <= l1 then cp := c1
else
if k <= l2 thencp := c2
else
if k <= l3then cp := c3
else cp :=Maxk;
end;
procedure critical_path;
var i, j : byte;
k : longint;
begin
for i:=s to t do w[i] := Maxk;
w[s] := 0;
for i:=s to t-1 do
for j:=i+1 to t do
begin
k := cp(i, j);