1
M
M
Ụ
Ụ
C
CL
L
Ụ
Ụ
C
CI. PHẦN ĐẶT VẤN ĐỀ: 2
I.1/ Lý do chọn đề tài 2
I.2/ Mục tiêu nghiên cứu 2
I.3/ Nhiệm vụ nghiên cứu 2
I.4/ Đối tượng nghiên cứu 2
I.5/ Các phương pháp nghiên cứu 2
II/. PHẦN NỘI DUNG: 3
II.1/ Lịch sử của vấn đề nghiên cứu 3
II.2/ Cơ sở lý luận của đề tài 3
II.3/ Thực trạng của vấn đề nghiên cứu 3
II.4/ Nội dung nghiên cứu và kết quả nghiên cứu 3
A/ NỘI DUNG NGHIÊN CỨU 3
1. MỘT SỐ KHÁI NIỆM CƠ BẢN 3
1.1. Đồ thị 3

Trong nghiên cứu này, các học sinh được chọn là các em học lớp chuyên Tin học
khối 10, 11, 12; các học sinh được bồi dưỡng trong đội tuyển dự thi HSG cấp tỉnh, cấp
quốc gia và một số giáo viên đứng lớp dạy tin học ở trường THPT Chuyên Tiền Giang.
I.5/ Các phương pháp nghiên cứu
* Phương pháp suy luận, tổng hợp: kết hợp từ nhiều nguồn tài liệu tham khảo của
các tác giả và tra cứu trên mạng internet với các đề thi Học sinh Giỏi rút ra những kinh
nghiệm, hệ thống lại kiến thức, mở ra các hướng mới.
* Phương pháp trò chuyện – phỏng vấn: trao đổi tâm tình với nhiều học sinh giỏi
để nắm tình hình trong việc giải các bài toán tin về lý thuyết đồ thị.
* Phương pháp khảo sát: bản thân được tham gia giảng dạy các lớp, đội tuyển
HSG, các kỳ tập huấn, ra đề; tham khảo đồng nghiệp, quý Thầy Cô đã giảng dạy đội
tuyển nhiều năm nên có nắm được tình hình sử dụng các phương pháp làm bài của các
em học sinh.
3
* Phương pháp phân tích lý luận: phân tích giúp học sinh nắm thật rõ bản chất vấn
đề, lựa chọn được phương pháp giải cho phù hợp.
II/. PHẦN NỘI DUNG:
II.1/ Lịch sử của vấn đề nghiên cứu
Trong những năm liên tiếp dạy bồi dưỡng HSG môn Tin Học lớp 10, 11, 12 và
đội tuyển dự thi HSG cấp Tỉnh, cấp Quốc Gia, đội tuyển dự thi Olympic 30/4 dành cho
các trường THPT, cũng như tham khảo ý kiến các đồng nghiệp chuyên dạy bồi dưỡng
đội tuyển ở các Tỉnh bạn, ở các trường THPT Chuyên, tôi rút ra một điều là “CƠ SỞ
TOÁN HỌC RẤT QUAN TRỌNG TRONG DẠY LẬP TRÌNH”. Được sự động viên
khuyến khích của quý Thầy Cô trong tổ, tôi mạnh dạng chọn viết đề tài “Cơ sở toán học
của một số bài toán trong lý thuyết đồ thị”.
II.2/ Cơ sở lý luận của đề tài
Kết hợp các bài giảng và tài liệu tham khảo, kinh nghiệm bản thân để phân tích,
tổng hợp, hệ thống lại.
II.3/ Thực trạng của vấn đề nghiên cứu
Đa số học sinh chuyên tin rất ngại, sợ khi giải các bài toán tin có ứng dụng toán

