ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Dư Phương Hạnh
NÂNG CAO HIỆU NĂNG THI HÀNH
CÁC PHÉP TOÁN TRÊN ĐỒ THỊ
LUẬN ÁN TIẾN SỸ HỆ THỐNG THÔNG TIN
Hà Nội - 2019
ĐẠI HỌC QUỐC GIA HÀ NỘI
TRƯỜNG ĐẠI HỌC CÔNG NGHỆ
Dư Phương Hạnh
NÂNG CAO HIỆU NĂNG THI HÀNH
CÁC PHÉP TOÁN TRÊN ĐỒ THỊ
LUẬN ÁN TIẾN SỸ HỆ THỐNG THÔNG TIN
Chuyên ngành: Hệ thống thông tin
Mã số: 9480104.01
Người hướng dẫn khoa học:
1. PGS.TS. Nguyễn Hải Châu
2. PGS.TS. Nguyễn Kim Khoa
Hà Nội - 2019
LỜI CẢM ƠN
Luận án được thực hiện tại Trường Đại học Công nghệ - ĐHGQ Hà Nội, dưới sự hướng
dẫn của PGS.TS. Nguyễn Hải Châu và PGS.TS. Nguyễn Kim Khoa (Trường ETS - Đại học
Quebec - Canada).
Trước hết, tôi xin được bày tỏ lòng biết ơn sâu sắc tới PGS.TS. Nguyễn Hải Châu và
PGS.TS. Nguyễn Kim Khoa, những người đã hướng dẫn, đưa ra những định hướng giúp tác
giả hoàn thành bản luận án này. Tôi cũng chân thành cám ơn toàn thể các thầy, cô đồng
nghiệp trong Bộ môn Các hệ thống thông tin đã đồng hành trong nhiều năm, góp nhiều ý
kiến quan trọng để tác giả có thể hoàn thiện các nội dung khoa học của luận án.
Để có được kết quả ngày hôm nay, tôi cũng xin chân thành cảm ơn Trường Đại học Công
nghệ, Khoa Công nghệ Thông tin, các Phòng chức năng của Trường, đã tạo điều kiện thuận
lợi cho tôi trong quá trình nghiên cứu và công tác tại Trường.
Sau cùng, tôi xin chân thành cảm ơn gia đình, những người thân và bạn bè đã giúp đỡ,
động viên tôi trong suốt thời gian thực hiện luận án này!
Hà Nội, tháng 08 năm 2019
Dư Phương Hạnh
i
LỜI CAM ĐOAN
Tôi cam đoan đây là công trình nghiên cứu của riêng tôi. Các nội dung viết chung với
các tác giả khác đều được sự đồng ý của đồng tác giả trước khi đưa vào Luận án. Các kết
quả nêu trong luận án là trung thực và chưa từng được ai công bố trong các công trình nào
khác.
Tác giả
Dư Phương Hạnh
ii
Mục lục
1 GIỚI THIỆU CHUNG 1
1.1 Độnglựcnghiêncứu ............................... 1
1.1.1 Cấu trúc dữ liệu phù hợp để nâng cao hiệu năng thi hành các phép
toántrênđồthị.............................. 2
1.1.2 Xử lý các truy vấn khoảng cách ngắn nhất trên đồ thị động quy mô lớn 2
1.1.3 Nâng cao hiệu năng tính các độ đo quan trọng trong phân tích đồ thị
quymôlớn ................................ 3
1.2 Một số nghiên cứu liên quan . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
1.3 Mục tiêu, phạm vi nghiên cứu, đóng góp và bố cục của luận án . . . . . . . 10
1.3.1 Mụctiêunghiêncứu ........................... 10
1.3.2 Phạm vi và phương pháp nghiên cứu . . . . . . . . . . . . . . . . . . 11
1.4 Các đóng góp chính của luận án . . . . . . . . . . . . . . . . . . . . . . . . . 11
1.5 Tổchứccủaluậnán ............................... 12
2 CƠ SỞ LÝ THUYẾT 14
2.1 Lýthuyếtđồthị.................................. 14
2.1.1 Kháiniệm................................. 14
2.1.2 Kiểuđồthị ................................ 16
2.1.3 Các đặc điểm chính của đồ thị . . . . . . . . . . . . . . . . . . . . . . 17
2.2 Biểudiễnđồthị.................................. 18
2.2.1 Danhsáchcáccạnh............................ 18
2.2.2 Matrậnliềnkề .............................. 18
2.2.3 Danhsáchliềnkề............................. 19
2.2.4 Matrậnliênthuộc ............................ 20
2.2.5 Ma trận hàng thưa nén . . . . . . . . . . . . . . . . . . . . . . . . . . 20
2.3 Các phép toán chính trên đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . 21
2.3.1 Duyệtđồthị................................ 22
2.3.1.1 Duyệt theo chiều rộng trước - BFS . . . . . . . . . . . . . . 22
2.3.1.2 Duyệt theo chiều sâu trước - DFS . . . . . . . . . . . . . . . 24
2.3.2 Phântíchđồthị ............................. 26
iii