Luận án Tiến sĩ Hệ thống thông tin: Nâng cao hiệu năng thi hành các phép toán trên đồ thị

Luận án quan tâm đến bài toán nghiên cứu đề xuất phương pháp tổ chức dữ liệu đồ thị phù hợp kết hợp cùng với những giải pháp song song hoá các phép toán trên đồ thị quy mô lớn cả về số cạnh lẫn số đỉnh để có thể tiến hành xử lý các truy vấn và phân tích trên đồ thị một cách hiệu quả nhất.
Nội dung trích xuất từ tài liệu:
Luận án Tiến sĩ Hệ thống thông tin: Nâng cao hiệu năng thi hành các phép toán trên đồ thị ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ Dư Phương HạnhNÂ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ạnhNÂ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 - 2019LỜ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ướngdẫn của PGS.TS. Nguyễn Hải Châu và PGS.TS. Nguyễn Kim Khoa (Trường ETS - Đại họcQuebec - 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ácgiả 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ô đồngnghiệ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ôngnghệ, 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ậnlợ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 iLỜ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ớicá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ếtquả 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àokhác. Tác giả Dư Phương Hạnh iiMục lục1 GIỚI THIỆU CHUNG 1 1.1 Động lực nghiên cứ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án trê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ị quy mô 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ục tiêu nghiên cứ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ức của luận án . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 CƠ SỞ LÝ THUYẾT 14 2.1 Lý thuyết đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 2.1.1 Khái niệ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ểu diễn đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.1 Danh sách các cạnh . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.2 Ma trận liền kề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.2.3 Danh sách liền kề . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 2.2.4 Ma trận liên thuộ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ân tích đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 iiiMỤC LỤC iv 2.3.2.1 Tính khoảng cách . . . . . . . . . . . . . . . . . . . . . . . 26 2.3.2.2 Đường đi ngắn nhất . . . . . . . . . . . . . . . . . . . . . . 27 2.3.2.3 Độ trung tâm . . . . . . . . . . . . . . . . . . . . . . . . . . 29 2.3.3 Mật độ đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 2.3.4 Phân cụm đồ thị . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 ...