Giáo trình Lý thuyết đồ thị - Lê Văn Hạnh

 với 
máy j là m(i,j) (thơng thường chi phí này phụ thuộc vào độ dài cáp nối cần sử dụng). Hãy tìm cách 
nối mạng sao cho tổng chi phí là nhỏ nhất. Bài tốn này cũng dẫn về bài tốn tìm cây khung nhỏ 
nhất. 
 Bài tốn tìm cây khung nhỏ nhất đã cĩ những thuật tốn rất hiệu quả để giải chúng. Trong 
tài liệu này sẽ xét hai trong số những thuật tốn như vậy: thuật tốn Kruskal và thuật tốn Prim. 
6.2.3. Thuật tốn Kruskal 
Thuật tốn sẽ xây dựng tập cạnh ET của cây khung nhỏ nhất T=(VT, ET) theo từng bước. Trước 
hết sắp xếp các cạnh của đồ thị G theo thứ tự khơng giảm của trọng số. Bắt đầu từ ET=, ở mỗi bước 
ta sẽ lần lượt duyệt trong danh sách cạnh đã sắp xếp, từ cạnh cĩ độ dài nhỏ đến cạnh cĩ độ dài lớn 
hơn, để tìm ra cạnh mà việc bổ sung nĩ vào tập ET khơng tạo thành chu trình trong tập này. Thuật 
tốn sẽ kết thúc khi ta thu được tập ET gồm n1 cạnh. Cụ thể cĩ thể mơ tả như sau: 
(i). Bắt đầu từ đồ thị rỗng T cĩ n đỉnh. 
(ii). Sắp xếp các cạnh của G theo thứ tự khơng giảm của trọng số. 
(iii). Bắt đầu từ cạnh đầu tiên của dãy này, ta cứ thêm dần các cạnh của dãy đã được xếp vào 
T theo nguyên tắc cạnh thêm vào khơng được tạo thành chu trình trong T. 
(iv). Lặp lại Bước 3 cho đến khi nào số cạnh trong T bằng n1, ta thu được cây khung nhỏ 
nhất cần tìm. 
Chương 6 - Cây 
Lê Văn Hạnh Jan17 69 
Ví dụ: Tìm cây khung nhỏ nhất của đồ thị cho trong hình dưới đây: 
Bắt đầu từ đồ thị rỗng T cĩ 6 đỉnh. 
Sắp xếp các cạnh của đồ thị theo thứ tự khơng giảm của trọng số: 
(v3,v5) (v4,v6) (v4,v5) (v5,v6) (v3,v4) (v1,v3) (v2,v3) (v2,v4) (v1,v2) 
4 8 9 14 16 17 18 20 33 
Đầu tiên, thêm vào đồ thị T cạnh (v3, v5). 
Do số cạnh của T là 1<61 nên tiếp tục thêm cạnh (v4, v6) vào T. Bây giờ số cạnh của T đã là 
2 vẫn cịn nhỏ hơn 6, ta tiếp tục thêm cạnh tiếp theo trong dãy đã sắp xếp vào T. Sau khi thêm cạnh 
(v4, v5) vào T, nếu thêm cạnh (v5, v6) thì nĩ sẽ tạo thành với 2 cạnh (v4, v5), (v4, v6) đã cĩ trong T một 
chu trình. Tình huống tương tự cũng xãy ra đối với cạnh (v3, v4) là cạnh tiếp theo trong dãy. Tiếp theo 
ta bổ sung cạnh (v1, v3), (v2, v3) vào T và thu dược tập ET gồm 5 cạnh: 
{(v3, v5), (v4, v6), (v4, v5), (v1, v3), (v2, v3)}. 
6.2.4. Thuật tốn Prim 
Thuật tốn Kruskal làm việc kém hiệu quả đối với những đồ thị dày (đồ thị cĩ số cạnh m  
n(n1)/2). Trong trường hợp đĩ, thuật tốn Prim tỏ ra hiệu quả hơn. Thuật tốn Prim cịn được gọi là 
phương pháp lân cận gần nhất. 
B1: VT:={v*}, trong đĩ v* là đỉnh tuỳ ý của đồ thị G. 
ET:=. 
B2: Với mỗi đỉnh vjVT, tìm đỉnh wjVT sao cho 
m(wj,vj) = min m(xi, vj)=:j 
 xiVT 