đầu của một cạnh hoặc một cung.
Hai cạnh a, b (hoặc hai cung a, b) gọi là hai cạnh kề nhau (hoặc hai cung kề
nhau) nếu chúng có một đỉnh chung.
Khuyên là cạnh (hoặc cung) có 2 đầu trùng nhau.
Đỉnh treo là đỉnh thuộc duy nhất một cạnh hoặc cung.
Đỉnh cô lập là đỉnh không thuộc cạnh hoặc cung nào.
1.1.3. Phân loại đồ thị
Cho đồ thị G = (V, E), nếu E chỉ gồm các cạnh thì G là đồ thị vô hướng. Nếu E
chỉ gồm các cung thì G là đồ thị có hướng. Nếu E gồm cả cạnh và cung thì G là đồ thị
hỗn hợp.
Đa đồ thị: Đồ thị G = (V, E) vô hướng (hoặc có hướng) là đa đồ thị khi và chỉ
khi nó là đồ thị không khuyên và có ít nhất một cặp đỉnh được nối với nhau bằng ít nhất
2 cạnh (hoặc 2 cung nối theo thứ tự của cặp đỉnh).
Đơn đồ thị: Đồ thị G = (V, E) vô hướng (hoặc có hướng) là đơn đồ thị khi và chỉ
khi nó là đồ thị không khuyên và mỗi cặp đỉnh được nối với nhau không quá một cạnh
(hoặc cung).

Vô hướng Có hướng Vô hướng Có hướng
Đơn đồ thị Đa đồ thị
Hình 1.2. Phân loại đồ thị
5
1.1.4. Bậc của đỉnh:
1.1.4.1. Định nghĩa: Bậc của đỉnh v trong đồ thị G = (V, E), ký hiệu deg(v), là số
các cạnh liên thuộc với nó, riêng khuyên tại một đỉnh được tính hai lần cho bậc của nó.
Đỉnh v gọi là đỉnh treo nếu deg(v) = 1 và gọi là đỉnh cô lập nếu deg(v) = 0.

Hình 1.3
deg(v
1
) = 7

Chứng minh: Rõ ràng mỗi cạnh e = (u, v) được tính một lần trong deg(u) và
một lần trong deg(v). Từ đó suy ra tổng tất cả các bậc của các đỉnh bằng hai lần số cạnh.
1.1.4.3. Hệ quả: Số đỉnh bậc lẻ của một đồ thị là một số chẵn.
Chứng minh: Gọi V
1
và V
2
tương ứng là tập các đỉnh bậc chẵn và tập các đỉnh
bậc lẻ của đồ thị G = (V, E). Khi đó:
1 2
2|E| = deg( ) deg( )
v V v V
v v
 

 

Vế trái là một số chẵn và tổng thứ nhất cũng là một số chẵn nên tổng thứ hai là
một số chẵn. Vì deg(v) là lẻ với mọi v  V
2
nên |V
2
| là một số chẵn.
1.1.4.4. Mệnh đề: Trong một đơn đồ thị, luôn tồn tại hai đỉnh có cùng bậc.
Chứng minh: Xét đơn đồ thị G = (V, E) có |V| = n. Bậc của mỗi đỉnh trong đồ
thị có n đỉnh nhận các giá trị từ 0 đến n – 1. Rõ ràng trong đồ thị không thể đồng thời có:
một đỉnh có bậc 0 (đỉnh cô lập) và một đỉnh có bậc n – 1 (có cạnh nối với tất cả các đỉnh
còn lại). Vì vậy theo bậc của các đỉnh, ta chỉ có thể phân n đỉnh thành n – 1 nhóm. Vậy
theo nguyên lý Dirichlet tồn tại một nhóm có ít nhất 2 đỉnh, tức là luôn tìm được ít nhất 2
đỉnh có bậc bằng nhau.

