ĐẠI HỌC THÁI NGUYÊN
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG

TRẦN THỊ PHƯƠNG THẢO

NGHIÊN CỨU CÁC THUẬT TOÁN VỀ CÂY KHUNG
VÀ ỨNG DỤNG

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Thái Nguyên, 2015


LỜI CAM ĐOAN
Tên em là Trần Thị Phương Thảo, học viên lớp Cao học K12E, chuyên
ngành Khoa học máy tính, khóa học 2013 – 2015. Em xin cam đoan luận văn:
“NGHIÊN CỨU CÁC THUẬT TOÁN VỀ CÂY KHUNG VÀ ỨNG DỤNG ”

Dưới sự hướng dẫn của PGS TSKH. Nguyễn Xuân Huy - Trường Đại học
Công nghệ thông tin và Truyền thông, Đại học Thái Nguyên , với các nội
dung trình bày được trích dẫn đầy đủ từ các nguồn tài liệu tham khảo chính
thống (báo khoa học, các sách có bản quyền), các nội dung trình bày trong
luận văn hoàn toàn trung thực. Và đây là công trình nghiên cứu của bản thân
kết hợp với sự hướng dẫn của PGS TSKH.Nguyễn Xuân Huy tạo lập ra.
Nếu có nội dung nào sao chụp lại hoặc không phải do chính bản thân
tạo ra, em xin hoàn toàn chịu tránh nhiệm và chịu các hình thức kỷ luật.

Phú Thọ, ngày 4 tháng 10 năm 2015
HỌC VIÊN
Trần Thị Phương Thảo


2. Đối tượng và phạm vi nghiên cứu..............................................................2
3. Phương pháp nghiên cứu............................................................................2
4. Hướng nghiên cứu của đề tài......................................................................3
5. Những nội dung nghiên cứu chính.............................................................3
CHƯƠNG 1: TỔNG QUAN VỀ CÂY KHUNG..........................................4
1.1 MỘT SỐ KHÁI NIỆM LIÊN QUAN TỚI ĐỒ THỊ...............................4
1.1.1 Định nghĩa đồ thị .................................................................................4
1.1.2. Các loại đồ thị ....................................................................................5
1.1.3. Bậc của đồ thị ...................................................................................6
1.2. ĐỒ THỊ CON, ĐỒ THỊ BỘ PHẬN.................................................8
1.2.1. Đồ thị con, đồ thị bộ phận .................................................................8
1.2.2. Đường đi, chu trình trong đồ thị..........................................................8
1.3 TỔNG QUAN VỀ CÂY KHUNG........................................................10
1.3.1 Định nghĩa về cây...............................................................................10
1.3.2 Cây khung ..........................................................................................11
1.3.3 Cây khung cực tiểu.............................................................................12
1.3.4 Rừng khung, rừng khung cực tiểu......................................................13
1.3.4.1 Rừng khung.....................................................................................13
1.3.4.2 Rừng khung cực tiểu.......................................................................14
1.3.5 Cầu, cạnh trọng yếu...........................................................................15
1.3.6 Khớp...................................................................................................16
1.3.7 Liên thông hóa...................................................................................16
1.4 BIỂU DIỄN ĐỒ THỊ TRÊN MÁY TÍNH.............................................20


1.4.1 Ma trận kề và ma trận trọng số...........................................................21
1.4.2 Ma trận liên thuộc..............................................................................22
1.4.3 Danh sách kề......................................................................................23
CHƯƠNG 2: TÌM HIỂU MỘT SỐ THUẬT TOÁN VỀ CÂY KHUNG....25
2.1 GIỚI THIỆU KỸ THUẬT FIND UNION............................................25

n đỉnh thì cây khung của đồ thị này có n đỉnh và n - 1 cạnh. Nhiều bài toán
trong thực tiễn đòi hỏi phải xây dựng cây khung với các biến thể khác nhau,
thí dụ: Bài toán du lịch, bài toán kết nối mạng máy tính, bài toán quản lý vốn
vay của địa phương.
Một số biến thể của cây khung cũng được vận dụng nhiều trong thực tiễn
[3] Thí dụ: Một mạng giao thông có nhiều cầu. Khi một cầu bị phá thì mạng
vẫn có thể liên thông. Một cầu được gọi là trọng yếu nếu như khi bỏ cầu đó
thì mạng mất liên thông [3]. Trong chiến tranh đối phương thường quan tâm
phá những cầu trọng yếu. Trong một mạng máy tính đường nối giữa hai máy
được xem là trọng yếu nếu đường nối đó bị đứt thì mạng mất tính liên thông.
Một đỉnh trong đồ thị liên thông được gọi là trọng yếu hay đỉnh khớp nếu
bỏ đỉnh đó và những cạnh liên thuộc thì đồ thị mất tính liên thông [3].


2

