Khảo sát tính liên thông của đồ thị bằng kỹ thuật FIND - Union và ứng dụng

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

ĐẠ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 BÌNH AN

KHẢO SÁT TÍNH LIÊN THÔNG CỦA ĐỒ THỊ

BÀNG KỸ THUẬT FIND – UNION VÀ ỨNG DỤNG

Chuyên ngành: Khoa học máy tính

Mã số: 60 48 0101

LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH

Người hướng dẫn khoa học: PGS.TS NGUYỄN XUÂN HUY

THÁI NGUYÊN - 2016

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

LỜI CAM ĐOAN

Tôi xin cam đoan đây là công trình nghiên cứu của riêng tôi. Các

số liệu, kết quả đánh giá, nhận xét và các đề xuất cải tiến mới nêu trong

Luận văn là trung thực và chưa từng được ai công bố trong bất kỳ công

trình nào khác.

Tôi xin cam đoan rằng mọi sự giúp đỡ cho việc thực hiện Luận

văn này cũng như các trích dẫn hay tài liệu học thuật tham khảo đã

được cảm ơn đến tác giả hay ghi rõ ràng nguồn gốc thông tin trích dẫn

trong Luận văn.

Học viên thực hiện Luận văn

TRẦN BÌNH AN

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

LỜI CẢM ƠN

Trước hết, cho tôi được gửi lời cảm ơn đến sự hướng dẫn và giúp đỡ

tận tình của PGS TSKH Nguyễn Xuân Huy.

Xin cảm ơn các Thầy/Cô tại trường Đại học Công nghệ Thông tin và

Truyền thông Thái Nguyên đã sát cánh và cung cấp cho tôi những kiến thức

quí báu trong suốt thời gian học tập và nghiên cứu thực hiện luận văn.

Tôi cũng in gửi lời cảm ơn đến gia đình, bạn bè cùng những người thân

đã luôn quan tâm và giúp đỡ tôi trong suốt thời gian học tập, nghiên cứu để

hoàn thành luận văn này.

Luận văn không thể tránh khỏi những sai sót, rất mong nhận được ý

kiến đóng góp của Thầy/Cô và các bạn để luận văn được hoàn thiện hơn.

Tôi xin chân thành cảm ơn.

Thái Nguyên, tháng 4 năm 2016

TRẦN BÌNH AN

i

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

MỤC LỤC

LỜI CAM ĐOAN

LỜI CẢM ƠN

MỤC LỤC...................................................................................................... i

DANH MỤC TỪ VIẾT TẮT.......................................................................iii

DANH MỤC CÁC BẢNG...........................................................................iv

DANH MỤC CÁC HÌNH............................................................................. v

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 ......................................................... 3

2.1. Đối tượng nghiên cứu.............................................................................................3

2.2. Phạm vi nghiên cứu.................................................................................................3

3. Hướng nghiên cứu của đề tài ................................................................. 3

3.1. Về lý thuyết:...............................................................................................................3

3.2. Về thực nghiệm:........................................................................................................3

4. Những nội dung nghiên cứu chính......................................................... 4

Chương 1. TỔNG QUAN VỀ LÝ THUYẾT ĐỒ THỊ HỮU HẠN ............. 5

1.1. Đồ thị và các khái niệm liên quan....................................................... 6

1.1.1. Định nghĩa đồ thị..................................................................................................6

1.1.2. Các loại đồ thị........................................................................................................7

1.1.3. Một số dạng đồ thị đặc biệt..............................................................................9

1.1.4. Bậc của đồ thị...................................................................................................... 12

1.1.5. Đường đi, chu trình, tính liên thông của đồ thị ..................................... 14

1.2. Biểu diễn đồ thị trên máy tính........................................................... 16

1.2.1. Ma trận kề, ma trận trọng số........................................................................ 16

1.2.2. Danh sách cạnh (cung)................................................................................... 19

1.2.3. Danh sách kề ....................................................................................................... 21

Chương 2. KỸ THUẬT FIND – UNION TRONG XỬ LÝ ĐỒ THỊ ........ 23

2.1. Kỹ thuật FIND – UNION ................................................................. 23

ii

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

2.2. Những bài toán cơ bản trong lý thuyết đồ thị ................................... 30

2.2.1. Thành phần liên thông..................................................................................... 30

2.2.2. Cây khung............................................................................................................. 33

2.2.3. Cây khung cực tiểu............................................................................................ 35

2.2.4. Rừng khung.......................................................................................................... 37

2.2.4. Cầu .......................................................................................................................... 40

2.2.5 Đỉnh khớp............................................................................................................... 46

Chương 3. MỘT SỐ ỨNG DỤNG ............................................................. 49

3.1. Một số ứng dụng ............................................................................... 49

3.2. Bài toán “Giao thông trong ứng phó thiên tai” ......................................... 49

3.3. Hướng giải quyết bài toán................................................................. 51

3.3.1. Phân tích bài toán.......................................................................... 51

3.1.2. Hướng giải quyết bài toán.............................................................................. 51

3.3.3. Demo ...................................................................................................................... 56

KẾT LUẬN................................................................................................. 63

