Các bài toán với chu trình đồ thị
Nguyễn Văn Trung
ứng dụng của chu trình trong đồ thị hiện chưa được xét nhiều. Tôi xin đưa ra một số các
bài toán tương đối hay, khó sử dụng tính chất của chu trình mà đem lại cài đặt hết sức đơn
giản so với các thuật giải khác và có phần hiệu quả hơn rất nhiều.
Định nghĩa: Trong một đồ thị có hướng, độ dài của một chu trình của đồ thị là số đỉnh
thuộc chu trình đó.
Bài toán 1: Đồng hồ cổ
Trong một ngôi mộ cổ, các nhà khoa học đã tìm thấy một thiết bị đặc biệt, trên đó có N
nút, mỗi nút khắc một kí tự đặc biệt, ấn vào nút đặc biệt dưới đế, thiết bị bắt đầu hoạt
động! Sau mỗi ngày, vị trí các kí tự lại thay đổi. Kết quả quan sát cho thấy, sau mỗi
khoảng thời gian cố định, kí tự ở vị trí i sẽ chuyển tới vị trí j và mỗi i có một j cố định của
mình. Dĩ nhiên, ở mỗi vị trí chỉ có một ký tự. Ngừơi ta dự đoán đây là lịch đếm ngày phục
vụ cho một công việc nào đó, ví dụ để xác định thời gian luyện dưựơc liệu điều chế các
biệt dựơc bí ẩn hoặc tính tuổi của một người...Số khoảng thời gian từ khi bấm nút khởi
động đến lúc tất cả các ký tự quay trở về vị trí ban đầu của nó đưựơc gọi là chu kỳ của
hoạt động, hay ngắn gọn là chu kỳ. Hãy lập trình xác định chu kỳ của thiết bị tìm thấy, biết
rằng không có chu kỳ nào vựơt quá 10
12
.
Dữ liệu: vào từ file văn bản CLOCK.INP:
- Dòng đầu tiên chứa số nguyên N - số ký tự trên thiết bị (1 <= n <= 10000).
- Các dòng sau chứa N số nguyên A
1
, A
2
,..., A
n
cho biết ký tự ở vị trí i sẽ chuyển tới vị trí
A
i

