ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
TRỊNH THỊ THANH GIANG
CẤU TRÚC CÂY
TRONG ĐỒ THỊ VÔ HƯỚNG
LUẬN VĂN THẠC SĨ TOÁN HỌC
Thái Nguyên - 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC KHOA HỌC
TRỊNH THỊ THANH GIANG
CẤU TRÚC CÂY
TRONG ĐỒ THỊ VÔ HƯỚNG
Chuyên ngành: TOÁN ỨNG DỤNG
Mã số: 60.46.36
LUẬN VĂN THẠC SĨ TOÁN HỌC
Người hướng dẫn khoa học
TSKH. Phan Thị Hà Dương
Thái Nguyên - 2011
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
1
Mục lục
Lời cảm ơn 3
Mở đầu 4
1 Một số khái niệm cơ bản về đồ thị 6
1.1 Các định nghĩa . . . . . . . . . . . . . . . . . . . . . . . 6
1.2 Một số đơn đồ thị đặc biệt . . . . . . . . . . . . . . . . . 7
1.2.1 Đồ thị đầy đủ . . . . . . . . . . . . . . . . . . . . 7
1.2.2 Đồ thị vòng . . . . . . . . . . . . . . . . . . . . . 8
1.2.3 Đồ thị bánh xe . . . . . . . . . . . . . . . . . . . 8
1.2.4 Đồ thị hai phần . . . . . . . . . . . . . . . . . . . 9

dạy và trang bị cho tôi những kiến thức cơ bản trong suốt quá trình tôi
học tập tại trường.
Tôi xin cảm ơn tới Sở GD - ĐT Tỉnh Hà Giang, Ban Giám Hiệu, các
đồng nghiệp Trường THPT Đồng Yên - Bắc Quang - Hà Giang đã tạo
điều kiện cho tôi học tập và hoàn thành kế hoạch học tâp.
Những lời cảm ơn cuối cùng tôi gửi tới những người thân yêu nhất
trong gia đình tôi đã giúp đỡ, chia sẻ, cũng như động viên tôi rất nhiều
để tôi vượt qua khó khăn và đạt được những kết quả trong học tập và
công tác như hiện nay.
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
4
Mở đầu
Lí thuyết đồ thị là ngành khoa học được phát triển từ lâu nhưng lại
có nhiều ứng dụng hiện đại. Những ý tưởng cơ bản của nó được đưa ra
từ thế kỉ XVIII bởi nhà toán học Thụy sĩ tên là Leonhard Euler. Ông
đã dùng đồ thị để giải quyết bài toán cầu K¨onigsberg nổi tiếng.
Lí thuyết đồ thị được ứng dụng rất nhiều trong thực tế. Rất nhiều
bài toán thuộc nhiều ứng dụng khác nhau được giải bằng mô hình đồ
thị.
Một loại đồ thị đặc biệt được gọi là cây. Khái niệm cây đã được dùng
từ năm 1857, khi nhà toán học Anh, Arthur Cayley dùng cây để xác
định những dạng khác nhau của hợp chất hóa học. Từ đó cây đã được
dùng để giải nhiều bài toán trong nhiều lĩnh vực khác nhau.
Luận văn trình bày một số khái niệm cơ bản về đồ thị, cây và một số
tính chất của cây, trình bày công thức tính số cây bao trùm của đồ thị
đầy đủ n đỉnh được đánh nhãn và một số thuật toán tìm cây bao trùm
của đồ thị.
Ngoài phần mở đầu, phần kết luận, luận văn gồm 4 chương.
Chương 1 Một số khái niệm cơ bản về đồ thị
Chương này trình bày một số khái niệm cơ bản về đồ thị và các ví dụ

1.1 Các định nghĩa
Định nghĩa 1.1. Một đơn đồ thị G = (V, E) gồm một tập không
rỗng V là tập các đỉnh và một tập E là tập các cạnh, đó là các cặp không
sắp thứ tự của các đỉnh phân biệt.
Ví dụ 1.1. Đồ thị trong hình 1 là một đơn đồ thị.
Định nghĩa 1.2. Một đa đồ thị G=(V, E) gồm một tập các đỉnh V,
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
7
một tập các cạnh E và một hàm f từ E tới {{u, v}|u, v ∈ V , u = v}. Các
cạnh e
1
và e
2
được gọi là cạnh song song hay cạnh bội nếu f (e
1
) = f (e
2
).
Ví dụ 1.2. Đồ thị trong hình 2 là một đa đồ thị.
Đinh nghĩa 1.3. Hai đỉnh u và v trong một đồ thị vô hướng G
được gọi là liền kề (hay láng giềng) nếu {u, v} là một cạnh của G. Nếu
e = {u, v } thì e gọi là cạnh liên thuộc với các đỉnh u và v. Cạnh e cũng
được gọi là cạnh nối các đỉnh u và v. Các đỉnh u và v được gọi là các
điểm đầu mút của cạnh {u, v }.
Định nghĩa 1.4. Bậc của một đỉnh trong đồ thị vô hướng 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ó. Người ta kí hiệu bậc của đỉnh v là deg(v).
Ví dụ 1.3. Trong hình 3, deg(a) = 0, deg(b) = 3, deg(c) = 5, deg(d)
= 3, deg(e) = 3, deg(f) = 2.
1.2 Một số đơn đồ thị đặc biệt

, v
n
} và {v
n
, v
1
}. Các vòng C
3
, C
4
, C
5
, C
6
biểu
diễn trên hình 5.
1.2.3 Đồ thị bánh xe
Khi thêm một đỉnh vào vòng C
n
, với n  3 và nối đỉnh này với mỗi
một trong n đỉnh của C
n
bằng những cạnh mới, ta sẽ nhận được đồ thị
hình bánh xe W
n
. Các đồ thị hình bánh xe W
3
, W
4
, W

, K
3 ,3
, K
2 ,6
được biểu diễn trên
hình vẽ sau:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
10
1.3 Các đồ thị mới từ đồ thị cũ
Định nghĩa 1.5. Đồ thị con của đồ thị G = (V, E) là đồ thị H=(W,
F), trong đó W ⊆ V và F ⊆ E .
Ví dụ 1.5. Trong hình 9, đồ thị H là đồ thị con của đồ thị G.
Định nghĩa 1.6. Hợp của hai đơn đồ thị G
1
= (V
1
, E
1
) và
G
2
= (V
2
, E
2
) là một đơn đồ thị có tập các đỉnh là V
1
∪ V
2
và tập

2
) = {x
1
, x
2
}, , f (e
n
) = {x
n−1
, x
n
},
với x
0
= u và x
n
= v. Khi đồ thị là đơn ta kí hiệu đường đi này bằng dãy
các đỉnh x
0
, x
1
, , x
n
(vì danh sách các đỉnh này xác định duy nhất một
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
11
đường đi). Đường đi được gọi là một chu trình nếu nó bắt đầu và kết
thúc tại cùng một đỉnh, tức là u=v. Đường đi hoặc chu trình khi đó gọi
là đi qua các đỉnh x
1

của cây. Chương gồm hai mục: Trong mục 2.1 là định nghĩa về cây và
ví dụ minh họa. Mục 2.2 trình bày các tính chất của cây và chứng minh
các tính chất đó. Các kiến thức trong chương này được tham khảo từ
chương 9 trong sách [1].
2.1 Định nghĩa cây
Cây là một đồ thị vô hướng, liên thông và không có chu trình.
Ví dụ 2.1. Trong hình 13, G là một cây vì G liên thông và không có
chu trình, H không là một cây vì H chứa chu trình đơn, ví dụ như chu
trình 1, 7, 2, 6, 1.
2.2 Các tính chất của cây
Định lí 2.1. Cho G = (V, E) là một đơn đồ thị vô hướng. Các mệnh
đề sau là tương đương:
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
13
1. G là một cây.
2. G không chứa chu trình và|V | = |E| + 1.
3. G liên thông và |V | = |E| + 1.
4 .G liên thông nhưng nếu xóa đi một cạnh bất kỳ của G thì đồ thị
nhận được không liên thông nữa.
5. Giữa hai đỉnh bất kì của G có một và chỉ một đường đi.
6. G không chứa chu trình nhưng nếu thêm vào G một cạnh bất kì
thì đồ thị nhận được sẽ có chu trình.
Chứng minh:
• 1 =⇒ 2: Theo định nghĩa của cây thì G không chứa chu trình.
Ta sẽ chứng minh |V | = |E| + 1 bằng phương pháp quy nạp. Giả sử
G có n đỉnh, ta cần chứng minh G có n − 1 cạnh.
Rõ ràng khẳng định trên đúng với n = 1.
Giả sử khẳng định đúng với n − 1.
Ta phải chứng minh khẳng định đúng với n.
Trươc hết ta nhận thấy rằng mọi cây có n đỉnh đều tìm được ít nhất

