CHƯƠNG I: LÝ THUYẾT ĐỒ THỊ VÀ CÂY 1.1 Các khái niệm cơ bản về đồ thị 1.1 Định nghĩa đồ thị (Graph) 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 đó. Được mô tả hình thức:G = (V, E) V gọi là tập các đỉnh (Vertices) và E gọi là tập các cạnh (Edges). 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.1: Ví dụ về mô hình đồ thị 1.2 Các khái niệm Như trên định nghĩa đồ thị G = (V, E) là một cấu trúc rời rạc, tức là các tập V và E hoặc là tập hữu hạn, hoặc là tập đếm được, có nghĩa là ta có thể đánh số thứ tự 1, 2, 3.
cho các phần tử của tậpV và E. Hơn nữa, đứng trên phương diện người lập trình cho máy tính thì ta chỉ quan tâm đến cácđồ thị hữu hạn (V và E là tập hữu hạn) mà thôi, chính vì vậy từ đây về sau, nếu không chú thích gì thêm thì khi nói tới đồ thị, ta hiểu rằng đó là đồ thị hữu hạn. 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). Ta có một số khái niệm sau: - Đơn đồ thị: G được gọi là đơn đồ thị nếu giữa hai đỉnh u, v của V có 7 nhiều nhấtlà 1 cạnh trong E nối từ u tới v.
- Đa đồ thị: G được gọi là đa đồ thị nếu giữa hai đỉnh u, v của V có thể có nhiều hơn 1 cạnh trong E nối từ u tới v. - Đồ thị vô hướng: G được gọi là đồ thị vô hướng nếu các cạnh trong E là không định hướng, tức là cạnh nối hai đỉnh u, v bất kỳ cũng là cạnh nối hai đỉnh v, u. Hay nói cách khác, tập E gồm các cặp (u, v) không tính thứ tự (u, v) (v, u) - Đồ thị có hướng: G được gọi là đồ thị có hướng nếu các cạnh trong E là có định hướng, có thể có cạnh nối từ đỉnh u tới đỉnh v nhưng chưa chắc đã có cạnh nốitừ đỉnh v tới đỉnh u. Hay nói cách khác, tập E gồm các cặp (u, v) có tính thứ tự:(u, v) ≠ (v, u).
Trong đồ thị có hướng, các cạnh được gọi là các cung. Đồ thị vôhướng cũng có thể coi là đồ thị có hướng nếu như ta coi cạnh nối hai đỉnh u, vbất kỳ tương đương với hai cung (u, v) và (v, u). Ví dụ: 3 1 2 5 4 Vô hướng Có hướng Vô hướng Có hướng Vô hướng Đa đồ thị Hình 1.2: Ví dụ về phân loại đồ thị Đối với đồ thị vô hướng G = (V, E). Xét một cạnh e E, nếu e=(u,v) thìta nói hai đỉnh u và v là kề nhau (adjacent) và cạnh e này liên thuộc (incident)với đỉnh u và đỉnh v.
Với một đỉnh v trong đồ thị, ta định nghĩa bậc (degree) của v, ký hiệu deg(v) là số cạnh liên thuộc với v. Dễ thấy rằng trên đơn đồ thị thì 8 số cạnh liên thuộc với v cũng là số đỉnh kề với v. Đối với đồ thị có hướng G = (V, E). Xét một cung e E, nếu e=(u,v) thìta nói u nối tới v và v nối từ u, cung e là đi ra khỏi đỉnh u và đi vào đỉnh v.Đỉnh u khi đó được gọi là đỉnh đầu, đỉnh v được gọi là đỉnh cuối của cung e.
Với mỗi đỉnh v trong đồ thị có hướng, ta định nghĩa: Bán bậc ra của v kýhiệu deg+(v) là số cung đi ra khỏi nó; bán bậc vào ký hiệu deg-(v) là số cung đi vàođỉnh đó. - Đường đi: Một đường đi độ dài k từ đỉnh u đến đỉnh v là dãy (u=x0, x1,.Đỉnhu gọi là đỉnh xuất phát, v gọi là đỉnh kết thúc của đường đi. Đường đi không cócạnh nào đi qua hơn 1 lần gọi là đường đi đơn. - Chu trình: Đường đi có đỉnh xuất phát trùng với đỉnh kết thúc gọi là chu trình.
Tương tự ta có khái niệm chu trình đơn.3 Các thuật toán tìm kiếm trên đồ thị a. Thuật toán tìm kiếm theo chiều sâu DFS (Depth – First – Search) Là một thuật toán duyệt hoặc tìm kiếm trên một cây hoặc một đồ thị. Thuật toán khởi đầu tại gốc (hoặc chọn một đỉnh nào đó coi như gốc) và phát triển xa nhất có thể theo mỗi nhánh. Thông thường, DFS là một dạng tìm kiếm thông tin không đầy đủ mà quá trình tìm kiếm được phát triển tới đỉnh con đầu tiên của nút đang tìm kiếm cho tới khi gặp được đỉnh cần tìm hoặc tới một nút không có con.
Khi đó giải thuật quay lui về đỉnh vừa mới tìm kiếm ở bước trước. Trong dạng không đệ quy, tất cả các đỉnh chờ được phát triển được bổ sung vào một ngăn xếp Last In First Ount (LIFO).3 Ví dụ về thuật toán tìm kiếm DFS Tìm kiếm ưu tiên chiều sâu bắt đầu thăm đỉnh A, đi theo cạnh trái, tiếp tục tìm kiếm xong ở cây con trái mới chuyển sang tìm kiếm ở cây con phải. Thứ tự thăm viếng các đỉnh là: A, B, D, F, E, C, G. Quá trình viếng thăm các đỉnh diễn ra như sau: Sau khi thăm đỉnh A, vì B chưa được thăm nên theo cạnh AB ta thăm B, tiếp tục theo cạnh BD tới viếng thăm D.
Từ D không thể tiếp tục đi xa hơn, ta quay lại B. Từ B, theo BF đến thăm F, từ F đến thăm E. Từ E vì A đã viếng thăm nên ta quay lại F, rồi quay lại B. Tại B vì tất cả các khả năng từ B đã xem xét nên ta quay lại A.
Từ A, quá trình tiếp tục với các đỉnh C và G. Kết quả của thuật toán: - Duyệt các đỉnh:Có thể dùng giải thuật này để tạo một danh sách tuyến tính các đỉnh của một đồ thị (hoặc cây). Có ba cách hiện thực phương pháp này: Duyệt tiền thứ tự (preordering): Tạo ra một danh sách mà trong đó các đỉnh xuất hiện theo đúng trật tự nó được thăm đến khi chạy thuật toán. Đây chính là biểu diễn tự nhiên của quá trình thực hiện giải thuật tìm kiếm theo chiều sâu.
Một biểu thức ở dạng tiền thứ tự được gọi là ký pháp tiền tố. Duyệt hậu thứ tự (postordering): Tạo ra một danh sách mà trong đó các đỉnh xuất hiện theo thứ tự của lần duyệt đến sau cùng khi thực hiện giải 10 thuật. Một lần duyệt hậu thứ tự một cây biểu thức sẽ cho ra một ký pháp hậu tố. Duyệt đảo hậu thứ tự (reverse postordering): Kết quả của cách duyệt này là sự đảo ngược lại thứ tự trong kết quả duyệt hậu thứ tự.
Thông thường, khi duyệt cây, cách này cho ra cùng kết quả với duyệt tiền thứ tự, nhưng xét tổng quát, khi duyệt một đồ thị, tiền thứ tự và đảo hậu thứ tự cho ra kết quả khác nhau. Với các đồ thị có hướng và không có vòng, cách duyệt đảo hậu thứ tự cho ra một trât tự tô-pô của đồ thị đó. Thuật toán tìm kiếm theo chiều sâu của đồ thị vô hướng: - Ý tưởng thuật toán:DFS trênđồ thị vô hướng cũng giống như khám phá mê cung với một cuộn chỉ và một thùng sơn đỏ để đánh dấu, tránh bị lạc. Trong đó mỗi đỉnh s trong đồ thị tượng trưng cho một cửa trong mê cung.
Ta bắt đầu từ đỉnh s, buộc đầu cuộn chỉ vào s và đánh đấu đỉnh này này "đã thăm". Sau đó ta đánh dấu s là đỉnh hiện hành u. Bây giờ, nếu ta đi theo cạnh (u,v) bất kỳ. Nếu cạnh (u,v) dẫn chúng ta đến đỉnh "đã thăm" v, ta quay trở về u.
Nếu đỉnh v là đỉnh mới, ta di chuyển đến v và lăn cuộn chỉ theo. Đánh dấuv là "đã thăm". Đặt v thành đỉnh hiện hành và lặp lại các bước. Cuối cùng, ta có thể đi đến một đỉnh mà tại đó tất cả các cạnh kề với nó đều dẫn chúng ta đến các đỉnh "đã thăm".
Khi đó, ta sẽ quay lui bằng cách cuộn ngược cuộn chỉ và quay lại cho đến khi trở lại một đỉnh với một đỉnh còn chưa được khám phá. Lại tiếp tục quy trình khám phá như trên. Khi chúng ta trở về s và không còn cạnh nào kề với nó chưa bị khám phá là lúc DFS dừng. - Độ phức tạp của thuật toán: DFS được gọi đúng 1 lần ứng với mỗi đỉnh.
Mỗi cạnh được xem xét đúng 2 lần, mỗi lần từ một đỉnh kề với nó. 11 Với ns đỉnh và ms cạnh thuộc thành phần liên thông chứa s, một phépDFS bắt đầu tại s sẽ chạy với thời gian O(ns + ms) nếu: Đồ thị được biểu diễn bằng cấu trúc dữ liệu dạng danh sách kề. Đặt nhãn cho một đỉnh là "đã thăm" và kiểm tra xem một đỉnh "đã thăm chưa tốn chi phí O(degree). Bằng cách đặt nhãn cho các đỉnh là "đã thăm", ta có thể xem xét một cách hệ thống các cạnh kề với đỉnh hiện hành nên ta sẽ không xem xét một cạnh quá 1 lần.
- Xác định đỉnh kề trong DFS Kết quả của DFS phụ thuộc vào cách ta chọn đỉnh kế tiếp Hình 1.4 Xác định đỉnh kề trong thuật toán DFS Nếu ta bắt đầu tại A và thử cạnh nối đến F, sau đó đến B, rồi đến E, C, cuối cùng là G ta được: 12 Hình 1.5 Đường đi bắt đầu từ A và kết thúc tại G Nếu cũng bắt đầu từ A nhưng đi theo trình tự, tập các cạnh đã thăm,backedge và các điểm đệ quy sẽ khác trước.6 Bắt đầu từ A nhưng đi theo trình tự tập các cạnh đã thăm b. Thuật toán tìm kiếm theo chiều rộng Tìm kiếm theo chiều rộngBreadth First Search (BFS) là một thuật toán tìm kiếm trong đồ thị trong đó việc tìm kiếm chỉ bao gồm 2 thao tác: (a) thăm một đỉnh của đồ thị; (b) thêm các đỉnh kề với đỉnh vừa thăm vào danh sách có thể thăm trong tương lai. Có thể sử dụng thuật toán tìm kiếm theo chiều rộng cho hai mục đích: tìm kiếm đường đi từ một đỉnh gốc cho trước tới một đỉnh đích, và tìm kiếm đường đi từ đỉnh gốc tới tất cả các đỉnh khác. Trong đồ thị không có trọng số, thuật toán tìm kiếm theo chiều rộng luôn tìm ra đường đi ngắn nhất có thể.
Thuật toán BFS bắt đầu từ đỉnh gốc và lần lượt thăm các đỉnh kề với đỉnh gốc. Sau đó, với mỗi đỉnh trong số đó, thuật toán lại lần lượt thăm các đỉnh kề với nó mà chưa được thăm trước đó và lặp lại.