HƯỚNG PHÁT TRIỂN CỦA ĐỀ TÀI ...................................................... 64

TÀI LIỆU THAM KHẢO........................................................................... 65

PHỤ LỤC.................................................................................................... 66

iii

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

DANH MỤC TỪ VIẾT TẮT

Ký hiệu, viết tắt Ý nghĩa tiếng Việt Ý nghĩa tiếng Anh

G Đồ thị Graph

V Đỉnh của đồ thị Vertices

E Cạnh của đồ thị Edges

Deg Bậc của đồ thị Degree

 Thuộc, nếu a  A: Ta nói

a là phần tử con của tập

A

Member, if A is a set and

a is one of the objects of

A, this is denoted a ∈ A

∉ Không thuộc Not member

>; ≥ Lớn hơn; lớn hơn hoặc

bằng

Greater than; is greater

than or equal to

<; ≤ Nhỏ hơn; nhỏ hơn hoặc

bằng

Less than; is less than or

equal to

{, } Tập Set of

∩ Phép giao Intersected with

∪ Phép hợp The union of ... or ...

# Khác Is incomparable to

| | Tập tử của tập Memmer of set

|...| Ma trận Matrix

 Kéo theo if ... then

O() Ô lớn (độ phức tạp tính

toán)

Big O (complexity

theory)

iv

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

DANH MỤC CÁC BẢNG

Bảng 1.1. Biểu diễn ma trận vô hướng không có trọng số bằng ma trận ... 16

Bảng 1.2. Biểu diễn đồ thị có hướng có trọng số bằng ma trận.................. 18

Bảng 1.3. Biểu diễn đồ thị vô hướng có trọng số bằng ma trận ................. 19

Bảng 1.4. Biểu diễn đồ thị không trọng số bằng danh sách cạnh (cung).... 21

Bảng 1.5. Biểu diễn đồ thị có trọng số bằng danh sách cạnh có trọng số .. 21

Bảng 1.6. Biểu diễn đồ thị bằng danh sách kề ............................................ 22

Bảng 2.1. File đồ thị vào G gồm 9 đỉnh, 6 cạnh và kết quả đầu ra............. 23

Bảng 2.2. Đồ thị G gồm 9 đỉnh, 6 cạnh ...................................................... 31

Bảng 2.3. File dữ liệu vào và ra của đồ thị G 9 đỉnh, 12 cạnh.................... 35

Bảng 3.1. Đặt số hiệu cho huyện Bát Xát và các xã ................................... 55

Bảng 3.2. Kết quả chạy chương trình kiểm tra tính liên thông................... 57

Bảng 3.3. Kết quả chạy chương trình cây khung........................................ 59

Bảng 3.4. Khoảng cách từ các xã đến xã Trịnh Tường............................... 60

v

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

DANH MỤC CÁC HÌNH

Hình 1.1. Các mô hình đồ thị........................................................................ 6

Hình 1.2. Đồ thị hữu hạn............................................................................... 6

Hình 1.3. Đơn đồ thị vô hướng 8 đỉnh 7 cạnh .............................................. 7

Hình 1.4. Đơn đồ thị có hướng 8 đỉnh 7 cạnh............................................... 8

Hình 1.5. Đồ thị hỗn hợp............................................................................... 8

Hình 1.6. Đồ thị đầy đủ................................................................................. 9

Hình 1.7. Đồ thị vòng C1, C2, C3................................................................. 10

Hình 1.8. Đồ thị bánh xe W1, W2, W3....................................................... 10

Hình 1.9. Đồ thị lập phương Q1, Q2, Q3.................................................... 10

Hình 1.10. Đồ thị 2 phía K2,3, K3,3, K3,4................................................. 11

Hình 1.11. Đồ thị phẳng K.......................................................................... 12

Hình 1.12. Đồ thị vô hướng ........................................................................ 12

Hình 1.13. Đồ thị có hướng......................................................................... 13

Hình 1.14. Đường đi trên đồ thị.................................................................. 14

Hình 1.15. Đồ thị không liên thông ............................................................ 15

Hình 1.16. Đồ thị vô hướng không có trọng số G ...................................... 16

Hình 1.17. Đồ thị G có hướng, có trọng số................................................. 18

Hình 1.18. Đồ thị vô hướng G có trọng số.................................................. 19

Hình 1.19. Đồ thị vô hướng không có trọng số G ...................................... 20

Hình 1.20. Đồ thị vô hướng có trọng số G.................................................. 21

Hình 1.21. Đồ thị vô hướng không có trọng số và có trọng số................... 22

Hình 2.1. Khởi trị danh sách d[i] ..............Error! Bookmark not defined.5

Hình 2.2. Cập nhật cạnh (1, 2).................................................................... 26

Hình 2.3. Cập nhật cạnh (3, 6).................................................................... 27

Hình 2.4. Cập nhật cạnh (2, 7).................................................................... 27

Hình 2.5. Cập nhật cạnh (3, 8) ................................................................... 27

Hình 2.6. Cập nhật cạnh (5, 9).................................................................... 28

Hình 2.7. Cập nhật cạnh (4, 9).................................................................... 29