deg
t
(v
3
) = 2, deg
o
(v
3
) = 4
deg
t
(v
4
) = 1, deg
0
(v
4
) = 3
deg
t
(v
5
) = 1, deg
o
(v
5
) = 0
deg
t
(v


Hình 1.5. Đơn đồ thị, vô hướng

Hình 1.6. Đa đồ thị, vô hướng
7 Hình 1.7. Đa đồ thị, có hướng
1.2.2. Biểu diễn đồ thị trên máy tính
1.2.2.1. Biểu diễn đồ thị bằng ma trận liền kề (ma trận liền kề)
Giả sử đồ thị G = (V, E) có tập đỉnh V = {u
1
, u
2
, …, u
n
}, tập cạnh (hoặc cung) là
E. Ta xây dựng ma trận vuông A cấp n sao cho  i, j: 1 ≤ i, j ≤ n có:
 


 









1

0

2

0

0

0

1

1

3

1

0

0

0

1

4


3

4

5

1

0

0

1

0

0

2

0

0

0

1

0


0

0

0Nhận xét:
- Nếu G là đồ thị vô hướng thì ma trận A sẽ đối xứng qua đường chéo chính,
ij ji
A A | i, j:1 i, j n
   
. Tổng các số trên hàng i = Tổng các số trên cột i = Bậc của
đỉnh i = deg(i)
- Nếu G là đồ thị có hướng, A là ma trận liền kề tương ứng thì trên ma trận A
Tổng các số trên hàng i = Bán bậc ra của đỉnh i = deg
t
(i)
Tổng các số trên cột i = Bán bậc vào của đỉnh i = deg
o
(i)
8
Trong trường hợp G là đơn đồ thị, ta có thể biểu diễn ma trận liền kề A tương ứng
là các phần tử logic. A
ij
= TRUE nếu (i, j)  E và A
ij
= FALSE nếu (i, j)  E.

Ưu điểm của ma trận liền kề:

j
) ngược lại khi không có cạnh nối u
i
với u
j
(hoặc không có cung nào
nối trực tiếp u
i
tới u
j
) thì C[i, j] =  (kí hiệu  là giá trị không xác định). Trong nhiều
trường hợp, ngầm định C[i, i] = 0 với mọi đỉnh trong đồ thị không khuyên.

Hình 1.10
1 2 3 4 5
1

0 0
15

20

0
2

0 0 0
29

12


ta liệt kê và lưu tất cả các cạnh/cung của đồ thị. Trong cách biểu
diễn này, người ta liệt kê tất cả các cạnh của đồ thị trong một
danh sách, mỗi phần tử của danh sách là một cặp (u, v) tương
ứng với một cạnh của đồ thị. (Trong trường hợp đồ thị có hướng
thì mỗi cặp (u, v) tương ứng với một cung, u là đỉnh đầu và v là
đỉnh cuối của cung). Danh sách được lưu trong bộ nhớ dưới
dạng mảng hoặc danh sách móc nối. Ví dụ với đồ thị bên:

Hình 1.11

Cài đặt trên mảng:
1 2 3 4 5
(1, 3) (2, 4) (3, 5) (4, 1) (5, 2)

Cài đặt trên danh sách móc nối:

Ưu điểm của danh sách cạnh:
 Trong trường hợp đồ thị thưa (có số cạnh tương đối nhỏ: chẳng hạn m < 6n),
cách biểu diễn bằng danh sách cạnh sẽ tiết kiệm được không gian lưu trữ, bởi
nó chỉ cần 2m ô nhớ để lưu danh sách cạnh.
 Trong một số trường hợp, ta phải xét tất cả các cạnh của đồ thị thì cài đặt trên
danh sách cạnh làm cho việc duyệt các cạnh dễ dàng hơn. (Thuật toán Kruskal
chẳng hạn)
Nhược điểm của danh sách cạnh:
 Nhược điểm cơ bản của danh sách cạnh là khi ta cần duyệt tất cả các đỉnh kề
với đỉnh v nào đó của đồ thị, thì chẳng có cách nào khác là phải duyệt tất cả
các cạnh, lọc ra những cạnh có chứa đỉnh v và xét đỉnh còn lại. Điều đó khá
tốn thời gian trong trường hợp đồ thị dày (nhiều cạnh).
1.2.2.4. Biểu diễn bằng danh sách kề
Cho đồ thị G = (V, E), với mỗi đỉnh u

Xây dựng 2 mảng một chiều A và P với ý nghĩa sau: Các vị trí j trong mảng A từ
P[i-1]+1 đến P[i] cho biết A[j] là đỉnh kề với đỉnh i.
Ví dụ: Với đồ thị như hình 1.13 có số đỉnh là N = 5, số cạnh là M = 6
Mảng




A 1 2*M = 2, 3, 5, 1, 3, 1, 2, 4, 3, 5,
1, 4

Mảng




P 0 N = 0, 3, 5, 8, 10, 12

Dựa vào hai mảng A và P có thể biết các đỉnh kề với đỉnh 3 là các đỉnh từ vị trí
p[2]+1 = 5 + 1 = 6 tới vị trí p[3] = 8 trong mảng A; đó là các đỉnh A[6] = 1, A[7] = 2 và
A[8] = 4.
Lưu ý rằng với đồ thị có hướng gồm m cung thì cấu trúc Forward Star cần phải
đủ chứa m phần tử, với đồ thị vô hướng m cạnh thì cấu trúc Forward Star cần phải đủ
chứa 2m phần tử.
Ưu điểm của danh sách kề:
 Đối với danh sách kề, việc duyệt tất cả các đỉnh kề với một đỉnh v cho trước là
