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

sau một khoảng thời gian. Các số cách nhau ít nhất một dấu cách.
Kết quả: Ra file văn bản CLOCK.OUT số nguyên - chu kỳ của thiết bị
Ví dụ:
Thuật toán :
1. Đánh số các ký tự từ 1 đến N tương ứng với N đỉnh của đồ thị.
2. Sau một khoảng thời gian kí tự i sẽ chuyển tới vị trí A[i], ta coi như đỉnh thứ i của đồ thị
có cạnh nối đến đỉnh A[i], ta được một đồ thị có hướng gồm N đỉnh, một cung sẽ nối từ kí
tự đến kí tự tiếp theo nó biến đổi thành.
3. Gọi t[i] = thời gian để kí tự thứ i chuyển về vị trí ban đầu. Xuất phát từ đỉnh i của đồ thị
dễ nhận thấy từ i chỉ có một đường đi duy nhất để quay trở về i, đường đi đó chính là chu
trình chứa i do đó t[i] = độ dài chu trình chứa đỉnh i.
4. Dùng mảng đánh dấu free[i] = true nếu chưa tìm được chu trình chứa đỉnh i, false nếu
ngược lại.
Đoạn mã sau tìm t[i] với i = 1…n;
procedure findt;
var
i, j, nt : Integer; {nt là biến cho biết độ dài của chu trình đang xét}
begin
FillChar(Free, SizeOf(Free), True);
for i := 1 to n do
if Free[i] then
begin
nt := 0; j := i; {bắt đầu tìm chu trình xuất phát từ đỉnh i}
repeat
Free[j] := False;
Inc(nt);
j := A[j];
until j = i;
repeat
t[j] := nt; {các đỉnh thuộc chu trình đều có thời gian biến đổi là nt }

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

1
, x
2
,…, x
t
} là tập các lá bài được chọn ra.Ta có x
u
thuộc đồ thị có duy
nhất một cung đi ra, giả sử x
u
có cung đến x
u1
, x
u1
có cung đến x
u2
, … cuối cùng x
ui
có
cung đến x
u
vì x
u
thuộc tập được chọn.
Từ đây cũng suy ra mỗi đỉnh chỉ thuộc một chu trình duy nhất.
Xét ví dụ trên, tập chọn ra là
1 2 3 4 5 6 7 8 9 10
Mảng O: 5 6 8 9 3 2 4 1 7 10
Chu trình 1: 1 →5 → 3 → 8 →1
Chu trình 2: 2 → 6 → 2

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;

end;
{Ghi kết quả}
Việc kiểm tra tính đúng đắn của bài toán rất dễ, bạn đọc có thể tự viết chương trình
kiểm tra.
Bài toán 3: Hệ thống dữ liệu của Ngân Hàng.
Một ngân hàng có N chi nhánh có tên từ 1 đến N, mỗi chi nhánh có một hệ thống dữ liệu
(HTDL), hai chi nhánh khác nhau có HTDL khác nhau. Trong một lần thay đổi máy tính
của toàn bộ N chi nhánh, do sơ xuất, ngừơi ta đã cài đặt không đúng vị trí của các HTDL,
chẳng hạn HTDL tại A là của chi nhánh B, tại B là của chi nhánh C, …(có thể có chi nhánh
đã giữ đúng HTDL của nó), mặc dù hai chi nhánh khác nhau vẫn giữ hai HTDL khác
nhau.
Cần phải tiến hành tráo đổi các HTDL giữa các chi nhánh sao cho mỗi chi nhánh có đựơc
HTDL của nó. Giữa hai chi nhánh có thể tiến hành trao đổi trong một ngày, hai cặp máy
khác nhau có thể làm đồn thời công việc này trong cùng một ngày. Hãy tính xem cần ít
nhất bao nhiêu ngày để hoàn tất công việc này.
Input: file văn bản NH.INP
- Dòng đầu ghi số N <= 10000.
- Dòng thứ hai ghi N số, số thứ i là HTDL của chi nhánh mà chi nhánh i đang giữ hiện
thời.
Output: file văn bản NH.OUT
- Dòng đầu ghi số M là số ngày ít nhất cần cho việc tráo đổi.
- M dòng tiếp theo, mỗi dòng gồm n số, số thứ i trong n số đó là số hiệu chi nhánh tiến
hành tráo đổi với chi nhánh thứ i trong ngày đó.
Ví dụ :
Hướng dẫn:
Bài này là một bài tương đối khó nếu giải theo cách giải thông thường. Tuy nhiên điều đặc
biệt ở bài toán này là tuy dữ liệu khá lớn, N ≤ 10000 nhưng thời gian để tráo đổi lại không
lớn, nhiều nhất là hai ngày.
Rõ ràng ta có thể đưa bài toán về giống dạng đồ thị cuả Bài toán 1, với N ngân hàng là N
đỉnh của đồ thị, một đỉnh được nối tới một đỉnh duy nhất là chi nhánh mà nó giữ HTDL.

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
,

x
3
với x
p − 2

,
…, x
i
với x
p + 1 − i
thì lúc này tại một chi nhánh sẽ tồn tại hai khả năng:
- Hoặc nó đã có hệ thống dữ liệu của chính nó.
- Nếu không, nó giữ HTDL của chi nhánh k nào đó và chi nhánh này giữ HTDL của nó.
Tóm lại ta có cách đổi chỗ như sau:
- Ngày 1: Với chi nhánh i, ta tìm chu trình chứa nó và tiến hành tráo đổi như trên : Gọi
nCir là độ dài của chu trình (x
1
, x
2
, …, x
nCir
) với x
1
= i, ta cứ đổi chỗ HTDL của chi
nhánh x
j
với chi nhánh x
nCir + 1 … j
, j = 1..nCir.
- Ngày 2: Sau khi tráo đổi các HTDL của các ngân hàng cho nhau, giả sử ngân hàng thứ i

đ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);

end;