và gán cho đỉnh vj nhãn [wj, j]. Nếu khơng tìm đuợc wj như vậy (tức là khi vj khơng kề với 
bất cứ đỉnh nào trong VT) thì gán cho vj nhãn [0, ]. 
B3: Chọn đỉnh vj* sao cho j* = min j 
vjVT 
VT := VT  {vj*}, 
ET := ET  {(wj*, vj*)}. 
Nếu |VT| = n thì thuật tốn dừng và (VT, ET) là cây khung nhỏ nhất. 
Nếu |VT| < n thì chuyển sang Bước 4. 
B4: Đối với tất cả các đỉnh vjVT mà kề với vj*, ta thay đổi nhãn của chúng như sau: 
 Nếu j > m(vj*, vj) thì đặt j:=m(vj*, vj) và nhãn của vj là [vj*, j]. Ngược lại, ta giữ 
nguyên nhãn của vj. Sau đĩ quay lại Bước 3. 
Hình 5.2. Cây ban đầu Hình 5.3. Cây khung nhỏ nhất 
v2 
v3 
v1 
v4 
v5 
v6 v1 
v2 
v3 
v4 
v5 
v6 
33 
17 
18 16 
4 
9 
8 
14 
20 
Chương 6 - Cây 
Lê Văn Hạnh Jan17 70 
Ví dụ 2: Tìm cây khung nhỏ nhất bằng thuật tốn Prim của 
đồ thị gồm các đỉnh A, B, C, D, E, F, H, I được cho 
bởi ma trận trọng số sau, với gốc là A: 
Yêu cầu viết các kết quả trung gian trong từng 
bước lặp, kết quả cuối cùng cần đưa ra tập cạnh và độ 
dài của cây khung nhỏ nhất. 
V.lặp A B C D E F H I VT ET 
K.tạo  [A,15] [A,16] [A,19] [A,23] [A,20] [A,32] [A,18] A  
1   [A,16] [B,13] [A,23] [B,19] [B,20] [B,12] A, B (A,B) 
2   [A,16] [I,11] [I,21] [I,18] [I,14]  A, B, I (A,B), (B,I) 
3   [D,13]  [I,21] [I,18] [I,14]  A, B, I, D (A,B), (B,I), (I,D) 
4     [I,21] [I,18] [I,14]  A, B, I, 
D, C 
(A,B), (B,I), 
(I,D), (D,C) 
5     [I,21] [H,17]   A, B, I, 
D, C, H 
(A,B), (B,I), 
(I,D), (D,C), (I,H) 
6     [I,21]    A, B, I, 
D, C, H, 
F 
(A,B), (B,I), 
(I,D), (D,C), 
(I,H), (H,F) 
7         A, B, I, 
D, C, H, 
F, E 
(A,B), (B,I), 
(I,D), (D,C), 
(I,H), (H,F), (I,E) 
Vậy độ dài cây khung nhỏ nhất là: 
15 + 12 + 11 + 13 + 14 + 17 + 21 = 103. 
(A,B) + (B,I) + (I,D) + (D,C) + (I,H) + (H,F) + (I,E) 
6.3. SO SÁNH HAI THUẬT TỐN Prim  Kruskal 
(i). Xét các cạnh đưa vào cây 
- Prime: thực hiện việc mở rộng tập đã xét (ban đầu chỉ gồm một đỉnh, 0 cạnh thành n đỉnh, 
n-1 cạnh) dựa trên các cạnh ngắn nhất nối giữa tập đã xét và tập chưa xét. Tư tưởng chính 
là thêm vào các cạnh ngắn nhất sao cho khơng tạo ra chu trình. Như vậy, cĩ trường hợp 
một cạnh sẽ phải xét đi xét nhiều lần rồi mới được chọn, thậm chí khơng hề được chọn. 
- Kruskal: cũng thêm lần lượt các cạnh vào đồ thị, theo thứ tự từ trọng nhỏ nhất đến trọng 
lớn nhất (như vậy mỗi cạnh sẽ chỉ được duyệt một lần duy nhất). Ta chỉ bổ sung cạnh vào 
cây khung nếu việc thêm cạnh này khơng làm phát sinh ra chu trình. 
(ii). Kiểm tra tính liên thơng của đồ thị 
- Prim: cần kiểm tra đồ thị liên thơng trước khi thi hành thuật tốn. 
- Kruskal: khơng cần kiểm tra đồ thị liên thơng trước khi thi hành thuật tốn. Nếu quá trình 
thi hành thuật tốn tìm được cây khung/bao trùm thì đồ thị liên thơng và ngược lại là đồ thị 
khơng liên thơng. 
(iii). Chi phí cho việc kiểm tra chu trình 
- Prime: mở rộng tập đỉnh đã xét (mỗi lần 1 đỉnh nên khơng cần kiểm tra chu trình. 
- Kruskal: kiểm tra nếu khi thêm cạnh đang xét vào cây khung mà khơng làm phát sinh chu 
trình thì sẽ chọn cạnh này. Việc kiểm tra chu trình cĩ khả năng gây tốn chi phí 


































14182111191218
14172321202032
18173430211920
21233422293423
11213022131319
19202129133316
12201934133315
18322023191615
Chương 6 - Cây 
Lê Văn Hạnh Jan17 71 
Gợi ý cải tiến giảm chi phí kiểm tra chu trình: 
 Dùng một mảng Nhãn cĩ kích thước bằng số đỉnh của đồ 
thị. Giá trị Nhãn[i] tại đỉnh i được khởi tạo bằng với chính 
chỉ số i của đỉnh. 
Ví dụ: Với đồ thị G ở trên ta cĩ 
Đỉnh 0 1 2 3 
Nhãn 0 1 2 3 
 Khi chọn một cạnh (u,v) được thêm vào cây khung/cây bao trùm, ta sửa nhãn của tất cả 
các đỉnh cĩ cùng giá trị với nhãn của đỉnh v thành nhãn của đỉnh u. 
Ví dụ: 
 Sau khi thêm cạnh (0,1) vào cây khung/cây bao trùm hay tập T, ta sửa nhãn của tất 
cả các đỉnh cĩ cùng giá trị với nhãn của đỉnh 1 (là 1) thành nhãn của đỉnh 0 (là 0). 
Đỉnh 0 1 2 3 
Nhãn 0 0 2 3 
 Sau đĩ, khi chọn tiếp cạnh (0, 3), ta sửa nhãn của đỉnh 3 (đang cĩ giá trị là 3) 
để cĩ cùng giá trị với nhãn của đỉnh 0 (là 0). 
Đỉnh 0 1 2 3 
Nhãn 0 0 2 0 
 Sau đĩ, khi chọn cạnh để thêm vào cây khung/cây bao trùm thì chỉ chọn cạnh cĩ nhãn hai 
đỉnh là khác nhau sẽ khơng tạo thành chu trình. 
Ví dụ: 
 Khi ta xét tới cạnh (1,3): ta khơng chọn cạnh này vì đỉnh 1 và đỉnh 3 cĩ cùng nhãn 
là 0 
 Chọn tiếp cạnh (1,2): 2 đỉnh 1 và 2 cĩ nhãn khác nhau nên cạnh (1,2) sẽ được 
chọnđưa vào cây khung/cây bao trùm. 
Đỉnh 0 1 2 3 
Nhãn 0 0 0 0 
Nhận xét: Sau khi ta đã chọn đủ n-1 cạnh, mảng nhãn chỉ chứa một giá trị duy nhất. 
6.4. CÂY CĨ GỐC 
6.4.1. Định nghĩa về cây cĩ gốc 
- Cây cĩ hướng là đồ thị cĩ hướng mà đồ thị vơ hướng nền của nĩ là một cây. 
- Cây cĩ gốc là một cây cĩ hướng, trong đĩ cĩ một đỉnh đặc biệt, gọi là gốc, từ gốc cĩ đường đi 
đến mọi đỉnh khác của cây. 
Ví dụ: 
 Hình 5.4. Cây cĩ gốc 
r 
a 
b 
c 
e 
g 
d i 
h 
l 
m 
j 
f 
k 
n 
o 
p 
q 
0 3 
2 1 
3 
5 
5 
4 
2 
Chương 6 - Cây 
Lê Văn Hạnh Jan17 72 
Trong cây cĩ gốc thì gốc r cĩ bậc vào bằng 0, cịn tất cả các đỉnh khác đều cĩ bậc vào bằng 1. 
Một cây cĩ gốc thường được vẽ với gốc r ở trên cùng và cây phát triển từ trên xuống, gốc r 
gọi là đỉnh mức 0. Các đỉnh kề với r được xếp ở phía dưới và gọi là đỉnh mức 1. Đỉnh ngay dưới đỉnh 
mức 1 là đỉnh mức 2, ... 
 Tổng quát, trong một cây cĩ gốc thì v là đỉnh mức k khi và chỉ khi đường đi từ r đến v cĩ độ 
dài bằng k. 
 Mức lớn nhất của một đỉnh bất kỳ trong cây gọi là chiều cao của cây. 
 Cây cĩ gốc ở hình trên thường được vẽ như trong hình dưới đây để làm rõ mức của các đỉnh. 
Trong cây cĩ gốc, mọi cung đều cĩ hướng từ trên xuống, vì vậy vẽ mũi tên để chỉ hướng đi là 
khơng cần thiết; do đĩ, người ta thường vẽ các cây cĩ gốc như là cây nền của nĩ. 
6.4.2. Đỉnh ngồi – đỉnh trong 
- Đỉnh treo vn là đỉnh khơng cĩ con; đỉnh treo cũng gọi là lá hay đỉnh ngồi; 
- Một đỉnh khơng phải lá là một đỉnh trong. 
6.4.3. Cây nhị phân 
- Một cây cĩ gốc T được gọi là cây m-phân nếu mỗi đỉnh của T cĩ nhiều nhất là m con. Với 
m=2, ta cĩ một cây nhị phân. 
- Trong một cây nhị phân, mỗi con được chỉ rõ là con bên trái hay con bên phải; con bên trái 
(hoặc bên phải) được vẽ phía dưới và bên trái (hoặc bên phải) của cha. 
- Cây cĩ gốc T được gọi là một cây m-phân đầy đủ nếu mỗi đỉnh trong của T đều cĩ m con. 
6.4.4. Mệnh đề về cây m phân 
- Một cây m-phân đầy đủ cĩ i đỉnh trong thì cĩ mi+1 đỉnh và cĩ (m1)i+1 lá. 
- Một cây m-phân cĩ chiều cao h thì cĩ nhiều nhất là mh lá. 
- Một cây m-phân cĩ l lá thì cĩ chiều cao h  [logml]. 
6.5. DUYỆT CÂY NHỊ PHÂN 
6.5.1. Định nghĩa 
Trong nhiều trường hợp, ta cần “thăm” mọi đỉnh của một cây nhị phân, mỗi đỉnh chỉ một lần. 
Ta gọi đĩ là việc duyệt cây nhị phân hay đọc cây nhị phân. 
 Cĩ nhiều thuật tốn duyệt cây nhị phân, các thuật tốn đĩ khác nhau chủ yếu ở thứ tự thăm các 
đỉnh. 
r 
a b c d 
e g f h i j 
k l m n 
p o q Hình 5.5. Trình bày cây theo dạng “phân mức” 
Chương 6 - Cây 
Lê Văn Hạnh Jan17 73 
 Cây nhị phân T cĩ gốc r được ký hiệu là T(r). Giả sử r cĩ con bên trái là u, con bên phải là v. 
Cây cĩ gốc u và các đỉnh khác là mọi dịng dõi của u trong T gọi là cây con bên trái của T, ký hiệu 
T(u). Tương tự, ta cĩ cây con bên phải T(v) của T. Một cây T(r) cĩ thể khơng cĩ cây con bên trái hay 
bên phải. 
 Sau đây là ba trong các thuật tốn duyệt cây nhị phân T(r). Các thuật tốn đều được trình bày 
đệ quy. Chú ý rằng khi cây T(x) chỉ là mơt đỉnh x thì “duyệt T(x)” cĩ nghĩa là “thăm đỉnh x”. 
Ví dụ : 
6.5.2. Các thuật tốn duyệt cây nhị phân 
6.5.2.1. Thuật tốn Node- Left-Right 
(i). Thăm gốc r. 
(ii). Duyệt cây con bên trái của T(r). 
(iii). Duyệt cây con bên phải của T(r). 
 Kết quả duyệt cây T(a) theo thuật tốn Node- Left-Right là: 
a, b, d, g, l, h, e, i, m, n, c, f, j, o, p, k, q, s. 
6.5.2.2. Thuật tốn Left- Node- Right 
(i). Duyệt cây con bên trái của T(r). 
(ii). Thăm gốc r. 
(iii). Duyệt cây con bên phải của T(r). 
 Kết quả duyệt cây T(a) theo thuật tốn Left-Node- Right là: 
g, l, d, h, b, m, i, n, e, a, c, o, j, p, f, q, k, s. 
6.5.2.3. Thuật tốn Left-Right-Node 
(i). Duyệt cây con bên trái của T(r). 
(ii). Duyệt cây con bên phải của T(r). 
(iii). Thăm gốc r. 
Kết quả duyệt cây T(a) theo Left-Node- Right là: 
l, g, h, d, m, n, i, e, b, o, p, j, q, s, k, f, c, a. 
6.5.3. Ký pháp Ba Lan 
Xét biểu thức đại số sau đây: 
(a+b)(c
2
d
) (1) 
Hình 5.6. 
m 
g p 
e l s 
a f i r v 
t x c h k q s 
Chương 6 - Cây 
Lê Văn Hạnh Jan17 74 
 Ta vẽ một cây nhị phân như hình dưới đây, trong đĩ mỗi đỉnh trong mang dấu của một phép 
tính trong (1), gốc của cây mang phép tính sau cùng trong (1), ở đây là dấu nhân, ký hiệu là  , mỗi 
lá mang một số hoặc một chữ đại diện cho số. 
Duyệt cây nhị phân trong hình trên theo thứ tự Left-Node-Right là: 
a + b  c  d / 2 (2) 
và đây là biểu thức (1) đã bỏ đi các dấu ngoặc. 
 Ta nĩi rằng biểu thức (1) được biểu diễn bằng cây nhị phân T( ) trong hình trên, hay cây 
nhị phân T( ) này tương ứng với biểu thức (1). 
 Ta biết rằng các dấu ngoặc trong (1) là rất cần thiết, vì (2) cĩ thể hiểu theo nhiều cách khác 
(1), chẳng hạn như 
 (a + b  c)  d / 2 (3) 
hoặc là a + (b  c  d) / 2 (4) 
 Các biểu thức (3) và (4) cĩ thể biểu diễn bằng cây nhị phân trong các hình sau. 
Đối với cây trong hình 5.7, nếu duyệt theo Node-Left-Right, ta cĩ 
 + a b  c / d 2 (5) 
và nếu duyệt theo Left-Right- Node, ta cĩ: 
a b + c d 2 /   (6) 
 Cĩ thể chứng minh được rằng (5) hoặc (6) xác định duy nhất cây nhị phân trong hình thứ 
nhất, do đĩ xác định duy nhất biểu thức (1) mà khơng cần dấu ngoặc. Chẳng hạn cây nhị phân trên 
hình 5.8 được duyệt theo Node-Left-Right là 
+ 
 
a b c / 
2 d 
Hình 5.7. Biểu diễn biểu thức (a+b)(cd/2) dưới dạng cây nhị phân 
+ / 
a * d 2 
c b 
 
Hình 5.8. Biểu thức (3)=(a+b c) d/2) 
sau khi đưa vào cây nhị phân 
a / 
d * 
 2 