hết sức dễ dàng, cái tên “danh sách kề” đã cho thấy rõ điều này. Việc duyệt tất
cả các cạnh cũng đơn giản vì một cạnh thực ra là nối một đỉnh với một đỉnh
khác kề nó.
Nhược điểm của danh sách kề:

trên đồ thị có hướng G = (V, E) là dãy các đỉnh
0 1 2
, , , ,
k
u u u u u v
 
mà các cung
1
( , ) , 0, 1
i i
u u E i k

  
. Đường đi này còn có thể biểu diễn dưới dạng dãy các cung:
0 1 1 2 1
( , ),( , ), ,( , )
k k
u u u u u u

. Đỉnh u gọi là đỉnh đầu, đỉnh v gọi là đỉnh cuối của đường đi.
2.1.3. Định nghĩa 3. Đường đi có đỉnh đầu trùng với đỉnh cuối gọi là một chu trình
(mạch vòng).
Đường đi hay chu trình được gọi là đơn nếu không có cung nào bị lặp lại.
Đường đi hay chu trình được gọi là cơ bản nếu không có đỉnh nào bị lặp lại (trừ
trường hợp trong chu trình thì đỉnh đầu trùng đỉnh cuối là được lặp lại).
2.1.4. Định nghĩa 4. Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn
tìm được đường đi giữa hai đỉnh bất kì của nó.
2.1.5. Định nghĩa 5. Cho đồ thị vô hướng G = (V, E) và đồ thị con của G là đồ thị
' ( ', ')
G V E

đường đi nào nối u và v. Khi đó trong đồ thị G tồn tại hai thành phần liên thông là G
1
có
n
1
đỉnh và chứa u, G
2
chứa đỉnh v và có n
2
đỉnh. Vì G
1
, G
2
là hai trong số các thành phần
liên thông của G nên n
1
+n
2
 n. ta có:




1 2 1 2
deg u deg v (n 1) (n 1) n n 2 n 2 n
          
.
Điều mâu thuẫn ở trên dẫn đến kết luận là đồ thị G phải liên thông.
2.1.10. Hệ quả: Đơn đồ thị mà bậc của mỗi đỉnh của nó không nhỏ hơn một nửa số
đỉnh là đồ thị liên thông.

tất nhiên sẽ đến được từ S. Với mỗi đỉnh x kề với S đó thì tất nhiên những đỉnh y kề với
x cũng đến được từ S Điều đó gợi ý cho ta viết một thủ tục đệ quy DFS(u) mô tả việc
duyệt từ đỉnh u bằng cách thông báo thăm đỉnh u và tiếp tục quá trình duyệt DFS(v) với
v là một đỉnh chưa thăm kề với u.
- Để không một đỉnh nào bị liệt kê tới hai lần, ta sử dụng kỹ thuật đánh dấu, mỗi
lần thăm một đỉnh, ta đánh dấu đỉnh đó lại để các bước duyệt đệ quy kế tiếp không duyệt
lại đỉnh đó nữa
- Để lưu lại đường đi từ đỉnh xuất phát S, trong thủ tục DFS(u), trước khi gọi đệ
quy DFS(v) với v là một đỉnh kề với u mà chưa đánh dấu, ta lưu lại vết đường đi từ u tới
v bằng cách đặt DD[v] := u, tức là DD[v] lưu lại đỉnh liền trước v trong đường đi từ S tới
v. Khi quá trình tìm kiếm theo chiều sâu kết thúc, đường đi từ S tới F sẽ là:


1 2 1
F p DD F p DD[p ] S
     
.
procedure DFS(uV);
begin
1. Thông báo tới được u;
2. Đánh dấu u là đã thăm (có thể tới được từ S);
3. Xét mọi đỉnh v kề với u mà chưa thăm, với mỗi đỉnh v đó
begin
DD[v] := u; {Lưu vết đường đi, đỉnh mà từ đó tới v là u}
DFS(v);{Gọi đệ quy duyệt tương tự đối với v}
end;
end;
Begin {Chương trình chính}
Nhập dữ liệu: đồ thị, đỉnh xuất phát S, đỉnh đích F;
Khởi tạo: Tất cả các đỉnh đều chưa bị đánh dấu;

……
Quá trình được thực hiện cho đến khi tất cả các đỉnh có thể đến được từ đỉnh nguồn
đều đã được thăm.

Ví dụ: Tìm kiếm BFS trên đồ thị Hình 2.3 bắt đầu từ đỉnh 1, sẽ lần lượt thăm các
đỉnh là: 1, 2, 4, 12, 6, 7, 10, 11, 5, 14, 3, 8, 9, 13, 15.
Lưu ý:
 Mỗi thủ tục DFS(S), BFS(S) sẽ cho phép thăm tất cả các đỉnh cùng một thành
phần liên thông với s.
 Hai thủ tục được gọi tìm kiếm từ mọi đỉnh chưa được thăm, vì vậy sẽ thăm
được tất cả các đỉnh (mỗi đỉnh một lần): dù đồ thị có liên thông hay không liên
thông.
15
3. MỘT SỐ BÀI TẬP ÁP DỤNG:
3.1. Tìm đường đi giữa hai đỉnh
3.1.1. Bài toán. Giả sử s và t là hai đỉnh nào đó của đồ thị G. Hãy tìm đường đi từ s
đến t.
3.1.2. Hướng dẫn.
Như trên đã nêu, hai thủ tục DFS(s) và BFS(s) sẽ thăm tất cả các đỉnh cùng vùng
liên thông với s. Do đó, sau khi thực hiện xong thủ tục mà t chưa được thăm
(


dd t false

) thì không tồn tại đường đi từ s tới t. Ngược lại nếu t được thăm
(


dd t true

end;
Close(f);
end;
procedure DFS(u: Integer); {Thuat toan tim kiem theo chieu sau bat dau tu dinh u}
var v: Integer;
begin
for v := 1 to n do
if (Trace[v] = 0) and a[u, v] then {Voi moi dinh v chua tham ke voi u}
begin
Trace[v] := u;
DFS(v); {Tiep tuc tim kiem theo chieu sau bat dau tu v}
end;
end;
procedure Result; {In duong di tu X toi Y}
begin
if Trace[Y] = 0 then {Neu Y chua danh dau tham tuc la khong co duong}
WriteLn(g, ‘Path from ‘, X, ‘ to ‘, Y, ‘ not found’)
16
else {Truy vet duong di, bat dau tu Y}
begin
while Y <> X do
begin
Write(g, Y, ‘ <- ‘);
Y := Trace[Y];
end;
WriteLn(g, X);
end;
end;
begin
Enter;

procedure read_inp;
var f: text;
i, j: integer;
begin
assign(f, fi); reset(f);
readln(f, n);
fillchar(a, sizeof(a), 0);
while not seekeof(f) do {tao ma tran ke}
begin
17
read(f, i);
while not seekeoln(f) do
begin
read(f, j);
a[i, j] := 1;
a[j, i] := 1;
end;
readln(f);
end;
close(f);
end;
procedure DFS(i: integer);
var j: integer;
begin
for j :=1 to n do
if v[j] = 0 then {dinh j chua thuoc vung lien thong nao}
if a[i, j] =1 then {j ke voi i}
begin
v[j] := sv; {ghi nhan dinh j thuoc cung vung lien thong voi i la vung sv}
DFS(j); {tim kiem tiep tu dinh j}

Read_inp;
solve;
write_out;
END.
Hoàn toàn tương tự, nếu trong chương trình trên thay thủ tục DFS(i) bằng thủ tục
BFS(i) sẽ có chương trình tìm số thành phần liên thông theo thuật toán tìm kiếm chiều
rộng.
Ngoài phương pháp trên, còn dùng phương pháp hợp nhất các vùng liên thông
thành một vùng liên thông lớn hơn.
18
Phương pháp 2. Hợp nhất dần các vùng liên thông tiến hành như sau:
 Ban đầu coi mỗi đỉnh thuộc một vùng, số hiệu vùng của đỉnh là số hiệu của đỉnh.
 Thực hiện vòng lặp:
- Duyệt lần lượt các cạnh. Nếu 2 đỉnh liên thuộc một cạnh thuộc hai vùng liên thông
khác nhau thì hợp nhất hai vùng liên thông này bằng cách: chọn số hiệu vùng của
đỉnh có số hiệu nhỏ hơn làm số hiệu vùng chung cho các đỉnh thuộc hai vùng này.
- Lặp cho đến khi không còn hai vùng liên thông nào có thể hợp nhất với nhau.

3.2.2. Thành phần liên thông của đồ thị có hướng
a) Một số nhận xét
- Khi thực hiện tìm kiếm DFS trên đồ thị có hướng G sẽ hình thành cây tìm kiếm
DFS của G. Đỉnh r được gọi là một điểm chốt nếu từ các đỉnh thuộc nhánh gốc r (của cây
tìm kiếm DFS trên G) không có cung nối tới một đỉnh đã thăm trước r.
- Mỗi thành phần liên thông mạnh
1
G
sẽ nằm hoàn toàn trong một nhánh thuộc
cây tìm kiếm DFS của G, nhánh này có gốc là một điểm chốt và tập đỉnh của
1
G

