CHƯƠNG 1 TỎNG QUAN VỀ LÝ THUYÉT ĐÒ THỊ VÀ SƠ ĐÒ MẠNG 1. Tổng quan về lý thuyết đồ thị 1.1 Khái niệm và định nghĩa Đồ thị G là một cặp (V,E), trong đó V là tập đỉnh và E = {(x,y) | x, yeV} là tập cung (cạnh). Về thực chất, đồ thị là một tập hợp các đối tượng được biêu diễn bằng các đỉnh và giữa các đỉnh có một quan hệ biểu diễn bằng các cạnh. Đồ thị thường được ký hiệu là G hay G(V,E).1 biểu điễn một đồ thị G;(V,E) trong đó: Tập đỉnh V = {1,2,3,4,5}; Tập cạnh E = {a, b, c, d, e, g} với a = (1,2), b = (2, 3), c = 4, 4), d= (4, 5), e= (1, 3), g= (1, 5) Đường di trong dé thị: Một đường đi œ trong đồ thi G(V,E) là một day các đỉnh và cạnh xen kẽ : Vo bị Vị bạ.
Vận bị Vị bjs Visi. Vạ Dn Vụ sao cho V i (0<i<n-l), vị là điểm đầu còn Viv là điểm cuối của cạnh bj+1, Vo được gọi là đỉnh đầu, vạ được gọi là đỉnh cuối của đường đi œ và nói œ xuất phát từ đỉnh Vo đến đỉnh Vụ. Ví dụ một đường đi trong đồ thị hình 1.1 như sau: @-—®-—@®-—#¬>@œ Hình 1.2 Đường đi œ Ta có: 1a2b3elg5, là một đường đi trong dé thị G,(V,E) trong hình 1.1 xuất phát từ vp = 1 đến vạ = 5. Chu trình: Là một đường đi khép kin, tức là đỉnh cuối vạ = vo của đường đi.
Một chu trình đơn là chu trình không có đỉnh lặp lại. Đồ thị G gọi là dé thj liên thông nêu với cặp đỉnh (u, v) bất kỳ đều tồn tại một đường đi nối hai đỉnh này. Đồ thị G không liên thông thì mỗi đồ thị con liên thông cực đại của nó được gọi là một thành phần liên thông. Đồ thị có trọng số: Ứng với mỗi cạnh ta gán cho một số (nguyên hay thực) không âm w mang thông tin nào đó có liên quan đến cạnh gọi là trọng số của cạnh đó.
Dé thị mà mọi cạnh đều có trọng số gọi là đồ thị có trong số (Weitghted Graph). Trọng số có thé là quãng đường trên bản đồ giao thông, cước phí vận tải trên đường đó, thông lượng trên mạng thông tin, .Trong đồ thị có trọng số, độ dài đường đi được định nghĩa là tổng trọng số của các cạnh trên đường đi đó. Dé thị có hướng: Là đồ thị mà mọi cạnh của nó đều xác định thứ tự các đỉnh kể (khi đó các cạnh còn được gọi là các cung).3 biểu diễn dé thị có hướng.3 Dé thị có hướng (a) Không có trọng số; (b) Có trọng số Vi sơ đồ mạng được trình bay ở các chương sau thường được biểu diễn bởi các đồ thị có hướng, có trọng số nên chúng tôi tập trung trình bày tổng quan một sé vấn dé liên quan đến đồ thị có hướng, có trọng số. Sau đây, khi nhắc đến các đồ thị, nếu không có chú ý gì thêm, ta hiểu là các đồ thị có hướng.
Khi nói đến cung, ta hiểu đó là cung trong đồ thị có hướng.2 Biểu diễn đồ thị Để có thể giải các bài toán liên quan đến đồ thị trên máy tính, chúng ta cần phải có các phương pháp dé biểu diễn đồ thị. Các phương pháp biểu diễn đồ thị hay chính là các cầu trúc dữ liệu mô tả đồ thị thường được sử dụng là: - Biểu diễn bằng ma trận kè - _ Biểu diễn bằng danh sách kề -_ Biểu diễn bằng danh sách cung (cạnh) Biểu diễn bằng ma trận kè Để biểu diễn đồ thị có hướng, có trọng số G với n đỉnh ta sử dụng một ma trận A cỡ nxn với các phân tử (aj) của ma trận được xác định như sau: w, nếu có cung (i, j) với trọng số wy a= œ nếu không có cung (i,j) Ví dụ: Ma trận ké biểu diễn đồ thị Ga(V,E) với 5 đỉnh trong Hình 1.3 như Sau : > a88 8nœy 8œ 8BN 8œ Phương pháp biéu diễn đồ thi bằng ma trận kể có ưu nhược điểm sau: Ưu điểm: Các phép toán cơ sở của đồ thị đều cho phép dễ dàng, thuận tiện cho việc truy nhập các cung, các đỉnh kề. Cho cặp đỉnh (i, j) bat kỳ thì xác định được ngay có cung (i, j) hay không và trong số là bao nhiêu. Nhược điểm: Sẽ tôn nhiều không gian lưu trữ nếu đồ thị có ít cung mà nhiều đỉnh, tức là ma trận kể sẽ thưa, có nhiều phần tử bằng œ, khi đó tuy có ít dit liệu cần lưu trữ nhưng ta vẫn phải lưu cả một ma trận kích thước lớn.
Biểu diễn đồ thị bằng danh sách kè Để biểu diễn đồ thị bằng danh sách kể có thé thay n dòng của ma tran bằng n danh sách móc nối. Nút đầu của mỗi danh sách là đỉnh được xét, theo sau là các đỉnh kể với nó và trọng số của cung tương ứng. Ví dụ: Danh sách kể biểu diễn đồ thị G3(V,E) với 5 đỉnh trong Hình 1.3 như Sau: 1| L {2 [8 >[4 [6] >[ NIL 2] LÌ {4 [2 | >[ NIL 3] [ fifa] >| NIL 4.[Ree bleibt} s[ ] {2 [2], } 1w Trong mỗi nút đầu của mỗi danh sách lưu chỉ số của mỗi đỉnh của đồ thị. Các nút tiếp theo trong danh sách chứa chỉ số của đỉnh kề với đỉnh đó và trong số của cung tương ứng.
Số nút trong mỗi danh sách bằng số cung đi ra từ đỉnh lưu trong nút đầu của danh sách. Cấu trúc mỗi nút của danh sách có thê được khai báo như sau: struct Node { int Index; float weight Node *next; diễn một đồ thị có n đỉnh là một mảng các danh sách liên kết G: Node G[n]; Cách biểu diễn đồ thị dùng cấu trúc danh sách kể có ưu điểm là tiết kiệm không gian lưu trữ và cho phép dễ đàng truy cập mọi đỉnh kề của một đỉnh đang xét. Tuy nhiên danh sách kể không thuận tiện cho việc truy cập các cung. Biểu diễn đồ thị bằng danh sách cung Trong trường hợp đồ thị thưa có n đỉnh, m cạnh (đồ thị có số cung thoả mãn bất đẳng thức: m<6n), người ta thường biểu diễn đồ thị dưới dang danh sách cung.
Trong cách này, ta sẽ lưu trữ danh sách tất cả các cung của đồ thị có hướng. Khi đó dé lưu trữ đồ thị ta cần 2m don vị nhớ. Nhược điểm của cách biéu diễn nay là để xác định những đỉnh nào kể với một đỉnh cho trước, ta phải làm m phép so sánh khi đuyệt qua tất cả các cạnh của đồ thị. Ví dụ: Danh sách cung của dé thị G;(V, E) 19 cung Đầu Cuối | Trọng số 1 1 2 8 2 1 4 6 3 2 4 2 4 3 1 4 5 4 3 5 6 4 5 3 7 5 3 2 Dé trả lời câu hỏi có hay không cung di từ i đến j, trường hợp xấu nhất ta phải duyệt m bước (với m là tổng số cung có trong đồ thị).3 Các thuật toán tim đường di trong đồ thị 1.1 Mé đầu Trong thực tế, nhiều bài toán có thê mô hình bằng đồ thị có trọng số.
Ví dụ ta cần mô hình một hệ thống đường hàng không. Mỗi thành phố được biểu diễn bằng một đỉnh, mỗi chuyến bay là một cạnh nối 2 đỉnh tương ứng. Nếu trong bài toán đang xét ta cần tính đến khoảng cách giữa các thành phó thì ta cần gán cho mỗi cạnh của đồ thị cơ sở trên khoảng cách giữa các thành phố tương ứng. Nếu ta quan tâm đến thời gian của mỗi chuyến bay thì ta sẽ gán các thời lượng này cho mỗi cạnh của đồ thị cơ sở.
Ví ụ đồ thị biểu diễn khoảng cách giữa một số tỉnh/thành phó của Việt Nam: Trọng số ghi trên mỗi cạnh là khoảng cách tính bằng km Hà Tâ Thanh Hoá Deng Mav Vinh Long s e XN11 © 153 100/⁄ vI 5 "4 x Z 1710 Ha NộiÌ yy 56 \ in e HP ` pug Hồ Chí Minh ⁄ Long An 790 658 e ` A052 /250 Nam Dinh \ >⁄ / Huế Khánh Hoà Hình 1.4 Biểu đồ khoảng cách Bài toán đặt ra là tim đường đi ngắn nhất từ thành phố này đến thành phố khác. Hay nói theo ngôn ngữ của lý thuyết đồ thị: Chúng ta gọi chung là Bài oán tìm đường đi ngắn nhất trên đồ thị (ngắn gọn là Bài toán tim đường đi ngắn nhấU), tìm đường đi có tổng trọng số nhỏ nhất từ đỉnh này đến một đỉnh khác của dé thị. Một thuật toán được áp dụng tương đối phổ biến dé giải bài toán tìm đường đi do Dijkstra đề xuất năm 1959 gọi là thuật toán Dijkstra mà chúng tôi sẽ trình bày trong mục 1. Trường hợp riêng của bài toán tìm đường đi khi đồ thị không có chu trình thì thuật toán Dijkstra có thể được cải tiến để độ phức tạp chỉ còn O(n) - với n là số đỉnh của đồ thị, thuật toán này được trình bày trong mục 1.
Thuật toán Dijkstra Xét đồ thị G(V, E) trong hình vẽ Hình 1.5 sau đây: Bài toán đặt ra là: Xuất phát từ đỉnh 1, chúng ta cần tìm đường đi ngắn nhất tới các đỉnh còn lại? Thuật toán Dijkstra giải quyết bài toán trên, được xây dựng trên ý tưởng sau: Cho đỉnh s e V, tìm đường đi ngắn nhất từ s tới mọi đỉnh v e V. Thuật toán thực hiện việc gán nhãn d[v] tạm thời cho mỗi đỉnh v dé lưu đường đi ngắn nhất từ đỉnh s tới v trong mỗi bước, sau đó thực hiện việc giảm giá trị của nhãn đến khi không thể giảm được nữa thì d[v] chính là đường đi ngắn nhất từ s đến đỉnh v. Bước 1: Gan nhãn tạm thời cho mọi đỉnh veV là trong số của cạnh (s, v), ký hiệu là d[v]: d[v] = a[s, v], d[s] = 0. Gọi T là tập chứa các đỉnh được gán nhãn tam thời: T = V\s.
10 Bước 3: Loại đỉnh u ra khỏi T (u đã được gán nhãn có định sau bước 2). Bước 4: Nếu T # ©, lặp lại bước 2, ngược lại, dừng. Thuật toán Dijkstra có thể được trình bày dưới dạng giả mã (pseudo - code) như sau: THUẬT TOÁN: DIJKSTRA Input: Đồ thị (V, E) có hướng, n đỉnh, với ma trận trọng số biểu diễn A = (ajnxn aj> 0 V ij e V; s € V là đỉnh xuất phát. Output: Khoảch cách ngắn nhất từ đỉnh s đến tat cả các đỉnh còn lại là d[v], ve V.
Truoc[v] ghi lại đỉnh đi trước v trong đường đi ngắn nhất từ s đến v.