Để xác định được các cầu trọng yếu hoặc đỉnh khớp ta cần dựa vào khái
niệm cây khung. Thí dụ, mọi cầu trọng yếu đều phải thuộc một cây khung nào
đó.
Với những lí do trên học viên chọn đề tài nghiên cứu các thuật toán về cây
khung và ứng dụng nhằm các mục đích sau:
- Tìm hiểu các khái niệm về đồ thị nói chung và đồ thị liên thông nói riêng.
- Tìm hiểu sâu về cây khung và các thuật toán liên quan đến cây khung và các
biến thể của cây khung.
- Xây dựng một số ứng dụng cây khung giải quyết một số vấn đề thực tiễn:
Bài toán kết nối mạng, bài toán quản lý giao thông, bài toán quản lý cụm hải
đảo và các quần thể động thực vật.
2. Đối tượng và phạm vi nghiên cứu
a. Đối tượng nghiên cứu:
Tổng quan lý thuyết về cây khung.

TỔNG QUAN VỀ CÂY KHUNG
1.1 MỘT SỐ KHÁI NIỆM LIÊN QUAN TỚI ĐỒ THỊ
( Các khái niệm cơ bản liên quan đến đồ thị được trình bày chi tiết trong tài
liệu [1,2,6])
1.1.1 Định nghĩa đồ thị
Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh của
đồ thị. Các loại đồ thị khác nhau được phân biệt dựa trên kiểu và số lượng
cạnh nối hai đỉnh nào đó của đồ thị.
u
y

x

- Nếu cạnh u = (x,y) mà x và y là hai đỉnh phân biệt thì ta nói x, y là hai đỉnh
kề nhau.
- Nếu u = (x,x) thì u là cạnh có hai đỉnh trùng nhau ta gọi đó là một khuyên.
u
x
- Nếu u = (x,y) mà x,y là cặp đỉnh có phân biệt thứ tự hay có hướng từ x đến
y thì u là một cung, khi đó x là gốc còn y là ngọn hoặc x là đỉnh ra, y là đỉnh
vào.

xX

y


5

- Khi giữa cặp đỉnh (x, y) có nhiều hơn một cạnh thì ta nói những cạnh cùng

hướng là đồ thị mà mọi u=(x, y)  V đều là cung.


6

5

2

4

3

6

8

1

7

Hình 1.2: Đơn đồ thị có hướng gồm 8 đỉnh và 7 cạnh
c. Đồ thị hỗn hợp
Đồ thị G=<V,E> được gọi là đồ thị hỗn hợp nếu tất cả các cạnh u  E mà
cặp đỉnh thuộc nó u = (x,y) có nhiều hơn một đường đi.

1

3


Nếu tập cạnh E là hữu hạn thì tổng giá trị bậc của các đỉnh gọi là bậc của đồ
thị. Bậc của đồ thị bằng hai lần số cạnh. Số các đỉnh bậc lẻ luôn là số chẵn.
Bậc cực đại của đồ thị G, ký hiệu Δ(G), là bậc lớn nhất của các đỉnh trong đồ
thị; bậc cực tiểu, δ(G), là bậc nhỏ nhất của các đỉnh trong đồ thị.
b. Bậc của đồ thị có hướng

A

B

E

D

C

Hình 1.4: Đồ thị có hướng
Xét đồ thị cho trong hình 1.4 Ta có:
deg - (a)=1, deg - (b)=2, deg - (c)=2, deg - (d)=2, deg - (e) = 2.
deg + (a)=3, deg + (b)=1, deg + (c)=1, deg + (d)=2, deg + (e)=2.


8

Bậc của một đỉnh v là số cạnh liên thuộc với v (trong đó, khuyên được tính
hai lần). Bậc của v được ký hiệu là

.

Trong một đồ thị có hướng, bậc trong của đỉnh v là số cung kết thúc tại v,

từ đỉnh đó thì phần còn lại của đồ thị được gọi là đồ thị con của đồ thị G đã
cho.
- Nếu trong đồ thị G ta bỏ đi một số cạnh nhưng giữ nguyên các đỉnh thì phần
còn lại của đồ thị được gọi là đồ thị bộ phận của đồ thị G.
1.2.2. Đường đi, chu trình trong đồ thị


9

Đường đi có độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương,
trên đồ thị vô hướng G = (V, E) là dãy x 0 , x 1 ,…, x n-1 , x n
trong đó u = x 0 , v = x n , (x i , x i+1 ) ∈ E, i = 0, 1, 2,…, n-1.
Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh:
(x 0 , x 1 ), (x 1 , x 2 ), …, (x n-1 , x n )
Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi. Đường đi có
đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi làchu trình . Đường đi
hay chu trình được gọi là đơn nếu như không có cạnh nào bị lặp lại.

a

b

d

e

c

f


G liên thông và không có chu trình đơn, Đồ thị vô hướng không có chu trình
đơn gọi là rừng (hợp của nhiều cây), với n = V > 1.
Khi đó sáu tính chất sau là tương đương
(1) G là đồ thị liên thông và không có chu trình
(2) G không có chu trình và có n - 1 cạnh
(3) G liên thông và có n - 1 cạnh
(4) G không có chu trình và nếu thêm vào một cạnh nối 2 đỉnh
không kề nhau thì G xuất hiện duy nhất một chu trình.
(5) G liên thông và nếu bỏ đi một cạnh tuỳ ý thì đồ thị nhận được
sẽ không liên thông.
(6) Mỗi cặp đỉnh trong G nối với nhau bằng một đường duy nhất.


11

Hình 1.17: Cây
1.3.2 Cây khung
Định nghĩa : Cây khung (còn gọi là cây bao trùm) của một đồ thị n đỉnh, m
cạnh là cây gồm n đỉnh với số cạnh tối thiểu bảo toàn tính liên thông của đồ
thị.
Cho đồ thị G = <V, E> với số đỉnh n lớn hơn 1.
Giả sử G' là đồ thị bộ phận của G (G' nhận được từ G bằng cách bỏ đi một số
cạnh nhưng vẫn giữ nguyên đỉnh). Nếu G' = <V, E'> là một cây thì G' gọi là
cây bao trùm của G. Theo đúng tính chất về cây. G' là cây bao trùm phải có
n - 1 cạnh và là một đồ thị liên thông không có chu trình.
Giả sử G = (V, E) là đồ thị vô hướng. Cây T = (V, F) với F  E gọi là cây
khung của đồ thị G. Tức là nếu như loại bỏ một số cạnh của G để được một
cây thì cây đó gọi là cây khung (hay cây bao trùm của đồ thị).
Dễ thấy rằng với một đồ thị vô hướng liên thông có thể có nhiều cây khung.
Điều kiện cần và đủ để một đồ thị vô hướng có cây khung là đồ thị đó phải


1

3

7

6

8

5

2

2
2

4
4
6

3

Hình 1.23
Cây khung cực tiểu của đồ thị G có trọng số = 30.
1.3.4 Rừng khung, rừng khung cực tiểu
1.3.4.1 Rừng khung
Định nghĩa : Cho G là một đồ thị vô hướng gồm n đỉnh và m cạnh. Hãy xác
định các cây khung trong mỗi mảnh liên thông của G. Tập hợp các cây khung


7

5

8

1

2

Hình 1.25
Rừng gồm 2 cây khung
1.3.4.2 Rừng khung cực tiểu
Định nghĩa: Cho đồ thị G vô hướng và liên thông với n đỉnh và m cạnh,
cạnh (u,v) có trọng số p(u,v) là một số dương. Rừng khung cực tiểu của G là
rừng khung với tổng trọng số của các cạnh trong khung là nhỏ nhất.

9
4

7
3

5

7

9



2

5

3

3

6

8

2

1

Hình 1.27
Rừng khung cực tiểu
1.3.5 Cầu, cạnh trọng yếu
Định nghĩa : Một cạnh trong đồ thị G được gọi là cầu hoặc cạnh trọng yếu
nếu xóa cạnh đó đi (giữ lại các đỉnh ở hai đầu), sẽ làm tăng số thành phần liên
thông của đồ thị.
cầu phải là cạnh khung, nghĩa là phải thuộc một cây hoặc rừng khung.

5

4

6

con liên thông, các đồ thị con này đôi một không có đỉnh chung. Các đồ thị
con liên thông rời nhau như vậy được gọi là các thành phần liên thông của đồ
thị đang xét.


17

G2
G1

G3

Hình 1.29 : Đồ thị G và các thành phần liên thông G1, G2, G3 của nó
Đôi khi, việc xoá đi một đỉnh và tất cả các cạnh liên thuộc với nó sẽ tạo ra
một đồ thị con mới có nhiều thành phần liên thông hơn đồ thị ban đầu, các
đỉnh như thế gọi là đỉnh cắt hay điểm khớp.
Hoàn toàn tương tự, những cạnh mà khi ta bỏ nó đi sẽ tạo ra một đồ thị có
nhiều thành phần liên thông hơn so với đồ thị ban đầu được gọi là một cạnh
cắt hay một cầu.

Khớp

Cầu


18

Hình 1.30 : Khớp và cầu
a. Đồ thị vô hướng liên thông
Định nghĩa: Đồ thị vô hướng G = (V, E) được gọi là liên thông nếu luôn tìm

Trong hình 1.31 : Đồ thị G là liên thông.
Trong hình 1.32 : Đồ thị H là không liên thông.
Ta gọi đồ thị con của đồ thị G = (V, E) là đồ thị H = (W, F), trong đó W ⊆ V
và F ⊆ E.

b. Đồ thị có hướng liên thông
Đối với đồ thị có hướng có hai khái niệm liên thông phụ thuộc vào việc ta có
xét đến hướng trên các cung hay không.

a

e

c

b

d

Hình 1.34 Đồ thị có hướng.


20

Định nghĩa 1 : Đồ thị có hướng G=<X,U> được gọi là liên thông mạnh
nếu luôn luôn tìm được đường đi giữa 2 đỉnh bất kỳ của nó.
Định nghĩa 2 : Đồ thị có hướng G=<X,U> được gọi là liên thông yếu nếu
đồ thị vô hướng tương ứng (tức là đồ thị đã cho được thay các cung bởi các
cạnh) với nó là đồ thị liên thông.
Rõ ràng nếu đồ thị là liên thông mạnh thì nó cũng là liên thông yếu, nhưng