Trong một xóm có n người và giữa hai người i và j có thể đã biết nhau hoặc chưa
biết nhau. Để thắt chặt mối quan hệ giữa mọi người trong xóm, xóm trưởng quyết định
19
như sau: Nếu một người z biết hai người người x và y mà người x chưa biết người y thì
người z phải giới thiệu người x cho người y để hai người làm quen với nhau.
Ví dụ: Trong xóm có 4 người 1, 2, 3 và 4. Người 1 biết người 2, người 3. Người 2
biết người 4 thì:
Người 1 sẽ giới thiệu người 2 với người 3.
Người 2 (đã biết người 3) sẽ giới thiệu người 3 với người 4.
Người 2 giới thiệu người 1 với người 4.
Với cách làm như xậy, xóm trưởng muốn biết là mọi người trong xóm có biết tất cả
nhau không?
Dữ liệu vào gồm: Đọc từ file văn bản Lamquen.Inp có cấu trúc như sau:
 Dòng đầu là số n (số người trong xóm).
 Các dòng kế tiếp, mỗi dòng là một cặp (x, y) thể hiện cho một cặp người đã biết
nhau.
Dữ liệu ra: Ghi ra file văn bản Lamquen.Out số 1 nếu tất cả mọi người trong xóm sẽ biết
nhau và số 0 trong trường hợp ngược lại.
Lamquen.inp

Lamquen.out
4
1 2
1 3
2 4
1
Hướng dẫn
Ta coi mỗi người là một đỉnh và mỗi quan hệ là một cạnh nối giữa hai đỉnh tương
ứng với hai người. Lúc đó ta sẽ có một đồ thị G = <V, E> với V= {1, 2, , n} và E =
{(x, y) với x, y có quan hệ}. Ví dụ với dữ liệu vào đã cho ta có đồ thị được biểu diễn trên

5
1 2
3 2
Hướng dẫn.
 Thực hiện vòng lặp.
1. Tìm một ô chứa số 0 chưa thăm là ô x có tọa độ dòng và cột là (i, j).
2. Loang (tìm kiếm theo chiều rộng) để tìm được miền 0 chứa ô x. Trong quá
trình loang cũng tính diện tích của miền (mỗi lần đến một ô mới thì tăng diện
tích một đơn vị).
3. Mỗi lần thực hiện xong loang thì tìm được một miền 0 chứa ô (i, j), lưu kết
quả (tọa độ i, j và diện tích của miền vào mảng kp) đồng thời tăng biến đếm
số miền 0.
Lặp cho đến khi hết ô 0 chưa thăm.
 Hiện số lượng miền 0.
 Duyệt mảng kết để tìm miền 0 có diện tích lớn nhất. Hiện diện tích miền 0 lớn
nhất.
 Duyệt mảng kết lần thứ hai để hiện tọa độ từng ô đại diện cho mỗi miền 0 có
diện tích bằng diện tích của miền 0 lớn nhất.
3.5. Truyền tin trên mạng Tên chương trình: Infor.Pas
Có một nhóm gồm N lập trình viên được đánh số từ 1 tới N, một số người trong họ
có biết địa chỉ email của người khác. Khi biết một thông tin mới họ gửi thông tin đó cho
người mà biết. Bạn là một người rất quan trọng và bạn biết tất cả các mối quan hệ của họ
cũng như bạn có một thông tin rất đặc biệt mà muốn cho tất cả họ đều biết. Hãy lập trình
chỉ ra một số ít nhất các lập trình viên cần cho họ biết thông tin sao cho những người đó
có thể thông báo cho tất cả những người còn lại biết thông tin của bạn.
Dữ liệu cho trong file văn bản với tên Infor.inp trong đó:
 Dòng đầu chứa số N (N ≤ 1000).
 Dòng thứ i trong N dòng tiếp theo chứa danh sách các lập trình viên mà người i
biết địa chỉ email của họ. Nếu người thứ i không biết địa chỉ của bất cứ ai thì dòng
này là dòng trống.

một ô xuất phát và một ô đích.
Kết quả: Đưa ra file văn bản DK_Robot.out thời gian tối thiểu tìm được (nguyên). Nếu
không tới được thì đưa ra số -1.
Ví dụ:
DK_Robot.inp

DK_Robot.out
5 5
2 0 0 1 1
0 1 0 0 1
1 1 0 0 1
0 0 0 0 1
3 1 0 0 1
8
Hình 3.2

Hướng dẫn: Dùng loang theo BFS
3.7. Sói và cừu Tên chương trình: Soicuu.pas
Có một số con cừu trong trại chăn nuôi của Mickey. Trong khi Mickey đang ngủ
say, những con sói đói đã vào trại và tấn công đàn cừu.
Trang trại hình chữ nhật gồm các ô được tổ chức thành hàng và cột. Trên bản đồ thể
hiện trang trại có các kí hiệu: kí tự “. ” là ô rỗng, kí tự “#” là hàng rào, kí tự “o” là cừu và
“v” là chó sói. Hai ô được xem là cùng môt miền nếu ta di chuyển từ ô này sang ô khác
bằng đường đi theo chiều ngang hoặc dọc và không có rào cản. Các ô mà từ đó có thể
thoát khỏi trang trại không được xem là một phần của bất kì miền nào.
May thay, những con cừu biết tự vệ. Chúng có thể chiến đấu với những con sói
trong miền (húc chết sói) nếu số lượng của chúng lớn hơn số lượng sói trong cùng miền.
Ngược lại, những con sói sẽ ăn hết các con cừu trong cùng một miền.
Ban đầu, các con cừu và sói đã được xác định trong các miền của trang trại.
Viết chương trình đếm số cừu và số sói còn sống sót vào buổi sáng hôm sau đó.

v

#

.

#

V

.

#

.

#

#

.

o

#

.

#


#

#

#

#

#

.

#

.

.

o

.

.

.

#

#


#

.

#

.

o

#

o

#

#

o

.

#

#

.

.


#

.
9 12
.

#

#

#

.

#

#

#

#

#

.

.


o

#

.

#

.

#

.

#

.

#

.

.

#

#

o


.

#

.

#

.

.

#

v

#

.

.

.

.

#

.


#

#

.

#

v

v

.

o

#

.

.

.

.

.

.

tích mới là 0: (1-1)*(12+1)=0, cách phân tích thứ hai cho ta tích mới 10: (3-1)*(4+1)=10,
còn cách phân tích thứ ba cho ta 7: (2-1)*(6+1)=7. Nếu như kết quả là khác 0 ta lại lặp
lại thủ tục này đối với số thu được. Rõ ràng áp dụng liên tiếp thủ tục trên, cuối cùng ta sẽ
đến được số 0, không phụ thuộc vào việc ta chọn cách phân tích nào để tiếp tục.
Yêu cầu: Cho trước số nguyên dương N (
4
1 10
N 
), hãy đưa ra tất cả các số nguyên
dương khác nhau có thể gặp trong việc áp dụng thủ tục đã mô tả đối với N.
Dữ liệu vào: từ file văn bản Zero.inp chứa số nguyên dương N.
Kết quả: Ghi ra file văn bản Zero.out :
 Dòng đầu tiên ghi K là số lượng số tìm được.
 Dòng tiếp theo chứa K số tìm được theo thứ tự tăng dần bắt đầu từ số 0.
