chương 1 đưa ra các khái niệm cơ bản về lý thuyết đồ thị, các thuật toán cơ bản trên mô hình đồ thị. Các kiến thức được tham khảo trong các tài liệu [1] [2] 1.1 Một số khái niệm cơ bản [1] 1.1 Định nghĩa về đồ thị Đồ thị là một cấu trúc rời rạc bao gồm các đỉnh và các cạnh nối các đỉnh này, các loại đồ thị khác nhau được phân biệt bởi kiểu và số lượng cạnh nối hai đỉnh nào đó của đồ thị. Giả sử V là tập hữu hạn, không rỗng các phần tử nào đó. Bộ G = (V,E) được gọi là đồ thị hữu hạn.
Mỗi phần tử của V gọi là một đỉnh và mỗi phần tử u = (x,y) của E được gọi là một cạnh của đồ thị G = (V,E). Xét một cạnh u của E khi đó tồn tại hai đỉnh x, y của V sao cho u = (x,y), ta nói rằng x nối với y hoặc x và y phụ thuộc u. Nếu cạnh u = (x,y) mà x và y là hai đỉnh phân biệt thì ta nói x, y là hai đỉnh kề nhau. Nếu u = (x,x) thì u là cạnh có hai đỉnh trùng nhau ta gọi đó là một khuyên.
Nếu u = (x,y) mà x, y là cặp đỉnh có phân biệt thứ tự hay có hướng từ x đến y thì u là một cung, khi đó x là gốc còn y là ngọn hoặc x là đỉnh vào, y là đỉnh ra. Khi giữa cặp đỉnh (x,y) có nhiều hơn một cạnh thì ta nói rằng những cạnh cùng cặp đỉnh là những cạnh song song hay là cạnh bội. Trong thực tế ta có thể gặp nhiều vấn đề mà có thể dùng mô hình đồ thị để biểu diễn, như sơ đồ mạng máy tính, sơ đồ mạng lưới giao thông, sơ đồ thi công một công trình. Đơn đồ thị vô hướng G = (V,E) bao gồm V là các tập đỉnh và E là các tậ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.
Đa đồ thị vô hướng G = (V,E) bao gồm V là tập các đỉnh, và E là họ 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. Hai cạnh e1 và e2 được gọi là cạnh lặp nếu chúng cùng tương ứng với một cặp đỉnh. Rõ ràng mỗi đơn đồ thị là đa đồ thị, nhưng không phải đa đồ thị nào cũng là đơn đồ thị, vì trong đa đồ thị có thể có hai (hoặc có nhiều hơn) cạnh nối một cặp đỉnh nào đó. 8 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Định nghĩa 3.
Giả đồ thị vô hướng G = (V,E) bao gồm V là các tập đỉnh, và E là họ các cặp không có thứ tự (không nhất thiết phải khác nhau) của V gọi là các cạnh. Cạnh e được gọi là khuyên nếu nó có dạng e = (u,u). Đơn đồ thị có hướng G = (V,E) bao gồm V là các tập đỉnh và E là 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. Nếu trong mạng có thể có đa kênh thoại một chiều, ta sẽ phải sử dụng đến khái niệm đa đồ thị có hướng: Định nghĩa 5.
Đa đồ thị có hướng G = (V,E) bao gồm V là các tập đỉnh và E là họ 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. Hai cung e1, e2 tương ứng cùng với một cặp đỉnh được gọi là cung lặp. Trong các phần tử tiếp theo chủ yếu chúng ta sẽ làm việc với đơn đồ thị vô hướng và đơn đồ thị có hướng. Vì vậy, để ngắn gọn, ta bỏ qua tính từ đơn khi nhắc đến chúng.2 Các thuật ngữ cơ bản Định nghĩa 6.
Hai đỉnh u và v của đồ thị vô hướng G được gọi là kề nhau nếu (u,v) là cạnh của đồ thị G. Ta gọi bậc của đỉnh v trong đồ thị vô hướng là số cạnh liên thuộc với nó và sẽ ký hiệu là deg(v). Nếu e = (u,v) là cung của đồ thị có hướng G thì ta nói hai đỉnh u và v là kề nhau, và nói cung (u,v) nối đỉnh u với đỉnh v hoặc cũng nói cung này là đi ra khỏi đỉnh u và đi vào đỉnh v. Ta gọi bán bậc ra (bán bậc vào) của đỉnh v trong đồ thị có hướng là số cung của đồ thị đi ra khỏi nó (đi vào nó) và ký hiệu là deg+(v)(deg-(v)).3 Đường đi, chu trình.
Đồ thị liên thông. Đường đi độ dài n từ đỉnh u đến đỉnh v, trong đó n là số nguyên dương, trên đồ thị vô hướng G = (V,E) là dãy x0, x1,…, xn-1, xn trong đó u = x0, v = xn, (xi, xi+1) E, i = 0,1,2,…, n-1. Đường đi nói trên còn có thể biểu diễn dưới dạng dãy các cạnh: (x0,x1), (x1,x2),…, (xn-1,xn). Đỉnh u gọi là đỉnh đầu, còn đỉnh v gọi là đỉnh cuối của đường đi.
Đường đi có đỉnh đầu trùng với đỉnh cuối (tức là u = v) được gọi là chu trình. Đường đi hay chu trình 9 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com được gọi là đơn nếu như không có cạnh nào bị lặp lại. Khái niệm đường đi và chu trình trên đồ thị có hướng được định nghĩa hoàn toàn tương tự như trường hợp đồ thị vô hướng, chỉ khác là ta có chú ý đến hướng trên các cung. Đồ 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ó.
Như vậy hai máy tính bất kỳ trong mạng có thể trao đổi thông tin được với nhau khi và chỉ khi đồ thị tương ứng với mạng này là đồ thị liên thông.2 Một số phƣơng pháp mô tả đồ thị [1][2] Với một biểu đồ nhất định có một số biểu diễn khác nhau. Việc dễ dàng cài đặt các thuật toán trên đồ thị cũng như hiệu quả của thuật toán phụ thuộc vào sự lựa chọn cách biểu diễn đồ thị đúng đắn. Hai cấu trúc được sử dụng phổ biến nhất để biểu diễn một đồ thị (có hướng hay vô hướng) là ma trận kề và danh sách kề.1 Cấu trúc ma trận kề Giả sử G = (V, E) là đơn đồ thị có số đỉnh (ký hiệu |V| là n), không mất tính tổng quát có thể coi các đỉnh được đánh số 1, 2,. Khi đó, ta có thể biểu diễn đồ thị bằng một ma trận vuông A cấp n trong đó A(i,j)=1 nếu cạnh (i,j) là tồn tại và A(i,j)=0 nếu cạnh (i,j) không tồn tại.
Trong trường hợp khi đồ thị có trọng số thì chúng ta có cấu trúc ma trận trọng số là một ma trận vuông A cấp n trong đó A(i,j)=trọng số của cạnh nếu cạnh (i,j) là tồn tại và A(i,j)= nếu cạnh (i,j) không tồn tại (A(i,i)=0 nếu không tồn tại khuyên. Các tính chất của ma trận liền kề: + Với đồ thị vô hướng G, ma trận liền kề tương ứng là ma trận đối xứng. + Nếu G là đồ thị vô hướng và A là ma trận liền kề tương ứng thì ta có Tổng các số trên hàng i = tổng các số trên cột i = Bậc của đỉnh i = deg(i) Ưu điểm của ma trận liền kề: Đơn giản, trực quan, dễ cài đặt. 10 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Nhược điểm của ma trận liền kề: Số cạnh của đồ thị là nhiều hay ít, ma trận liền kề luôn đòi hỏi n2 ô để lưu các phần tử ma trận gây lãng phí bộ nhớ dẫn tới không thể biểu diễn được đồ thị với số đỉnh lớn.1: (a) Một đồ thị vô hướng; (b) Biểu diễn ma trận kề; (c) Biểu diễn danh sách kề.2: (a) Một đồ thị có hướng; (b) Ma trận kề: (c) Biểu diễn danh sách kề.
11 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.3: (a) Đồ thị trọng số ; (b) Ma trận kề: (c) Danh sách kề.2 Cấu trúc danh sách kề Để mô tả đồ thị G, chúng ta có thể sử dụng cấu trúc danh sách theo tư tưởng: một đỉnh x bất kì sẽ lưu trữ các đỉnh kề với x bằng một danh sách tuyến tính. Các tính chất của danh sách kề: + Với cấu trúc danh sách kề thì số phần tử trong danh sách kề với mỗi đỉnh chính bằng bậc của đỉnh đó + Thường sử dụng cấu trúc con trỏ để mô tả 1.3 Một số thuật toán trên đồ thị [1][2] 1.1 Các thuật toán duyệt đồ thị Thuật toán duyệt theo chiều sâu DFS Tư tưởng của thuật toán: theo tư tưởng đệ quy tức là mọi đỉnh x kề với S sẽ đến được từ S, với mỗi đỉnh x thì những đỉnh y kề với x cũng đến được từ S. Điều đó gợi ý cho ta viết một thủ tục đệ quy DFS(u) mô tả việc duyệt từ đỉnh u bằng cách thông báo thăm đỉnh u và tiếp tục quá trình duyệt DFS(v) với v là một đỉnh chưa thăm kề với u. Để cài đặt đệ quy ta cần chú ý: Để không một đỉnh nào bị liệt kê tới hai lần, ta sử dụng kỹ thuật đánh dấu, mỗi lần thăm một đỉnh, ta đánh dấu đỉnh đó lại để các bước duyệt đệ quy kế tiếp không duyệt lại đỉnh đó nữa.
Để lưu lại đường đi từ đỉnh xuất phát S, trong thủ tục DFS(u), trước khi gọi đệ quy DFS(v) với v là một đỉnh kề với u mà chưa đánh dấu, ta lưu lại vết đường đi từ u tới v bằng cách đạt TRACE[v] := u, tức là TRACE[v] lưu lại đỉnh liền trước v trong đường đi từ S tới v. Thủ tục DFE được mô tả như sau 12 LUAN VAN CHAT LUONG download : add luanvanchat@agmail.com Procedure DFS(u) Input: G, u Output: Danh sách các đỉnh BEGIN 1: Đánh dấu u là được thăm (có thể tới được từ S); 2: Xét mọi đỉnh v kề với u mà chưa thăm, với mỗi đỉnh v đó; + Trace[v] := u; //Lưu vết đường đi + DFS(v); // Gọi đệ quy END; Thuật toán duyệt theo chiều rộng BFS Tư tưởng: Việc thăm một đỉnh sẽ lên lịch duyệt các đỉnh kề với nó nhất. Như vậy, thứ tự duyệt là ưu tiên chiều rộng. Ví dụ: Trong Hình 1.3, bắt đầu thăm đỉnh S.
Việc thăm đỉnh S sẽ phát sinh thứ tự duyệt những đỉnh kề với S. Chọn 1 đỉnh x để thăm. Khi thăm đỉnh x sẽ phát sinh yêu cầu duyệt những đỉnh kề với x… Hình 1.4: Duyệt cây theo chiều rộng BFS. Thuật toán duyệt theo chiều rộng được mô tả bằng thủ tục sau đây: Procedure BFS(u) Input: G, u Output: Danh sách các đỉnh 1: Khởi tạo: + Các đỉnh ở trạng thái chưa đánh dấu, trừ đỉnh xuất phát S.
+ Hàng đợi Q=S //Chứa các đỉnh sẽ được duyệt theo thứ tự.