ĐẠ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

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


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

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


MỤC LỤC
MỞ ĐẦU........................................................................................................1
1. Tính cấp thiết của đề tài.............................................................................1
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

KẾT LUẬN VÀ HƢỚNG PHÁT TRIỂN...................................................64
Tài liệu tham khảo:......................................................................................66

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


1

MỞ ĐẦU
1. Tính cấp thiết của đề tài
Khái niệm về cây khung đƣợc CayLey đƣa ra năm 1857 [4].
Cây là đồ thị vô hƣớng, liên thông, không có chu trình.
Trong tin học, cây đƣợc dùng để xây dựng các thuật toán, tổ chức các thƣ
mục, các thuật toán tìm kiếm, lƣu trữ và nén dữ liệu,…[3,5]. Có rất nhiều bài
toán vận dụng khái niệm về cây nhƣ: Sửa chữa đƣờng, định chiều các đƣờng
đi trong thành phố, tìm cây khung có nhiều lá nhất…
Cây khung của một đồ thị hữu hạn, vô hƣớng và liên thông là đồ thị con
liên thông chứa mọi đỉnh và ít cạnh nhất [1,2,3,4,5,6,7]. Nếu đồ thị ban đầu có
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.

thể của cây khung trong lớp các đồ thị hữu hạn.
3. Phƣơng pháp nghiên cứu
Sử dụng các phƣơng pháp nghiên cứu chính sau:

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


3

- Phƣơng pháp nghiên cứu lý thuyết: Tổng hợp tài liệu, hệ thống lại các kiến
thức, tìm hiểu các khái niệm, thuật toán sử dụng trong đề tài.
-

:

- Phƣơng pháp thực nghiệm: Điều tra chọn mẫu, xử lý thông tin,...
- Phƣơng pháp trao đổi khoa học, lấy ý kiến chuyên gia.
4. Hƣớng nghiên cứu của đề tài
- Tổng quan về lý thuyết đồ thị và cây khung.
- Nghiên cứu các thuật toán về cây khung.
- Ứng dụng của các bài toán cây khung trong thực tế.
- Cài đặt thử nghiệm chƣơng trình.
5. Những nội dung nghiên cứu chính
Nội dung chính của luận văn đƣợc chia thành ba chƣơng, cụ thể nhƣ sau:

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/

y

http://www.lrc-tnu.edu.vn/


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
cặp đỉnh là những cạnh song song hay là cạnh bội.

x

y

1.1.2. Các loại đồ thị
a. Đồ thị vô hướng
- Đồ thị G=<V,E> đƣợc gọi là đồ thị vô hƣớng nếu tất cả các cạnh u
mà cặp đỉnh thuộc nó u = (x,y) (trong đó x,y

V) không phân biệt thứ tự.

11

5

2
4

3



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

2

5

4

đỉnh 2, 4 và 5 có bậc bằng 3, đỉnh 6 có bậc 1.
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.

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


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

và bậc trong của đỉnh đó. Bậc ngoài cực đại và cực tiểu đƣợc ký hiệu Δ+(Γ) và
δ+(Γ); bậc trong cực đại và cực tiểu, Δ-(Γ) và δ-(Γ). Trong ngữ cảnh rõ ràng,
có thể bỏ qua chỉ số dƣới Γ
1.2. ĐỒ THỊ CON, ĐỒ THỊ BỘ PHẬN
1.2.1. Đồ thị con, đồ thị bộ phận
Cho đồ thị G = (V,E .
- Nếu trong đồ thị đó ta bỏ đi một số đỉnh nào đó và các cạnh (cung) xuất phát
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ị

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


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

Dãy b, c, f, e, b là chu trình độ dài 5. Đƣờng đi a, b, e, d, a, b có độ dài là 5
không phải là đƣờng đi đơn, do cạnh (a, b) có mặt trong nó 2 lần.
Khái niệm đƣờng đi và chu trình trên đồ thị có hƣớng đƣợc định nghĩa hoàn
toàn tƣơng tự nhƣ trong trƣờng hợp đồ thị vô hƣớng, chỉ khác là ta có chú ý
đến hƣớng trên các cung.

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


10

1.3 TỔNG QUAN VỀ CÂY KHUNG
1.3.1 Định nghĩa về cây : Cho đồ thị G = <V, E>, G đƣợc gọi là một cây nếu
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.

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


Hình 1.18

Hình 1.20

Hình 1.19

Hình 1.21

Hình 1.18 đồ thị G.
Hình 1.19, 1.20, 1.21 cây khung của đồ thì G.
1.3.3 Cây 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. Cây khung cực tiểu (còn gọi là cây
bao trùm ngắn nhất) của G là cây khung với tổng trọng số của các cạnh trong
khung là nhỏ

Số hóa bởi Trung tâm Học liệu - ĐHTN

nhất.

http://www.lrc-tnu.edu.vn/


13

Hình 1.22: Đồ thị G

5
8

đó đƣợc gọi là rừng khung của đồ thị G.
Rừng là đồ thị mà mỗi thành phần liên thông của nó là một cây.

4

3

Số hóa bởi Trung tâm Học liệu - ĐHTN

7

5

http://www.lrc-tnu.edu.vn/


14

2

8

6

1

Hình 1.24
Đồ thị vô hƣớng có 8 đỉnh và 8 cạnh.

3

7

9

5
2

5
6

8
3

Số hóa bởi Trung tâm Học liệu - ĐHTN

1

2
3

http://www.lrc-tnu.edu.vn/


15

Hình 1.26
Đồ thị có 8 đỉnh và 8 cạnh dạng x y p

7
4

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

3

2

1

7

8

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


16

Hình 1.28
Đồ thị có 8 đỉnh, 7 cạnh.
Đồ thị có 3 cầu (1,5), (2,5) và (3,7) (tô đậm)



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
Số hóa bởi Trung tâm Học liệu - ĐHTN

Cầu
http://www.lrc-tnu.edu.vn/


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
đƣợc đƣờng đi giữa hai đỉnh bất kỳ của nó.
Định lý 1: Nếu bậc của mọi đỉnh đồ thị vô hƣớng G=<V,E> không nhỏ
hơn một nửa số đỉnh thì đồ thị đó liên thông.
Định lý 2 : Đồ thị vô hƣớng liên thông là định hƣớng đƣợc khi và chỉ khi
mỗi cạnh của nó nằm trên ít nhất một chu trình.

a

b

Đố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

c

b

e

d

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

Số hóa bởi Trung tâm Học liệu - ĐHTN

http://www.lrc-tnu.edu.vn/


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
điều ngƣợc lại là không luôn đúng, nhƣ chỉ ra trong ví dụ dƣới đây.