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 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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.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 = <V,E>, 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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 = <V,E>, 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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 = <V,E>, 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ó.
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 = <V,E>, 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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 = <V,E>. - 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 = <V,E>.
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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 = <V,E> 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 = <V,E> 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| vV -Trong đồ thị vô hướng, số đỉnh bậc lẻ là một số chẵn. + Cho đồ thị có hướng G = <V,E>. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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=<V,E>. - 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 = <V,E> 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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 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 = <V,E> 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| vV vV + Đồ thị vô hướng G = <V,E> đượ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ó.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. 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.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com 12 (u, v) tương ứng với một cạnh của đồ thị. 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.