c b 
+ 
Hình 5.9. Biểu thức (4)=a+(b cd)/2 
 sau khi đưa vào cây nhị phân 
Chương 6 - Cây 
Lê Văn Hạnh Jan17 75 
 + a  b c / d 2 khác với (5). 
và được duyệt theo Left-Right- Node là 
a b c  + d 2 /  khác với (6). 
 Vì vậy, nếu ta viết các biểu thức trong đại số, trong lơgic bằng cách duyệt cây tương ứng theo 
Node-Left-Right hoặc Left-Right- Node thì ta khơng cần dùng các dấu ngoặc mà khơng sợ hiểu nhầm. 
 Người ta gọi cách viết biểu thức theo Node-Left-Right là ký pháp Ba Lan, cịn cách viết theo 
Left-Right-Node là ký pháp Ba Lan đảo, để ghi nhớ đĩng gĩp của nhà tốn học và lơgic học Ba Lan 
Lukasiewicz (1878-1956) trong vấn đề này. 
 Việc chuyển một biểu thức viết theo ký pháp quen thuộc (cĩ dấu ngoặc) sang dạng ký pháp Ba 
Lan hay ký pháp Ba Lan đảo hoặc ngược lại, cĩ thể thực hiện bằng cách vẽ cây nhị phân tương ứng, 
như đã làm đối với biểu thức (1). Nhưng thay vì vẽ cây nhị phân, ta cĩ thể xem xét để xác định dần 
các cơng thức bộ phận của cơng thức đã cho. Chẳng hạn cho biểu thức viết theo ký pháp Ba Lan là 
   /   a b  5 c 2 3   c d 2    a c d /   b  3 d 3 5 
 Trước hết, chú ý rằng các phép tốn +, , *, /,  đều là các phép tốn hai ngơi, vì vậy trong cây 