j := A[j];
until j = i;
end ;
end ;
Ta xét tiếp bài toán : Như vậy ta đã biết sau một khoảng thời gian t[i] thì ký tự ở vị trí i sẽ
về vị trí ban đầu, hiển nhiên sau một khoảng thời gian là BS(t[i]) { bội số của t[i]} thì i
cũng sẽ trở về vị trí ban đầu. Vậy thời gian nhỏ nhất để các ký tự đều trở về vị trí ban đầu
là BCNN(t[i]) i = 1..n. Bài toán đưa về bài toán cơ bản là tìm BCNN của các số cho trước.
Đến đây vấn đề đã được giải quyết ổn thoả, ta có thể bỏ qua bước còn lại của bài toán.
Bài toán 2: Tập các lá bài cực đại:
Cho n lá bài ( n ≤ 20000) được đánh số hiệu từ 1 đến N. Trên mỗi lá bài ghi một số nguyên
F[i], (1 ≤ F[i] ≤ n, i = 1..n), có thể có nhiều lá bài cùng ghi một số. Hãy chọn ra trong n lá
bài trên một tập nhiều nhất các lá bài sao cho tập hợp các số hiệu của các lá bài đựơc chọn
giống hệt với tập hợp của các số ghi trên các lá bài.
Input: file văn bản CARD.INP:
- Dòng đầu ghi số n.
- Dòng tiếp theo gồm n số, số thứ i là số ghi trên lá bài thứ i.
Output: file văn bản CARD.OUT:
- Dòng đầu ghi số k, là số lớn nhất các lá bài đựơc chọn.
- Dòng tiếp theo ghi k số là số hiệu của các lá bài đựơc chọn theo thứ tự tăng dần.
Ví dụ:
Hướng dẫn:
1. Dùng mảng O[1..n] trong đó O[i] = số ghi trên lá bài thứ i, i = 1..n.
2. Mảng đánh dấu free[1..n] trong đó free[i] = false nếu i thuộc một chu trình nào đó,
free[i] = true nếu i không thuộc một chu trình nào, i = 1..n.
3. Ta coi n là bài trên là n đỉnh của một đồ thị có hướng, một cung nối từ đỉnh thứ i đến
đỉnh ghi trên lá bài thứ i tức là O[i], như vậy có n cung tất cả. Một tập các lá bài thoả mãn
đề bài là tập có số hiệu các lá bài trùng với số hiệu các số ghi trên lá bài chứng tỏ với một
đỉnh u thuộc tập được chọn ra, u phải thuộc một chu trình nào đó. Thật vậy:
Giả sử V = {x

Chu trình 3: 4→ 9 →7 →4
Chu trình 4: 10 → 10
Như vậy, mỗi chu trình sẽ cho ta các tập lá bài thoả mãn số hiệu của chúng trùng với tập
các số ghi trên các lá bài. Vậy trong đồ thị này, ta cứu tìm hết các chu trình thì sẽ đưựơc
tập các lá bài cực đại. Như trên đã chứng minh, dễ thấy nếu đỉnh u thuộc một chu trình nào
đó thì hiển nhiên quá trình tìm chu trình sẽ kết thúc sau không quá n lần lặp. Với một đỉnh
không thuộc chu trình nào, ta lặp việc tìm kiếm, nếu số lần tìm kiếm vượt quá n hoặc đỉnh
đó nối với một đỉnh khác đã thuộc chu trình thì ta kết luận đỉnh đó không thuộc chu trình
nào.
Chương trình đựơc cài đặt theo mô hình sau:
{Khai báo }
{Đọc dữ liệu }
procedure Solve;
var
i, j, Loop : Integer;
begin
FillChar(Free, SizeOf(Free), True);
for i := 1 to n do
if Free[i] then {nếu đỉnh i chưa thuộc chu trình nào}
begin
j := i; Loop := 0;
repeat
j := O[j]; Inc(Loop);
if Loop > n then Break; {nếu số lần lặp vượt quá n}
until (j = i) or (not Free[j]) or False;
if j = i then {nếu tìm được chu trình chứa i}
repeat
j := O[j]; Free[j] := False; {đi theo chu trình vừa tìm được để ghi nhận}
until j = i;
end;

Vậy ta thử làm như các bài trên, tìm chu trình và thử xem có điều gì đặc biệt.
Xét ví dụ trên, chu trình tìm được là: 1 → 4 → 2 → 3 (→1). Chúng ta có thể dễ dàng nhận
thấy nếu đổi chỗ 1 và 3, 2 và 4 thì HTDL tại các chi nhánh lúc này là:
1 2 3 4
HTDL: 1 2 4 3
và chỉ cần một lần đổi chỗ 3 và 4 trong ngày hai là xong.
Đến đây, ta có tính chất sau của chu trình trong bài này:
x
1
→ x
2
→ x
3
→… → x
p − 2
→ x
p − 1
→ x
p
→ x
1
. Nếu ta đổi chỗ x
1
với x
p
, x
2
với x
p − 1
,

đang giữ HTDL là k thì ta chỉ việc ghi ra HTDL mà chi nhánh k giữ ban đầu, do đó ta phải
dùng một mảng để ghi lại dữ liệu ta đọc vào, ở chương trình của chúng ta là mảng Giu }
Toàn bộ chương trình giải như sau:
Program HeThongDuLieuCuaNganHang;
Const
InputFile = ’NH.INP’;
OutputFile = ’NH.OUT’;
nMax = 10000;
Type
InterArr = array [1..nMax] of Integer;
Var
Fi, Fo : Text;
Giu, C : InterArr; { Giu[i] là HTDL mà chi nhánh i giữ }
D : ^InterArr; { D[i]= ngân hàng đổi HTDL cho ngân hàng i trong ngày 1}
Free: array [1..nMax] of BooLean; { Mảng này đánh dấu xem một đỉnh đã xét chưa }
n : Integer;
procedure Init;
begin
New(D);
FillChar(Free, SizeOf(Free), True);
end;
procedure Enter;
var
i : Integer;
begin
Assign(Fi, InputFile); Reset(Fi);
ReadLn(Fi, n);
for i := 1 to N do
Read(Fi, Giu[i]);
Close(Fi);