Lưu ý: Có thể có số xuất hiện trên nhiều đường biến đổi khác nhau, nhưng nó chỉ được
tính một lần trong kết quả. Thí dụ:
Zero.inp Zero.out
12 6
0 3 4 6 7 10
Hướng dẫn:
Đơn giản là sau mỗi lần phân tích thì chắc chắn kết quả mới luôn nhỏ hơn số đó. Vì
vậy ta chỉ cần lưu trữ vào mảng A: [0 10000] of boolean; trong đó A[i] = True nếu nó
xuất hiện trên đường đi đó, ngược lại thì A[i] = False. Bằng cách loang theo chiều sâu,
chúng ta sẽ đánh dấu các số nếu nó được dùng đến, cho đến khi không thể nào loang
được nữa thì dừng.
23
3.9. Bàn cờ thế (CHESSCBG) Tên chương trình: Chess.pas
Một bàn cờ thế là một bảng gồm 4 dòng, 4 cột. Mỗi thế cờ là một cách sắp xếp 8
quân cờ, hai quân khác nhau ở hai ô khác nhau.
Bài toán đặt ra là cho hai thế cờ 1 và 2, hãy tìm một số ít nhất bước di chuyển quân

cờ như sau: mỗi thế cờ xem như một số nhị phân 16 bit, do đó có giá trị thập phân là một
số kiểu Word, ví dụ, thế cờ thứ nhất trong file Dữ liệu là 1111000011100010, có mã hoá
là số 61666. Khi đó mã hoá của các thế cờ chỉ thuộc phạm vi từ 255 đến 65300. Ta sẽ
dùng kĩ thuật tìm kiếm theo chiều rộng để tìm đường đi từ thế T1 đến thế T2.
B/ KẾT QUẢ NGHIÊN CỨU
Qua quá trình nghiên cứu và vận dụng đề tài chuyên đề “CƠ SƠ TOÁN HỌC
CỦA MỘT SỐ BÀI TOÁN TRONG LÝ THUYẾT ĐỒ THỊ” (Phần 1: Duyệt đồ thị cơ
bản), tôi nhận thấy vấn đề này giúp ích rất nhiều cho học sinh chuyên tin học trong việc
học, giúp các em không còn “ngán ngại” chuyên đề này nữa, các em đã hiểu và vận dụng
khá tốt những phần liên quan đến lý thuyết đồ thị ứng dụng vào tin học (như duyệt đồ
thị, tìm số miền liên thông, …); một số em đã bước đầu sáng tạo được những cách giải
hay, các giải mới (tuy là những bài toán còn “đơn giản”). Riêng bản thân tôi sẽ tiếp tục
nghiên cứu sâu hơn nữa về chuyên đề này hy vọng sẽ “làm rõ hơn nữa” để học sinh
chuyên tin thích học và đạt nhiều thành tích hơn nữa.
24
III. PHẦN KẾT LUẬN
III.1/ Kết luận
Tin học và Toán học là hai bộ môn khác biệt nhưng không độc lập với nhau. Biết
vận dụng những kết quả và những suy luận, chứng minh từ toán học sẽ làm cho những
bài toán tin có những giải thuật đơn giản và kết quả rất tốt.
Như vậy, Tin học đã sử dụng cơ sở Toán học rất nhiều. Đặc biệt cơ sở toán học
cho lý thuyết đồ thị dựa vào các định lý, bổ đề trong toán học mà Tin học đã xây dựng
được những thuật toán, giải thuật rất hữu dụng, ngày nay việc ứng dụng lý thuyết đồ thị
vào nhiều dạng bài toán không còn là vấn đề khó khăn như trước đây và có những ứng
dụng rộng rãi.
Tôi viết đề tài nghiên cứu nhằm mục đích cùng trao đổi với Quý Thầy Cô dạy
chuyên đề bồi dưỡng học sinh giỏi Tin học về việc “hệ thống” các kiến thức, một vài kỹ
năng, ứng dụng toán học vào lập trình giải quyết các bài toán tin. Vì kiến thức và thời
gian còn nhiều hạn chế nên chắc rằng nghiên cứu còn có thiếu sót, tôi chân thành đón
nhận sự góp ý của Quý Thầy Cô. Xin chân thành cảm ơn.