nhị phân tương ứng, các đỉnh mang dấu các phép tốn đều là đỉnh trong và cĩ hai con. Các chữ và số 
đều đặt ở lá. Theo ký pháp Ba Lan (tương ứng Ba Lan đảo) thì T a b (tương ứng a b T) cĩ nghĩa là a 
T b, với T là một trong các phép tốn +, , *, /, . 
  533*/*2325*/*
35 dcadccba
dbdcadccba 

 
53)3(/)(*2)(325)(/*
3)(5 2

dbdcadccba
dbdcadccba

 
53)3(/)(*)(32)5(/*
3)3(
2
2
5
  
dbcba
dbdcadccba

 


5
)3(
32
2
5
3
3
5)3(/)(*)(3
2
5
*
db
cba
dbdcadc
cba






 


 
    
5
)3(
)(
3
)(
2
5
2
3
3
2
3
5
)3(
)(*)(
2
5
*
db
dcadc
cba
db
dcadc
cba






 






 
 
5
)3(
)()(
2
5 32
3
db
dcadc
cba 





 
Chương 6 - Cây 
Lê Văn Hạnh Jan17 76 
6.6. BÀI TẬP 
6.6.1. Vẽ tất cả các cây (khơng đẳng cấu) cĩ: 
6.5.1.1. 4 đỉnh 6.5.1.2. 5 đỉnh 6.5.1.3. 6 đỉnh 
6.6.2. Một cây cĩ n2 đỉnh bậc 2, n3 đỉnh bậc 3, , nk đỉnh bậc k. Hỏi cĩ bao nhiêu đỉnh bậc 1? 
6.6.3. Tìm số tối đa các đỉnh của một cây m-phân cĩ chiều cao h. 
6.6.4. Cĩ thể tìm được một cây cĩ 8 đỉnh và thoả điều kiện dưới đây hay khơng? Nếu cĩ, vẽ cây đĩ 
ra, nếu khơng, giải thích tại sao: 
6.6.4.1. Mọi đỉnh đều cĩ bậc 1. 
6.6.4.2. Mọi đỉnh đều cĩ bậc 2. 
6.5.4.3. Cĩ 6 đỉnh bậc 2 và 2 đỉnh bậc 1. 
6.6.4.4. Cĩ đỉnh bậc 7 và 7 đỉnh bậc 1. 
6.6.5. Chứng minh hoặc bác bỏ các mệnh đề sau đây. 
6.6.5.1. Trong một cây, đỉnh nào cũng là đỉnh cắt. 
6.6.5.2. Một cây cĩ số đỉnh khơng nhỏ hơn 3 thì cĩ nhiều đỉnh cắt hơn là cầu. 
6.6.6. Cĩ bốn đội bĩng đá A, B, C, D lọt vào vịng bán kết trong giải các đội mạnh khu vực. Cĩ mấy 
dự đốn xếp hạng như sau: 
6.6.6.1. Đội B vơ địch, đội D nhì. 
6.6.6.2. Đội B nhì, đội C ba. 
6.6.6.3. Đội A nhì, đội C tư. 
Biết rằng mỗi dự đốn trên đúng về một đội. Hãy cho biết kết quả xếp hạng của các đội. 
6.6.7. Hãy tìm cây khung của đồ thị sau bằng cách xố đi các cạnh trong các chu trình đơn. 
6.6.8. Cây Fibonacci cĩ gốc Tn đuợc dịnh nghĩa bằng hồi quy như sau. T1 và T2 đều là cây cĩ gốc 
chỉ gồm một đỉnh và với n=3,4,  cây cĩ gốc Tn được xây dựng từ gốc với Tn-1 như là cây 
con bên trái và Tn-2 như là cây con bên phải. 
6.5.7.1. Hãy vẽ 7 cây Fibonacci cĩ gốc đầu tiên. 
6.5.7.2. Cây Fibonacci Tn cĩ bao nhiêu đỉnh, lá và bao nhiêu đỉnh trong. Chiều cao của nĩ 
bằng bao nhiêu? 
6.6.9. Hãy tìm cây khung cho mỗi đồ thị sau. 
6.6.9.1 K5 6.6.9.2 K4,4 6.6.9.3 K1,6 
6.6.9.4 Q3 6.6.9.5 C5 6.6.9.6 W5. 
6.6.10. Đồ thị Kn với n=3, 4, 5 cĩ bao nhiêu cây khung khơng đẳng cấu? 
a b c 
d e f g 
h i j 
a b 
c d e 
h f i 
k 
g 
j 
l Hình 5.11. Hình 5.10. 
Chương 6 - Cây 
Lê Văn Hạnh Jan17 77 
6.6.11. Tìm cây khung nhỏ nhất của đồ thị sau theo thuật tốn Kruskal và Prim. 
6.6.11.1. 
6.6.11.2. 
6.6.12. Duyệt các cây sau đây lần lượt bằng 3 thuật tốn đã học. 
6.6.13. Tìm cây khung nhỏ nhất bằng thuật tốn Prim của 
đồ thị gồm các đỉnh A, B, C, D, E, F, H, I được 
cho bởi ma trận trọng số sau. 
Yêu cầu: viết các kết quả trung gian trong từng bước lặp, 
kết quả cuối cùng cần đưa ra tập cạnh và độ dài 
của cây khung nhỏ nhất. 
a 
c b 
d e 
g 
f 
h 
i j 
e d g f 
b c 
a 
h i 
m n 
 j k 
p q 
l 
o 
Hình 5.13. Hình 5.14. 
a b 
c d e f 
g h 
42 
14 10 4 
3 1 11 
3 
15 5 
7 
20 
9 
Hình 5.12. 


































18142112191120
18172321201932
14173430212018
21233422292419
12213022133323
19202129131315
11192024331316
20321819231516
Chương 6 - Cây 
Lê Văn Hạnh Jan17 78 
6.6.14. Viết các biểu thức sau đây theo ký pháp Ba Lan và ký pháp Ba Lan đảo. 
6.6.14.1. 
BDC
BDA
DCBA
DCBA





2
2
)(
))((
. 
665.14.2. 
5
)243(
3
5
3
)(
342
4 dbadad
c
ba






 






 . 
6.6.15. Viết các biểu thức sau đây theo ký pháp quen thuộc. 
6.5.15.1. x y + 2 ↑ x y − 2 ↑ − x y * /. 
6.5.15.2.    /   a b  3 c 2 4   c d 5    a c d /   b  2 d 4 3. 
6.6.16. Một địa đạo gồm các căn hầm 
với vị trí căn hầm và độ dài từng 
địa đạo như hình vẽ dưới. Nếu 
chỉ yêu cầu giữa các hầm cĩ thể 
cĩ đi tới nhau được bằng đường 
địa đạo. Hãy đưa ra phương án 
phải đào những địa đạo nào 
trong những địa đạo đã cho để 
tổng chiều dài địa đạo phải đào 
là ít nhất. 
6.6.17. Xác định thời gian ngắn nhất dể hồn thành dự án. Biết rằng dự án gồm 8 cơng đoạn, mỗi 
cơng đoạn cĩ thời gian (t[i]) và điều kiện về thời điểm bắt đầu cho trong bảng sau: 
Cơng đoạn t[i] Các cơng đoạn phải được hồn thành trước nĩ 
1 15 Khơng cĩ 
2 30 1 
3 80 Khơng cĩ 
4 45 2, 3 
5 124 4 
6 15 2, 3 
7 15 5, 6 
8 19 5 
A B 
C 
D 
E F 
H 
G 
I 
J 
60 
120 
20 90 30 
80 50 
40 100 
110 
50 60 
70 80 
40 60 100 
120 
60 
Hình 5.15 
Lý thuyết đồ thị 
Lê Văn Hạnh 
TÀI LIỆU THAM KHẢO 
[1]. PGS. Hồng Chí Thành và PGS Lê Trọng Vĩnh - bài giảng Lý Thuyết Đồ Thị, Khoa 
Tốn - Cơ - Tin học, Trường Đại học Khoa học Tự nhiên, ĐHQG HN 
[2]. Giáo trình tốn ứng dụng trong tin học, Vụ giáo dục chuyên nghiệp, NXB Giáo dục 
[3]. PTS.Nguyễn Cam - PTS.Chu Đức Khánh), Lý thuyết đồ thị (ngành Tin học), NXB Trẻ 
[4]. TS. Võ Văn Tuấn Dũng – Giáo trình tốn rời rạc –NXB Lao động – Xã hội -2009 
[5]. Seymour Lipschutz PhD, MarcLars Lipson PhD – Biên dịch Thanh Tâm, Quang Huy, 
Xuân Toại – Tuyển chọn 1800 bài tập tốn rời rạc – NXB Thống kê -2002 
[6]. Trần Ngọc Danh - Tốn rời rạc nâng cao –NXB ĐHQG TP.HCM - 2004 
[7]. – Kenneth h. Rosen – Biên tập Đặng Văn Sử, Trần Hiển - Tốn học rời rạc ứng dụng 
trong tin học – 1997 
[8]. Nguyễn Đức Nghĩa, Nguyễn Tơ Thành, “Tốn rời rạc”. NXB Giáo dục, 1999 
[9]. Kenneth H. Rosen, “Tốn rời rạc và Ứng dụng trong tin học”, NXB Khoa học và Kỹ 
thuật, 2000 
[10]. Jean-Claude Fournier, “Graph Theory and Applications with Exercises and Problems”, 
Wiley, 2009 
[11]. Reinhard Diestel, “Graph Theory”, Springer-Verlag New York, 2005