, v
2
) khỏi G, ta thu được cây G
1
với n − 1 đỉnh, mà theo giả
thiết quy nạp có n − 2 cạnh. Vậy G có n − 2 + 1 = n − 1 cạnh.
• 2 =⇒ 3: Ta chứng minh bằng phản chứng. Giả sử G không
liên thông. Khi đó G phân rã thành k  2 thành phần liên thông
G
1
, G
2
, , G
k
. Do G không chứa chu trình nên mỗi G
i
(i = 1, , k)
cũng không chứa chu trình vì thế mỗi G
i
là một cây. Do đó, nếu gọi |V
i
|
và |E
i
| theo thứ tự là số đỉnh và số cạnh của G
i
, ta có: |V
i
| = |E
i

0
, v
1
, , b = v
k
, v
m
, v
0
. Với hai
đỉnh c, d bất kì của G ta có:
+) Nếu đường đi từ c đến d không chứa cạnh (a, b) thì hiển nhiên vẫn
tồn tại đường đi từ c đến d.
+) Nếu đường đi từ c đến d chứa cạnh (a, b) thì sau khi xóa (a, b) vẫn
tồn tại đường đi từ c đến d là: từ c đi đến a và đi qua v
1
, , b = v
k
, , v
m
và đi đến d.
Vậy sau khi xóa một cạnh của G thì đồ thị nhận được vẫn liên thông
(mâu thuẫn với giả thiết (4)). Do đó chỉ có một và chỉ một đường đi
giữa 2 đỉnh bất kì của G.
• 5 =⇒ 6: G không chứa chu trình, vì nếu có chu trình thì sẽ tìm
được cặp đỉnh của G được nối với nhau bởi hai đường đi. Bây giờ, nếu
thêm vào G một cạnh e nối hai đỉnh u và v nào đó của G. Khi đó cạnh
này cùng với đường đi nối u với v sẽ tạo thành chu trình trong G.
• 6 =⇒ 1: Giả sử G không liên thông. Khi đó gồm ít ra là 2 thành
phần liên thông. Vì vậy, nếu thêm vào G một cạnh nối hai đỉnh thuộc

4
được cho trong hình vẽ sau:
Năm 1889, Cayley đã tìm ra công thức nổi tiếng: có n
n−2
cây bao
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
17
trùm của đồ thị đầy đủ K
n
được gán nhãn. Có nhiều chứng minh của
công thức này. Chứng minh đầu tiên của công thức Cayley là do Pr¨ufer.
Ý tưởng chứng minh của Pr¨ufer là tìm sự tương ứng một - một giữa tập
các cây bao trùm của đồ thị đầy đủ K
n
được gán nhãn và tập các dãy
số Pr¨ufer có độ dài n − 2 được định nghĩa như sau:
Định nghĩa 3.2. Một dãy số Pr¨ufer có độ dài n − 2, với n  2, là
dãy bất kì các số nguyên từ 1 đến n, các chữ số có thể được lặp lại.
Bổ đề 3.1. Có n
n−2
dãy số Pr¨ufer có độ dài n − 2.
Chứng minh: Theo định nghĩa có n cách chọn mỗi phần tử của một
dãy số Pr¨ufer có độ dài n − 2. Khi đó có n − 2 phần tử được chọn, vậy
tổng cộng chúng ta có n
n−2
cách chọn toàn bộ dãy số.
Ví dụ 3.3. Tập các dãy số Pr¨ufer có độ dài 2 là: {(1, 1), (1, 2), (1,
3), (1, 4), (2, 1), (2, 2), (2, 3), (2, 4), (3, 1), (3, 2), (3, 3), (3, 4), (4, 1),
(4, 2), (4, 3), (4, 4)}. Tổng cộng có 4
4−2

Bây giờ hãy xem xét một cây phức tạp hơn trong hình 17. Dãy số
Pr¨ufer tương ứng của nó là gì ?
Hình vẽ 18 minh họa từng bước mã hóa. Trong hình 18(a), đỉnh 1 là
lá với nhãn nhỏ nhất, do đó chúng ta thêm đỉnh kề duy nhất của nó là
đỉnh 3 vào dãy số, dãy số Pr¨ufer thu được dưới đây kí hiệu là P . Ta có
P = (3). Sau đó chúng ta xóa đỉnh 1 khỏi cây. Trong hình 18(b), đỉnh 2
là đỉnh có nhãn nhỏ nhất, chúng ta lại thêm đỉnh kề duy nhất của nó là
đỉnh 4 vào dãy số. Vì vậy chúng ta có P = (3, 4). Sau đó ta xóa đỉnh 2
khỏi cây thì đỉnh 5 là lá với nhãn nhỏ nhất. Chúng ta lại thêm đỉnh kề
duy nhất của nó là đỉnh 3 vào dãy số. Vì vậy chúng ta có P = (3, 4, 3).
Lặp lại quá trình này sau một số bước cho đến khi cây còn lại hai đỉnh.
Trong ví dụ này, đỉnh 6 và 9 là hai đỉnh còn lại. Ta được dãy số Pr¨ufer
tương ứng với cây trong hình 17 là P = (3, 4, 3, 6, 4, 6, 6).
Có thể thấy rằng các cây bao trùm khác nhau của đồ thị đầy đủ K
n
được gán nhãn xác định các dãy số Pr¨ufer khác nhau. Thuật toán giải
mã Pr¨ufer đưa ra thuật toán ngược lại. Nó tìm được cây T với n đỉnh
được gán nhãn ứng với một dãy số Pr¨ufer đã cho có n − 2 phần tử. Cho
một dãy số Pr¨ufer P = (p
1
, p
2
, , p
n−2
). Ta nhận thấy rằng bất kì đỉnh
v nào của T đều xuất hiện deg(v) − 1 lần trong dãy (p
1
, p
2
, , p

Pr¨ufer khác nhau sẽ cho các cây bao trùm khác nhau của đồ thị đầy đủ
K
n
được gán nhãn.
Ta có thuật toán giải mã Pr¨ufer như sau:
Thuật toán : GIẢI MÃ PR
¨
UFER
Đầu vào: Một dãy Pr¨ufer (p
1
, p
2
, , p
n−2
)
Đầu ra: Cây có nhãn với các đỉnh được gán nhãn bởi 1, 2, , n.
P ← dãy số Pr¨ufer đầu vào
n ← |P | + 2
V ← {1, 2, , n}
Bắt đầu với n đỉnh có nhãn 1, 2 , , n.
for i = 1 to n-2 do
v ← phần tử nhỏ nhất của tập V mà không xuất hiện
trong P
Nối đỉnh v đến đỉnh p
i
Xóa v khỏi tập V
Xóa p
i
khỏi P
/ * Bây giờ P = (p

22
Chương 4
Một số thuật toán xây dựng cây
bao trùm của đồ thị vô hướng liên
thông
Chúng ta biết rằng có thể tìm được cây bao trùm của đồ thị nhờ vào
việc loại bỏ các cạnh, nhưng chúng ta có thể xây dựng cây bao trùm
bằng cách lần lượt ghép thêm các cạnh. Tôi sẽ giới thiệu hai thuật toán
dựa trên nguyên tắc này.
Chương này bao gồm hai mục: Trong mục 4.1 chúng tôi trình bày về
thuật toán tìm kiếm ưu tiên chiều sâu. Mục 4.2 trình bày về thuật toán
tìm kiếm ưu tiên chiều rộng. Các kiến thức trong chương này được tham
khảo từ chương 9 trong sách [1] và chương 22 trong sách [2].
4.1 Thuật toán tìm kiếm ưu tiên chiều sâu
Ta sẽ xây dựng cây bao trùm của một đồ thị liên thông bằng phương
pháp tìm kiếm ưu tiên chiều sâu. Nghĩa là sẽ tạo một cây có gốc và
cây bao trùm sẽ là đồ thị vô hướng nền của cây có gốc này. Chọn tùy
ý một đỉnh của đồ thị làm gốc. Xây dựng đường đi từ đỉnh này bằng
cách lần lượt ghép các cạnh vào sao cho mỗi cạnh mới ghép sẽ nối đỉnh
cuối cùng trên đường đi với một đỉnh còn chưa thuộc đường đi. Tiếp tục
ghép thêm các cạnh vào đường đi chừng nào không thể thêm được nữa
thì thôi. Nếu đường đi qua tất cả các đỉnh của đồ thị thì cây do đường
đi này tạo nên sẽ là cây bao trùm. Nhưng nếu đường đi không đi qua
tất cả các đỉnh thì ta lùi lại đỉnh trước đỉnh cuối cùng của đường đi và
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên
23
xây dựng đường đi mới xuất phát từ đỉnh này đi qua các đỉnh còn chưa
thuộc đường đi. Nếu tất cả các đỉnh của đồ thị đều đã được viếng thăm
thì ta tìm được cây bao trùm, ngược lại, ta lại lùi thêm một đỉnh nữa
trên đường đi và xây dựng đường đi mới.