Luận án Nâng cao hiệu năng thi hành các phép toán trên đô thị

|1 GIỚI THIỆU chung! 1

Ịl.l Dộng lực nghiên cứu| 1

[1.1.1 Cắn trúc dữ liệu phù hợp đe nâng cao hiệu năng tin hành các phép I

I toán trẽn đồ thị| 2

Ịl.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ị I

I 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

Ịl.3.1 Mục tiêu nghiên cihĩỊ 10

Ịl.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 áiĩ| 11

|1.5 Tổ chức cùa luận án| 12

h cơ SỚ LÝ THUYẾtI 14

|2.1 Lý thuyết đồ thị| 14

[2.1.1 Khái niệmỊ 14

[2.1.2 Kiêu dồ thỉ] 16

12.1.3 Các đặc diem chính cùa đồ tÌĩỊ| 17

|2.2 Biểu diễn dồ thị| 18

[2.2.1 Danh sách các cạnhỊ 18

[2.2.2 Ma trận liền kề| 18

12.2.3 Danh sách liền kềl 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 dồ thj] 21

[2.3.1 Duyệt dồ tĩụ| 22

12.3.1.1 Duyệt theo chiều rộng trước - BFS| 22

12.3.1.2 Duyệt theo chiều sâu trưóc - DFS| 24

[2.3.2 Phàn tích dồ thị| 26