Luận văn Thạc sĩ Khoa học máy tính: Bài toán tìm bộ ghép cực đại trên đồ thị, ứng dụng giải một số bài toán trong thực tế

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:80

Thêm vào BST

Báo xấu

30
lượt xem 5
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn được bố cục thành 3 chương: Chương 1 - Cơ sở về lý thuyết đồ thị và độ phức tạp thuật toán; Chương 2 - Bài toán tìm bộ ghép cực đại trên đồ thị và các thuật toán; Chương 3 - Một số bài toán ứng dụng trong thực tế. Để hiểu rõ hơn mời các bạn cùng tham khảo nội dung chi tiết của luận văn này.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Bài toán tìm bộ ghép cực đại trên đồ thị, ứng dụng giải một số bài toán trong thực tế

i ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG VŨ MINH TIỆP BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ, ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN TRONG THỰC TẾ LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
ii ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN & TRUYỀN THÔNG VŨ MINH TIỆP BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ, ỨNG DỤNG GIẢI MỘT SỐ BÀI TOÁN TRONG THỰC TẾ Chuyên ngành: Khoa học máy tính Mã số: 60 48 01 LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC: TS. Trương Hà Hải Thái Nguyên - 2015 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
iii LỜI CAM ĐOAN Em xin cam đoan: Luận văn tha ̣c si ̃ Khoa học máy tính “ Bài toán tìm bộ ghép cực đại trên đồ thị, ứng dụng giải một số bài toán trong thực tế” nà y là công trình nghiên cứu thực sự của cá nhân em, được thực hiện trên cơ sở nghiên cứu lý thuyết và dưới sự hướng dẫn khoa học của Tiến sĩ Trương Hà Hải, Trường Đại học Công nghệ Thông tin và Truyền thông. Em xin chiụ trách nhiê ̣m về lời cam đoan này. Thái Nguyên, ngày tháng năm 2015 Tác giả Vũ Minh Tiệp Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
iv LỜI CẢM ƠN Để hoàn thành luận văn, em xin chân thành cảm ơn Trường Đại học Công nghệ Thông tin và Truyền thông, Phòng Đào tạo, các thầy, cô giáo giảng dạy lớp cao học Khoa học máy tính K12E đã quan tâm, tạo điều kiện thuận lợi, tận tình giảng dạy và giúp đỡ em trong thời gian theo học tại trường. Đặc biệt, em xin bày tỏ lòng biết ơn sâu sắc đến TS. Trương Hà Hải, người đã dành nhiều thời gian, tâm huyết hướng dẫn em trong suốt quá trình nghiên cứu và hoàn thành luận văn. Em cũng xin cảm ơn các cán bộ, giảng viên đồng nghiệp ở Trường Trung Cấp Kỹ Thuật Vĩnh Phúc đã tạo điều kiện về thời gian để em có thể học tập và hoàn thành luận văn. Mă ̣c dù đã cố gắ ng hế t sức hoàn thiê ̣n luâ ̣n văn, tuy nhiên chắ c chắ n vẫn còn nhiều thiế u sót, rấ t mong sự góp ý quý báu của quý thầ y cô và các ba ̣n. Xin trân trọng cảm ơn. Thái Nguyên, ngày tháng năm 2015 Tác giả Vũ Minh Tiệp Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
v MỤC LỤC Đặt vấn đề ............................................................................................................... 1 CHƯƠNG 1. CƠ SỞ LÝ THUYẾT VỀ ĐỒ THỊ VÀ ĐỘ PHỨC TẠP THUẬT TOÁN ..................................................................................................................... 4 1.1 CÁC KHÁI NIỆM CƠ BẢN ............................................................................. 4 1.1.1 Khái niệm đồ thị ............................................................................................ 4 1.1.2 Các loại đồ thị................................................................................................. 5 1.1.3 Biểu diễn đồ thị ............................................................................................ 11 1.2 ĐỘ PHỨC TẠP TÍNH TOÁN VÀ TÍNH HIỆU QUẢ CỦA THUẬT TOÁN .. 16 1.2.1 Định nghĩa thuật toán ................................................................................... 16 1.2.2 Phân tích độ phức tạp của thuật toán ............................................................ 17 1.2.3 Tối ưu thuật toán........................................................................................... 18 1.3 MỘT SỐ THUẬT TOÁN TÌM KIẾM TRÊN ĐỒ THỊ .................................... 19 1.3.1 Thuật toán tìm kiếm theo chiều sâu (DEPTH FIRST SEARCH) ................... 19 1.3.2 Thuật toán tìm kiếm theo chiều rộng (BREADTH FIRST SEARCH) ........... 21 CHƯƠNG 2. BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ VÀ CÁC THUẬT TOÁN ..................................................................................................... 24 2.1 ĐỒ THỊ HAI PHÍA ......................................................................................... 24 2.1.1 Định nghĩa .................................................................................................... 24 2.1.2 Các bài toán trên đồ thị hai phía .................................................................... 26 2.2 BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ HAI PHÍA................. 26 2.2.1 Bài toán ghép đôi không trọng và các khái niệm ........................................... 26 2.2.2 Thuật toán đường mở ................................................................................... 28 2.2.3 Độ phức tạp của thuật toán............................................................................ 29 2.3 BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI VỚI TỔNG TRỌNG SỐ CỰC ĐẠI HOẶC CỰC TIỂU TRÊN ĐỒ THỊ HAI PHÍA ..................................................... 29 2.3.1 Bài toán phân công ....................................................................................... 29 2.3.2 Thuật toán tìm cặp ghép với tổng trọng số trên các cạnh là lớn nhất hoặc nhỏ nhất ....................................................................................................................... 30 2.3.3 Thuật toán Hung-ga-ri .................................................................................. 33 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
vi 2.3.4 Phương pháp đối ngẫu Kuhn-Munkres .......................................................... 37 2.3.5 Đánh giá độ phức tạp và cải tiến thuật toán ................................................... 39 2.4 BÀI TOÁN TÌM BỘ GHÉP CỰC ĐẠI TRÊN ĐỒ THỊ TỔNG QUÁT ........... 42 2.4.1 Các khái niệm ............................................................................................... 42 2.4.2 Thuật toán Edmonds (1965) .......................................................................... 44 2.4.3 Thuật toán Lawler (1973) ............................................................................. 46 CHƯƠNG 3. MỘT SỐ BÀI TOÁN ỨNG DỤNG TRONG THỰC TẾ ................. 50 3.1 BÀI TOÁN ĐIỀU HÀNH TAXI ..................................................................... 50 3.1.1 Phát biểu bài toán ......................................................................................... 50 3.1.2 Phân tích bài toán và xây dựng thuật toán ..................................................... 50 3.2 BÀI TOÁN XẾP LỚP HỌC THEO TÍN CHỈ .................................................. 60 3.2.1 Mô hình đào tạo theo học chế tín chỉ............................................................. 60 3.2.2 Phát biểu bài toán ......................................................................................... 61 3.2.3 Phân tích bài toán và xây dựng thuật toán ..................................................... 62 TÀI LIỆU THAM KHẢO ..................................................................................... 73 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
vii DANH MỤC CÁC HÌ NH VẼ Hình 1: Ví dụ về mô hình đồ thị ..................................................................... 4 Hình 2: Đơn đồ thị vô hướng và không phải đơn đồ thị vô hướng .................. 5 Hình 3: Đa đồ thị vô hướng ............................................................................ 6 Hình 4: Đơn đồ thị có hướng và không phải đơn đồ thị có hướng .................. 7 Hình 5: Đa đồ thị có hướng ............................................................................ 8 Hình 6: Đơn đồ thị vô hướng.......................................................................... 9 Hình 7: Đồ thị có hướng ............................................................................... 10 Hình 8: Ví dụ biểu diễn đồ thị danh sách cạnh ............................................. 12 Hình 9: Ví dụ biểu diễn đồ thị danh sách liền kề .......................................... 13 Hình 10: Ví dụ biểu diễn đồ thị ma trận kề ................................................... 14 Hình 11: Ví dụ biểu diễn đồ thị ma trận liên thuộc ....................................... 16 Hình 12: Quá trình tìm kiếm theo chiều sâu ................................................. 20 Hình 13: Cây BFS ........................................................................................ 21 Hình 14: Quá trình tìm kiếm theo chiều rộng ............................................... 23 Hình 15: Ví dụ về đồ thị hai phía và không phải là đồ thị hai phía ............... 24 Hình 16: Đồ thị hai phía ............................................................................... 28 Hình 17: Ví dụ bài toán tìm bộ ghép cực đại trên đồ thị ............................... 43 Hình 18: Phép chập Blossom........................................................................ 45 Hình 19: Nở Blossom để dò đường xuyên qua Blossom ............................... 46 Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
1 Đặt vấn đề Ngày nay việc giải quyết các bài toán lớn cho hệ thống đòi hỏi sự hợp tác chặt chẽ giữa các chuyên gia trong các lĩnh vực chuyên môn, như các chuyên gia Toán, Toán ứng dụng và các chuyên gia Tin học, kỹ sư lập trình. Việc thiết lập được một mô hình hợp lý, phản ánh được bản chất của bài toán thực tế đồng thời khả thi về phương diện tính toán luôn là điều đáng được quan tâm. Đặc biệt trong các chuyên ngành liên quan thì toán học là chuyên ngành rất được quan tâm, một trong số đó là Lý thuyết đồ thị. Đồ thị biểu diễn được rất nhiều cấu trúc, nhiều bài toán thực tế có thể được biểu diễn bằng đồ thị. Ví dụ, cấu trúc liên kết của một website có thể được biểu diễn bằng một đồ thị có hướng như sau: các đỉnh là các trang web hiện có tại website, tồn tại một cạnh có hướng nối từ trang A tới trang B khi và chỉ khi A có chứa 1 liên kết tới B. Do vậy, sự phát triển của các thuật toán xử lý đồ thị là một trong các mối quan tâm chính của khoa học máy tính. Mặc dù Lý thuyết đồ thị đã được khoa học phát triển từ rất lâu nhưng lại có nhiều ứng dụng hiện đại, đặc biệt là các thuật toán trên đồ thị đã có nhiều ứng dụng trong nhiều lĩnh vực khác nhau như: Mạng máy tính, Lý thuyết mã, Tối ưu hoá, Kinh tế học ...Những ý tưởng cơ bản của lý thuyết đồ thị được nhà toán học Thụy sĩ Leonhard Euler đưa ra từ thế kỷ 18. Ông đã dùng lý thuyết đồ thị để giải quyết bài toán cầu Konigsberg nổi tiếng. Đồ thị cũng được dùng để giải nhiều bài toán thuộc những lĩnh vực rất khác nhau như: người ta có thể dùng đồ thị để biểu diễn sự cạnh tranh của các loài trong môi trường sinh thái, dùng đồ thị biểu diễn ai có ảnh hưởng đến ai trong một tổ chức nào đó và cũng có thể dùng đồ thị để giải các bài toán như bài toán tính số các tổ hợp khác nhau của các chuyến xe giữa hai thành phố trong một mạng giao thông, bài toán đi tham quan tất cả các phố của một Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
2 thành phố sao cho mỗi phố đi qua đúng một lần, hay bài toán tìm số màu cần thiết để tô các vùng khác nhau của một bản đồ,...Đồ thị với các trọng số được gán cho các cạnh của nó có thể dùng để giải các bài toán như bài toán tìm đường đi ngắn nhất giữa hai thành phố trong một mạng giao thông, bài toán phân công lao động sao cho tổng lợi nhuận thu được là lớn nhất. Đặc biệt, nhiều bài toán trong thực tế sử dụng mô hình đồ thị và các thuật toán trên đồ thị được giải quyết rất hiệu quả như: bài toán điều hành taxi, bài toán xếp lớp học theo tín chỉ có thể đưa về mô hình bài toán tìm bộ ghép cực đại trên đồ thị và sử dụng các thuật toán tương ứng. Chính vì đồ thị có thể được sử dụng để giải quyết nhiều bài toán thuộc nhiều lĩnh vực khác nhau một cách dễ dàng và phổ biến như vậy nên đồ thị giữ một vai trò hết sức quan trọng trong cuộc sống, đặc biệt là trong lĩnh vực công nghệ thông tin, dựa vào đồ thị và các thuật toán trên đồ thị người ta có thể xây dựng nên các phần mềm hữu ích giải các bài toán thực tế một cách nhanh chóng và tối ưu. Nhận thấy tính thiết thực của vấn đề này và được sự gợi ý của giảng viên hướng dẫn, tôi đã chọn nội dung nghiên cứu về “Bài toán tìm bộ ghép cực đại trên đồ thị, ứng dụng giải một số bài toán trong thực tế.” làm đề tài cho luận văn tốt nghiệp của mình. Luận văn được bố cục thành 3 chương: Chương 1. Cơ sở về lý thuyết đồ thị và độ phức tạp thuật toán: Chương này trình bày các khái niệm cơ bản về Lý thuyết đồ thị và độ phức tạp thuật toán Chương 2. Bài toán tìm bộ ghép cực đại trên đồ thị và các thuật toán: Chương này phát biểu các dạng bài toán tìm bộ ghép cực đại trên đồ thị, trình bày các thuật toán và đánh giá độ phức tạp của các thuật toán Chương 3. Một số bài toán ứng dụng trong thực tế: Tìm hiểu một số bài toán ứng dụng trong thực tế: Bài toán điều hành taxi, bài toán xếp lớp học theo tín Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
3 chỉ,…, xây dựng chương trình thử nghiệm giải các bài toán này ứng dụng bài toán xếp lớp học theo tín chỉ tại trường Trung cấp Kỹ thuật Vĩnh Phúc. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
4 CHƯƠNG 1 CƠ SỞ LÝ THUYẾT VỀ ĐỒ THỊ VÀ ĐỘ PHỨC TẠP THUẬT TOÁN 1.1 CÁC KHÁI NIỆM CƠ BẢN Phần này được tham khảo trong các tài liệu [2], [3], [5], [9] 1.1.1 Khái niệm đồ thị Đồ thị là một cấu trúc rời rạc gồm các đỉnh và các cạnh nối các đỉnh đó. Đồ thị được ký hiệu là G = (V, E), trong đó V là tập đỉnh và E là tập cạnh. Có thể coi E là tập các cặp(u,v) với u và v là hai đỉnh của V. Một số hình ảnh của đồ thị. Sơ đồ giao thông Mạng máy tính Hình 1: Ví dụ về mô hình đồ thị Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
5 1.1.2 Các loại đồ thị Có thể phân loại đồ thị theo đặc tính và số lượng của tập các cạnh E: Cho đồ thị G = (V, E). Định nghĩa 1: Một đơn đồ thị vô hướng là một bộ G = , trong đó: - V ≠  là tập hợp hữu hạn gồm các đỉnh của đồ thị. - E là tập hợp các cặp không có thứ tự gồm hai phần tử khác nhau của V gọi là các cạnh. Như vậy, theo định nghĩa trên, trong một đơn đồ thị không thể có các cặp cạnh nối cùng một cặp đỉnh (do E là tập hợp nên không thể có 2 cặp trùng nhau), các cạnh đều không phân biệt thứ tự nên cạnh [u,v] và cạnh [v,u] đều được coi là một cạnh duy nhất, điều này phù hợp với việc biểu diễn các con đường 2 chiều, và hiển nhiên là không có cặp [u,u] nào đó trong E. Ví dụ a) Đơn đồ thị vô hướng b) Không phải đơn đồ c) Không phải đơn đồ thị vô thị vô hướng do có các hướng do có cạnh nối một cặp cạnh nối cùng một đỉnh với chính nó. cặp đỉnh Hình 2: Đơn đồ thị vô hướng và không phải đơn đồ thị vô hướng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
6 Tuy nhiên, trên thực tế, cũng có thể trong một hệ thống giao thông vẫn tồn tại nhiều con đường đi nối cùng hai địa điểm, hoặc cũng có thể có một con đường để đi từ một địa điểm nào đó rồi lại quay về chính nó (đây có thể là một con đường nội bộ của một trung tâm mua sắm, …). Khi đó, tính chất của đơn đồ thị vô hướng như định nghĩa trên không cho phép nó biểu diễn được hệ thống giao thông trong trường hợp này. Muốn vậy, ta phải dùng một loại đồ thị tổng quát hơn, đó là: đa đồ thị vô hướng. Định nghĩa 2: Đa đồ thị vô hướng là một bộ G = , trong đó - V ≠  là tập hợp hữu hạn gồm các đỉnh của đồ thị. - E là một họ các cặp không có thứ tự của V gọi là các cạnh. Lưu ý: - Khi ta nói E là một họ nghĩa là nó có thể có những cặp trùng nhau (khác với khái niệm tập hợp). - Các cạnh nối cùng một cặp đỉnh được gọi là các cạnh song song. - Các cạnh nối từ một đỉnh với chính nó được gọi là khuyên. Ví dụ e2 e1 e a) Đa đồ thị vô hướng: e1 và e2 là b) Đa đồ thị vô hướng: e là khuyên các cạnh song song Hình 3: Đa đồ thị vô hướng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
7 Điểm chung của hai loại đồ thị đã được định nghĩa ở trên là tính chất vô hướng (hai chiều) của các cạnh. Trong thực tế, cũng có khi ta phải chú trọng đến tính có hướng của các cạnh nối này (chẳng hạn như biểu diễn các con đường một chiều). Từ đó, ta có thêm loại đồ thị: Đơn đồ thị có hướng và đa đồ thị có hướng. Về cơ bản, hai loại này cũng tương tự như hai loại mà ta định nghĩa ở trên, chỉ thêm sự khác biệt là tính chất có thứ tự của các cạnh. Định nghĩa 3: Đơn đồ thị có hướng là một bộ G = , trong đó: - V ≠  là tập hợp hữu hạn gồm các đỉnh của đồ thị. - E là tập hợp các cặp có thứ tự gồm hai phần tử khác nhau của V gọi là các cung. Ví dụ a) Đơn đồ thị có b) Không phải đơn đồ thị c) Không phải đơn đồ thị có hướng có hướng do có các cặp hướng do có cung nối một cung nối cùng một cặp đỉnh với chính nó. đỉnh. Hình 4: Đơn đồ thị có hướng và không phải đơn đồ thị có hướng Định nghĩa 4 : Đa đồ thị có hướng là một bộ G = , trong đó - V ≠  là tập hợp hữu hạn gồm các đỉnh của đồ thị. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
8 - E là một họ các cặp có thứ tự của V gọi là các cung. Các cung nối cùng một cặp đỉnh được gọi là các cung song song. Ví dụ e2 e1 e a) Đa đồ thị có hướng: e1 và e2 là các b) Đa đồ thị có hướng: e là cung song song. khuyên Hình 5: Đa đồ thị có hướng Định nghĩa 5: Một giả đồ thị G = (V, E) gồm một tập các đỉnh V, một tập các cạnh E và một hàm f từ E tới {{u,v} | u, v  V }. Một cạnh là một khuyên nếu f(e) = {u} với một đỉnh u nào đó. Một số thuật ngữ cơ bản + Cho đồ thị vô hướng G = . - Hai đỉnh u và v của đồ thị được gọi là kề nhau nếu (u,v) là một cạnh của đồ thị. - Nếu e = (u,v) là cạnh của đồ thị thì ta nói cạnh này là liên thuộc với hai đỉnh u và v. Cạnh được nói là nối đỉnh u và v. Đỉnh u và v được gọi là đỉnh đầu của cạnh e. + Cho đồ thị vô hướng G = . Bậc của đỉnh v trong đồ thị, ký hiệu là Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
9 deg(v), là số cạnh liên thuộc với nó. Đỉnh có bậc 0 được gọi là đỉnh cô lập,đỉnh có bậc 1 gọi là đỉnh treo. Ví dụ Cho đồ thị vô hướng G = sau: 1 2 3 4 5 6 Hình 6: Đơn đồ thị vô hướng - V = {1, 2, 3, 4, 5, 6} - E = {(1,2), (2,3), (1,4), (1,5), (2,5), (4,5), (2,4)} - Bậc của các đỉnh: - deg(1) = 3 deg(2) = 4 deg(3) = 1 - deg(4) = 3 deg(5) = 3 deg(6) = 0 - Đỉnh 3 là đỉnh treo - Đỉnh 6 là đỉnh cô lập + Cho G = là đồ thị vô hướng. Khi đó ta có tổng số bậc của các đỉnh của đồ thị sẽ bằng hai lần số cạnh của nó. Nói cách khác, ta có:  deg  v  2|E| vV -Trong đồ thị vô hướng, số đỉnh bậc lẻ là một số chẵn. + Cho đồ thị có hướng G = . Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
10 - Hai đỉnh u và v của đồ thị được gọi là kề nhau nếu (u,v) là một cung của đồ thị. - Nếu e=(u,v) là cung của đồ thị thì ta nói cung này đi ra khỏi đỉnh u và đi vào đỉnh v. Đỉnh u được gọi là đỉnh đầu của cung e và đỉnh v được gọi là đỉnh cuối của cung e. + Cho đồ thị có hướng G=. - Bán bậc ra của đỉnh v trong đồ thị, ký hiệu là deg+(v), là số cạnh đi ra khỏi v. - Bán bậc vào của đỉnh v trong đồ thị, ký hiệu là deg- (v), là số cạnh vào v. Ví dụ Xét đồ thị có hướng G = sau: 1 2 3 4 5 6 Hình 7: Đồ thị có hướng - V = {1, 2, 3, 4, 5, 6} - E = {(1,2), (2,3), (1,4), (5,1), (5,2), (2,6), (6,3), (4,5), (6,5), (3,4)} - Bậc của các đỉnh: Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
11 - Bán bậc ra: deg+(1)=2 deg+(2)=2 deg+(3)=1 deg+(4)=1 deg+(5)=2 deg+(6)=2 - Bán bậc vào: deg-(1)=1 deg-(2)=2 deg-(3)=2 deg-(4)=2 deg-(1)=2 deg-(1)=1 Tương tự như đồ thị vô hướng, đối với đồ thị có hướng ta cũng có kết quả gần tương tự về bậc của các đỉnh của đồ thị. + Cho G = là đồ thị có hướng. Tổng bán bậc ra của các đỉnh bằng tổng bán bậc vào của các đỉnh và bằng số cạnh của đồ thị.  deg  v    deg  v   |E| vV  vV  + Đồ thị vô hướng G = được gọi là liên thông nếu luôn tìm được đường đi giữa hai đỉnh bất kỳ của nó. 1.1.3 Biểu diễn đồ thị Lý thuyết đồ thị được ứng dụng trong rất nhiều lĩnh vực khác nhau. Để sử dụng được đồ thị hiệu quả và nhanh chóng hơn, chúng ta phải biểu diễn và xử lý được đồ thị với máy tính. Cách biểu diễn thông thường bằng hình vẽ và mô tả tập hợp sẽ không phù hợp với cách thức lưu trữ dữ liệu và xử lý trên máy tính. Chúng ta phải tìm một cấu trúc dữ liệu thích hợp để biểu diễn đồ thị trên máy tính. Có nhiều phương pháp khác nhau để biểu diễn đồ thị trên máy tính. Sau đây chúng ta sẽ lần lượt tìm hiểu một số phương pháp thông dụng. a. Danh sách cạnh Trong trường hợp đồ thị có n đỉnh, m cạnh, ta có thể biểu diễn đồ thị dưới dạng danh sách cạnh, trong cách biểu diễn này, người ta liệt kê tất cả các cạnh của đồ thị trong một danh sách, mỗi phần tử của danh sách là một cặp Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
12 (u, v) tương ứng với một cạnh của đồ thị. (Trong trường hợp đồ thị có hướng thì mỗi cặp (u, v) tương ứng với một cung, u là đỉnh đầu và v là đỉnh cuối của cung). Danh sách được lưu trong bộ nhớ dưới dạng mảng hoặc danh sách móc nối. Ví dụ với đồ thị dưới đây: 1 5 2 4 3 Cài đặt trên mảng: 1 2 3 4 5 (1,3) (2,4) (3,5) (4,1) (5,2) Cài đặt trên danh sách móc nối: 1 3 2 4 3 5 4 1 5 2 nil Hình 8: Ví dụ biểu diễn đồ thị danh sách cạnh Ưu điểm của danh sách cạnh: • Trong trường hợp đồ thị thưa (có số cạnh tương đối nhỏ: chẳng hạn m < 6n), cách biểu diễn bằng danh sách cạnh sẽ tiết kiệm được không gian lưu trữ, bởi nó chỉ cần 2m ô nhớ để lưu danh sách cạnh. • Trong một số trường hợp, ta phải xét tất cả các cạnh của đồ thị thì Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
13 cài đặt trên danh sách cạnh làm cho việc duyệt các cạnh dễ dàng hơn. (Thuật toán Kruskal chẳng hạn) Nhược điểm của danh sách cạnh: • Nhược điểm cơ bản của danh sách cạnh là khi ta cần duyệt tất cả các đỉnh kề với đỉnh v nào đó của đồ thị, thì chẳng có cách nào khác là phải duyệt tất cả các cạnh, lọc ra những cạnh có chứa đỉnh v và xét đỉnh còn lại. Điều đó khá tốn thời gian trong trường hợp đồ thị dày (nhiều cạnh). b. Danh sách liền kề Sử dụng danh sách liền kề để biểu diễn đồ thị không có cạnh bội. Danh sách này chỉ rõ các đỉnh nối với mỗi đỉnh của đồ thị. 1 Đỉnh Đỉnh liền kề 5 1 2, 3,4, 5 2 1,3, 4, 5 2 3 1,2,4 4 4 1,2,3 3 5 1,2 Hình 9: Ví dụ biểu diễn đồ thị danh sách liền kề Ưu điểm của danh sách kề: • Đối với danh sách kề, việc duyệt tất cả các đỉnh kề với một đỉnh v cho trước là hết sức dễ dàng, cái tên "danh sách kề" đã cho thấy rõ điều này. Việc duyệt tất cả các cạnh cũng đơn giản vì một cạnh thực ra là nối một đỉnh với một đỉnh khác kề nó. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn