Thạc Sĩ Nghiên cứu các thuật toán về cây khung và ứng dụng

Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


LỜI CẢM ƠN
Điều đầu tiên em xin gửi lời cảm ơn tới các Thầy, Cô Trường Đại học
Công nghệ thông tin và Truyền thông Thái Nguyên trong thời gian vừa qua đã
cung cấp và truyền đạt chương trình học với các môn học có nội dung bổ ích.
Thông qua chương trình học, em được lĩnh hội nhiều về kiến thức chuyên
môn, các phương pháp tiếp cận bài toán trong tin học.
Em xin gửi lời cảm ơn sâu sắc tới PGS TSKH. Nguyễn Xuân Huy,
người Thầy đã hướng dẫn, chỉ bảo, giám sát, theo dõi, cung cấp phương pháp,
nguồn dữ liệu tiếp cận bài toán để em có thể hoàn thành được luận văn của
mình.
Em xin cảm ơn Ban Giám hiệu trường THPT Trần Phú cùng các đồng
nghiệp trong Trường, xin cảm ơn Trường Đại học Công nghệ thông tin và
Truyền thông, Đại học Thái Nguyên đã tạo mọi điều kiện giúp đỡ để em hoàn
thành chương trình học tập và luận văn tốt nghiệp.
Điều cuối cùng em xin cảm ơn gia đình, bạn bè luôn nhiệt tình ủng
hộ, động viên, giúp đỡ cả về vật chất lẫn tinh thần trong thời gian học tập
và nghiên cứu.
Trong quá trình thực hiện luận văn, mặc dù đã có rất nhiều cố gắng
nhưng cũng không tránh khỏi những thiếu sót. Kính mong nhận được sự cảm
thông và tận tình chỉ bảo của các Thầy, Cô và các bạn.
Em xin trân trọng cảm ơn!.
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
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
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/


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
2.2 THUẬT TOÁN TÌM CÂY KHUNG, CÂY KHUNG CỰC TIỂU .31
2.2.1 Thuật toán tìm cây khung 31
2.2.2 Thuật toán tìm cây khung cực tiểu .33
2.3 THUẬT TOÁN LIỆT KÊ CÁC CÂY KHUNG THÀNH PHẦN CỦA
RỪNG KHUNG .40
2.4 THUẬT TOÁN LIỆT KÊ CÁC CÂY KHUNG THÀNH PHẦN CỦA
RỪNG KHUNG CỰC TIỂU .44
2.5 THUẬT TOÁN LIỆT KÊ CÁC CẦU .48
2.6 THUẬT TOÁN LIỆT KÊ CÁC KHỚP 50
CHƯƠNG 3: MỘT SỐ ỨNG DỤNG CỦA BÀI TOÁN CÂY KHUNG GIẢI
QUYẾT VẤN ĐỀ THỰC TẾ .54
3.1 BÀI TOÁN CÁP MẠNG .54
3.2 BÀI TOÁN TUYẾN ĐƯỜNG QUAN TRỌNG TRONG QUÂN SỰ 59
3.3 CÀI ĐẶT CHƯƠNG TRÌNH 64
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.
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].
Số hóa bởi Trung tâm Học liệu - ĐHTN http://www.lrc-tnu.edu.vn/

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ìm hiểu một số thuật toán về cây khung điển hình như: Tìm cây khung, tìm
cây khung cực tiểu, các bài toán về rừng khung, liệt kê các cây khung, cầu
trọng yếu, đỉnh khớp
Các ứng dụng của việc giải quyết các bài toán cây khung vào trong thực tế.
b. Phạm vi nghiên cứu:
Khảo sát, đánh giá tổng quan về lý thuyết cũng như các bài toán và các biến
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: