Đồ án Xây dựng bài toán ghép đôi không trọng số

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 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ất đị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ụ e 2 e e1 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 Đ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. 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 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. Đị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ị. E là một họ các cặp cạnh 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ụ e 2 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 . Đị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à 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: Hình 6: Đơn đồ thị vô hướng 1 2 3 4 5 6 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 = . 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: 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ị trên máy tính 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ải 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. 1.1.3.1. 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 (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 3 5 2 4 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 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ì 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). 1.1.3.2. Danh sách 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 5 4 3 2 Đỉnh Đỉnh liền kề 1 2, 3,4, 5 2 1,3, 4, 5 3 1,2,4 4 1,2,3 5 1,2 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 . Nhược điểm của danh sách kề Về lý thuyết, so với hai phương pháp biểu diễn trên, danh sách kề tốt hơn hẳn. Chỉ có điều, trong trường hợp cụ thể mà ma trận kề hay danh sách cạnh không thể hiện nhược điểm thì ta nên dùng ma trận kề (hay danh sách cạnh) bởi cài đặt danh sách kề có phần dài dòng hơn. 1.1.3.3. Ma trận liền kề Giả sử G = (V, E) là một đồ thị đơn trong đó |V| = n và các đỉnh được liệt kê tuỳ v1,,vn. Ma trận liền kề A của G ứng với danh sách các đỉnh này là ma trận không - một cấp n*n có phần tử hàng i, cột j bằng 1 nếu vi và vj liền kề nhau, và bằng 0 nếu chúng không được nối với nhau. 1 0 1 1 1 1 2 1 0 1 1 1 3 4 5 1 1 0 1 0 1 1 1 0 0 1 1 0 0 0 1 5 4 3 2 1 2 4 5 Hình 10: Ví dụ biểu diễn đồ thị ma trận kề Các tính chất của ma trận liền kề: Đối với đồ thị vô hướng G, thì ma trận liền kề tương ứng là ma trận đối xứng (aij = aji), điều này không đúng với đồ thị có hướng. Nếu G là đồ thị vô hướng và A là ma trận liền kề tương ứng thì trên ma trận A: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) Nếu G là đồ thị có hướng và A là ma trận liền kề tương ứng thì trên ma trận A: Tổng các số trên hàng i = Bán bậc ra của đỉnh i = deg+(i) Tổng các số trên cột i = Bán bậc vào của đỉnh i = deg-(i) Trong trường hợp G là đơn đồ thị, ta có thể biểu diễn ma trận liền kề A tương ứng là các phần tử logic.Aij = TRUE nếu (i, j) E và aij = FALSE nếu (i, j) ∉ E Ưu điểm của ma trận liền kề: Đơn giản, trực quan, dễ cài đặt trên máy tính Để kiểm tra xem hai đỉnh (u, v) của đồ thị có kề nhau hay không, ta chỉ việc kiểm tra bằng một phép so sánh: auv ≠ 0. Nhược điểm của ma trận liền kề: Bất kể số cạnh của đồ thị là nhiều hay ít, ma trận liền kề luôn luôn đòi hỏi n2 ô nhớ để lưu các phần tử ma trận, điều đó gây lãng phí bộ nhớ dẫn tới việc không thể biểu diễn được đồ thị với số đỉnh lớn. Với một đỉnh u bất kỳ của đồ thị, nhiều khi ta phải xét tất cả các đỉnh v khác kề với nó, hoặc xét tất cả các cạnh liên thuộc với n . Trên ma trận liền kề việc đó được thực hiện bằng cách xét tất cả các đỉnh v và kiểm tra điều kiện auv ≠ 0. Như vậy, ngay cả khi đỉnh u là đỉnh cô lập (không kề với đỉnh nào) hoặc đỉnh treo (chỉ kề với 1 đỉnh) ta cũng buộc phải xét tất cả các đỉnh và kiểm tra điều kiện trên dẫn tới lãng phí thời gian. 1.1.3.4. Ma trận liên thuộc Giả sử G = (V, E) là một đồ thị vô hướng, v1, v2, vn là tập các đỉnh còn e1, e2, ..., em là tập các cạnh của nó. Khi đó ma trận liên thuộc theo thứ tự trên của V và E là ma trận M = [mij] trong đ : mij = 1 nếu cạnh ej nối với đỉnh vi mij = 0 nếu cạnh ej không nối với e1 e2 e3 e4 e5 e6 e7 e8 v1 1 0 0 0 1 1 1 0 v2 1 1 1 1 0 0 0 0 v3 0 0 0 1 0 1 0 1 v4 0 0 1 0 0 0 1 1 v5 0 1 0 0 1 0 0 0 đỉnh v i e 1 e 6 e 4 e 3 e 2 e 7 V 1 V 5 V 4 V 2 V 3 e 8 Ví dụ biểu diễn đồ thị ma trận liên thuộc 1.2. Độ phức tạp tính toán và tính hiệu quả của thuật toán 1.2.1. Định nghĩa thuật toán Thuật toán là một dãy hữu hạn các bước, mỗi bước mô tả chính xác các phép toán hoặc hành động cần thực hiện để cho ta lời giải của bài toán. - Thao tác, hay còn gọi là tác vụ, phép toán ( Operation ) hay lệnh (Command), chỉ thị (Instruction)...là một hành động cần được thực hiện bởi cơ chế thực hiện thuật toán. Mỗi thao tác biến đổi bài toán từ một trạng thái trước (hay trạng thái nhập) sang trạng thái sau (hay trạng thái xuất).Thực tế mỗi thao tác thường sử dụng một số đối tượng trong trạng thái nhập (các đối tượng nhập )và sản sinh ra các đối tượng mới trong trạng thái xuất (các đối tượng xuất). Quan hệ giữa 2 trạng thái xuất và nhập cho thấy tác động của thao tác. Dãy các thao tác của thuật toán nối tiếp nhau nhằm biến đổi bài toán từ trạng thái ban đầu đến trạng thái kết quả. Mỗi thao tác có thể phân tích thành các thao tác đơn giản hơn. Trình tự thực hiện các thao tác phải được xác định rõ ràng trong thuật toán. Cùng một tập hợp thao tác nhưng xếp đặt theo trình tự khác nhau sẽ cho kết quả khác nhau. 1.2.2. Phân tích độ phức tạp của thuật toán Trong khi giải một bài toán có thể có một số giải thuật khác nhau, vấn đề là cần phải đánh giá các giải thuật đó để lựa chọn một giải thuật tốt nhất. Thông thường người ta căn cứ vào các tiêu chuẩn sau: Tiêu chuẩn về tính đúng đắn của thuật toán, thuật toán có cho lời giải đúng của bài toán hay không ? Tiêu chuẩn về tính đơn giản của thuật toán. Thường ta mong muốn có được một thuật toán đơn giản, dễ hiểu, dễ lập trình. Đặc biệt là những thuật toán chỉ dùng một vài lần ta cần coi trọng tính chất này, vì công sức và thời gian bỏ ra để xây dựng thuật toán thường lớn hơn rất nhiều so với thời gian thực hiện nó. Tiêu chuẩn về thời gian: Thời gian chạy của thuật toán có nhanh không? Khi một chương trình được sử dụng nhiều lần thì yêu cầu tiết kiệm thời gian thực hiện chương trình lại rất quan trọng, đặc biệt đối với những bài toán mà dữ liệu đầu vào lớn thì tiêu chuẩn này là rất quan trọng. Trong phần này ta quan tâm chủ yếu đến độ phức tạp thời gian của thuật toán. Các bước trong quá trình phân tích đánh giá thời gian chạy của thuật toán: Bước đầu tiên trong việc phân tích thời gian chạy của thuật toán là quan tâm đến kích thước dữ liệu, sẽ được dùng như dữ liệu nhập của thuật toán và quyết định phân tích thuật toán nào là thích hợp. Ta có thể xem thời gian chạy của thuật toán là một hàm theo kích thước của dữ liệu nhập. Nếu gọi n là kích thước của dữ liệu nhập thì thời gian thực hiện T của thuật toán được biểu diễn như một hàm theo n, ký hiệu là: T(n). Người ta thường coi T(n) là thời gian thực hiện chương trình trong trường hợp xâu nhất trên dữ liệu vào có kích thước n, tức là: T(n) là thời gian lớn nhất để thực hiện chương trình đối với mọi dữ liệu vào có cùng kích thước n. Bước thứ hai trong việc phân tích thời gian chạy của một thuật toán là nhân ra các thao tác trừu tượng của thuật toán để tách biệt sự phân tích và sự cài đặt. Bởi vì ta biết rằng tốc độ xử lý của máy tính và các bộ dịch của ngôn ngữ lập trình cao cấp đều ảnh hưởng đến thời gian chạy của thuật toán, nhưng những thao tác này không đồng đều trên các loại máy trên đó cài đặt thuật toán, vì vậy không thể dựa và chúng để đánh giá thời gian chạy của thuật toán. Chẳng hạn ta tách biệt sự xem xét xem có bao nhiêu phép toán so sánh trong một thuật toán sắp xếp khỏi sự xác định cần bao nhiêu micro giây chạy trên một máy tính cụ thể. Yếu tố thứ nhất được xác định bởi tính chất của thuật toán, còn yếu tố thứ hai được xác định bởi tính năng của máy tính. Điều này cho thấy rằng T(n) không thể được biểu diễn bằng giây, phút được; cách tốt nhất là biểu diễn theo số các chỉ thị trong thuật toán. 1.2.3. Tối ưu thuật toán Tiến trình tổng quát của việc tạo ra các sửa đổi ngày càng tiến bộ hơn cho một thuật toán để sinh ra một phiên bản khác chạy nhanh hơn được gọi là tối ưu thuật toán. Khi tối ưu một thuật toán ta thường dựa vào một nguyên lý, đó là nguyên l Profile : ― Tìm điểm mất thời gian nhiều nhất của thuật toán ―. Một số kỹ thuật thường dùng để tối ưu thuật toán là: Kỹ thuật tối ưu các vòng lặp và tối ưu việc rẽ nhánh Đây là điểm quan tâm đầu tiên khi cải tiến thuật toán, vì vòng lặp là câu lệnh thường làm tăng độ phức tạp của thuật toán. Việc cải tiến tập trung vào: Cố gắng giảm các vòng lặp lồng nhau. Tăng số lệnh thực hiện trong một bước lặp để giảm số lượng các bước lặp. Tách các lệnh không phụ thuộc vào chỉ số lặp ra khỏi vòng lặp. 1.3. Một số thuật toán tìm kiếm trên đồ thị 1.3.1. Thuật toán tìm kiếm theo chiều sâu ( Depth first search ) procedure DFS(u∈V); begin ; ; ; begin Trace[v]: = u; {Lưu vết đường đi, đỉnh mà từ đo tới v là u} DFS(v); {Gọi đệ quy duyệt tƣơng tự đối với v} end; end; begin {Chương trình chính} ; ; DFS(S); ; ; end. Ví dụ: Với đồ thị sau đây, đỉnh xuất phát S = 1: quá trình duyệt đệ quy có thể vẽ trên cây tìm kiếm DFS sau (Mũi tên u→v chỉ thao tác đệ quy: DFS(u) gọi DFS(v)). Quá trình tìm kiếm theo chiều sâu 1.3.2. Thuật toán tìm kiếm theo chiều rộng (Breadth first search) Cơ sở của phương pháp cài đặt này là "lập lịch" duyệt các đỉnh. Việc thăm một đỉnh sẽ lên lịch duyệt các đỉnh kề nó sao cho thứ tự duyệt là ưu tiên chiều rộng (đỉnh nào gần S hơn sẽ được duyệt trước). Ví dụ: Bắt đầu ta thăm đỉnh S. Việc thăm đỉnh S sẽ phát sinh thứ tự duyệt những đỉnh (x1, x2, ..., xp) kề với S (những đỉnh gần S nhất). Khi thăm đỉnh x1 sẽ lại phát sinh yêu cầu duyệt những đỉnh (u1, u2 ..., uq) kề với x1. Nhưng rõ ràng các đỉnh u này "xa" S hơn những đỉnh x nên chúng chỉ được duyệt khi tất cả những đỉnh x đã duyệt xong. Tức là thứ tự duyệt đỉnh sau khi đã thăm x1 sẽ là: (x2, x3..., xp, u1, u2, ..., uq). X 1 X 2 X p U 1 U 2 U p S Cây BFS Giả sử ta có một danh sách chứa những đỉnh đang "chờ" thăm. Tại mỗi bước, ta thăm một đỉnh đầu danh sách và cho những đỉnh chưa "xếp hàng" kề với n xếp hàng thêm vào cuối danh sách. Chính vì nguyên tắc đó nên danh sách chứa những đỉnh đang chờ sẽ được tổ chức dưới dạng hàng đợi (Queue) Ta sẽ dựng giải thuật như sau: Bước 1: Khởi tạo: Các đỉnh đều ở trạng thái chưa đánh dấu, ngoại trừ đỉnh xuất phát S là đã đánh dấu Một hàng đợi (Queue), ban đầu chỉ có một phần tử là S. Hàng đợi dùng để chứa các đỉnh sẽ đƣợc duyệt theo thứ tự ưu tiên chiều rộng Bước 2: Lặp các bước sau đến khi hàng đợi rỗng: Lấy u khỏi hàng đợi, thông báo thăm u (Bắt đầu việc duyệt đỉnh u) Xét tất cả những đỉnh v kề với u mà chưa được đánh dấu, với mỗi đỉnh v đó: Đánh dấu v. Ghi nhận vết đường đi từ u tới v (Có thể làm chung với việc đánh dấu) Đẩy v vào hàng đợi (v sẽ chờ được duyệt tại những bước sau) Bước 3: Truy vết tìm đường đi. Ví dụ: Xét đồ thị dưới đây, Đỉnh xuất phát S = 1. 1 2 4 6 3 5 7 1 2 4 6 3 5 7 8 8 1 Hàng đợi Đỉnh u (lấy ra từ hàng đợi) Hàng đợi (sau khi lấy u ra) Các đỉnh v kề u mà chưa lên lịch Hàng đợi sau khi đẩy những đỉnh v vào (1) 1 ∅ 2, 3 (2, 3) (2, 3) 2 (3) 4 (3, 4) (3, 4) 3 (4) 5 (4, 5) (4, 5) 4 (5) 6 (5, 6) (5, 6) 5 (6) Không có (6) (6) 6 ∅ Không có ∅ Quá trình tìm kiếm theo chiều rộng Để thứ tự các phần tử lấy ra khỏi hàng đợi, ta thấy trước hết là 1; sau đó đến 2, 3; rồi mới tới 4, 5; cuối cùng là 6. Rõ ràng là đỉnh gần S hơn sẽ được duyệt trước. Và như vậy, ta có nhận xét: nếu kết hợp lưu vết tìm đường đi thì đường đi từ S tới F sẽ là đường đi ngắn nhất (theo nghĩa qua ít cạnh nhất) 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 2.1. Đồ thị hai phía Một đơn đồ thị vô hướng G = (V, E) được gọi là đồ thị hai phía nếu tập các đỉnh V có thể phân thành hai tập con không rỗng, rời nhau X và Y sao cho mỗi cạnh của đồ thị nối một đỉnh của X với một đỉnh của Y. Khi đó , người ta còn ký hiệu G là ( X Y, E) và gọi một tập (giả sử là tập X) là tập các đỉnh trái và tập còn lại là tập các đỉnh phải của đồ thị hai phía G. Các đỉnh thuộc X còn gọi là các X_đỉnh, các đỉnh thuộc Y gọi là các Y_đỉnh. X Y Để kiểm tra một đồ thị liên thông có phải là đồ thị hai phía hay không, ta có thể áp dụng thuật toán sau: Với một đỉnh v bất kỳ: := {v}; Y := ∅; repeat := Y ∪ Kề(X); X := X ∪ Kề(Y); until (X∩Y ≠ ∅) or (X và Y là tối đại - không bổ sung được nữa); if X∩Y ≠ ∅ then else ; Đồ thị hai phía gặp rất nhiều mô hình trong thực tế. Chẳng hạn quan hệ hôn nhân giữa tập những người đàn ông và tập những người đàn bà, việc sinh viên chọn trường, thầy giáo chọn tiết dạy trong thời khoá biểu, bài toán xếp lớp học theo học chế tín chỉ v.v... Tính chất một đồ thị là hai phía khi và chỉ khi nó không chứa chu trình lẻ kích thước của phủ đỉnh nhỏ nhất bằng kích thước của cặp ghép lớn nhất kích thước của tập độc lập lớn nhất cộng kích thước của cặp ghép lớn nhất bằng số đỉnh. trong đồ thị hai phía liên thông, kích thước của phủ cạnh nhỏ nhất bằng kích thước tập độc lập lớn nhất trong đồ thị hai phía liên thông, kích thước của phủ cạnh nhỏ nhất cộng kích thước của phủ đỉnh nhỏ nhất bằng số đỉnh. một đồ thị là hai phía khi và chỉ khi có thể tô nó bằng hai màu. 2.2. Bài toán ghép cặp không trọng số trong đồ thị hai phía 2.2.1. Các khái niệm Cho một đồ thị hai phía G = (XÈY, E) ở đây X là tập các đỉnh trái và Y là tập các đỉnh phải của G. Một cặp ghép (matching) của G là một tập hợp các cạnh của G đôi một không có đỉnh chung. Bài toán ghép cặp (matching problem) là tìm một cặp ghép lớn nhất (nghĩa là có số cạnh lớn nhất) của G Xét một cặp ghép M của G. Các đỉnh trong M gọi là các đỉnh đã ghép (matched vertices), các đỉnh khác là chưa ghép. Các cạnh trong M gọi là các cạnh đã ghép, các cạnh khác là chưa ghép. Nếu định hướng lại các cạnh của đồ thị thành cung, những cạnh chưa ghép được định hướng từ X sang Y, những cạnh đã ghép định hướng từ Y về X. Trên đồ thị định hướng đó: Một đường đi xuất phát từ một X_đỉnh chưa ghép gọi là đường pha, một đường đi từ một X_đỉnh chưa ghép tới một Y_đỉnh chưa ghép gọi là đường mở. Một cách dễ hiểu, có thể quan niệm như sau: Một đường pha (alternating path) là một đường đi đơn trong G bắt đầu bằng một X_đỉnh chưa ghép, đi theo một cạnh chưa ghép sang Y, rồi đến một cạnh đã ghép về X, rồi lại đến một cạnh chưa ghép sang Y... cứ xen kẽ nhau như vậy. Một đường mở (augmenting path) là một đường pha. Bắt đầu từ một X_đỉnh chưa ghép kết thúc bằng một Y_đỉnh chưa ghép. Một đường pha P kết thúc bằng một đỉnh chưa ghép của Y được gọi là đường mở, bởi vì chúng ta có thể sử dụng nó chuyển M thành một cặp ghép lớn nhất. Đường mở đóng một vai trò quan trọng trong việc tìm kiếm các cặp ghép lớn. Chúng ta sử dụng thuật toán đường mở để tìm một cặp ghép lớn nhất. X Y 1 2 3 1 2 3 2.2.2. Thuật toán đường mở Bắt đầu từ một cặp ghép bất kỳ M (thông thường cặp ghép được khởi gán bằng cặp ghép rỗng hay được tìm bằng các thuật toán tham lam). Sau đó đi tìm một đường mở, nếu tìm được thì mở rộng cặp ghép M như sau: Trên đường mở, loại bỏ những cạnh đã ghép khỏi M và thêm vào M những cạnh chưa ghép. Nếu không tìm được đường mở thì cặp ghép hiện thời là lớn nhất. for ("xÎX) do if then Ví dụ: tìm cặp ghép trong đồ thị hai phía sau: X Y X1 X2 X3 Y1 Y2 Y3 Như ví dụ trên, với cặp ghép hai cạnh M = {(X1, Y1), (X2, Y2)} và đường mở tìm được gồm các cạnh: (X3, Y2) Ï M (Y2, X2) Î M (X2, Y1) Ï M (Y1, X1) Î M (X1, Y3) Ï M Vậy thì ta sẽ loại đi các cạnh (Y2, X2) và (Y1, X1) trong cặp ghép cũ và thêm vào đó các cạnh (X3, Y2), (X2, Y1), (X1, Y3) được cặp ghép 3 cạnh. 2.2.3. Độ phức tạp của thuật toán Vì đường mở bắt đầu từ một đỉnh chưa ghép thuộc tập X, đi theo một cạnh chưa ghép sang tập Y, rồi theo một cạnh đã ghép về tập X,cuối cùng là cạnh chưa ghép tới một đỉnh thuộc tập Y chưa ghép. Nên ta thấy độ dài đường mở là lẻ và trên đường mở số cạnh thuộc M ít hơn số cạnh không thuộc M là 1 cạnh . Ta có thể sử dụng thuật toán tìm kiếm theo chiều rộng (BFS) để đường mở tìm được là đường đi ngắn nhất, giảm bớt công việc cho bước tăng cặp ghép. Người ta đã chứng minh được chi phí thời gian thực hiện giải thuật này trong trường hợp xấu nhất sẽ là 0(n3) đối với đồ thị dày và 0(n(n+m)logn) đối với đồ thị thưa (trong đ n là số đỉnh và m là số cạnh của đồ thị ). 2.2.4. Cài đặt 2.2.3.1. Biểu diễn đồ thị hai phía Giả sử đồ thị hai phía G = (XÈY, E) có các X_đỉnh ký hiệu là X[1], X[2], ..., X[m] và các Y_đỉnh ký hiệu là Y[1], Y[2], ..., Y[n]. Ta sẽ biểu diễn đồ thị hai phía này bằng ma trận A cỡ mxn. Trong đó: A[i, j] = TRUE nếu như có cạnh nối đỉnh X[i] với đỉnh Y[j]. A[i, j] = FALSE nếu như không có cạnh nối đỉnh X[i] với đỉnh Y[j]. 2.2.3.2. Biểu diễn cặp ghép Để biểu diễn cặp ghép, ta sử dụng hai mảng: matchX[1..m] và matchY[1..n]. matchX[i] là đỉnh thuộc tập Y ghép với đỉnh X[i] matchY[j] là đỉnh thuộc tập X ghép với đỉnh Y[j]. Tức là nếu như cạnh (X[i], Y[j]) thuộc cặp ghép thì matchX[i] = j và matchY[j] = i. Quy ước rằng: Nếu như X[i] chưa ghép với đỉnh nào của tập Y thì matchX[i] = 0 Nếu như Y[j] chưa ghép với đỉnh nào của tập X thì matchY[j] = 0. Để thêm một cạnh (X[i], Y[j]) vào cặp ghép thì ta chỉ việc đặt matchX[i] := j và matchY[j] := i; Để loại một cạnh (X[i], Y[j]) khỏi cặp ghép thì ta chỉ việc đặt matchX[i] := 0 và matchY[j] := 0; 2.2.3.3. Tìm đường mở Vì đường mở bắt đầu từ một X_đỉnh chưa ghép, đi theo một cạnh chưa ghép sang tập Y, rồi theo một cạnh đã ghép để về tập X, rồi lại một cạnh chưa ghép sang tập Y ... cuối cùng là cạnh chưa ghép tới một Y_đỉnh chưa ghép. Nên có thể thấy ngay rằng độ dài đường mở là lẻ và trên đường mở số cạnh Î M ít hơn số cạnh Ï M là 1 cạnh. Và cũng dễ thấy rằng giải thuật tìm đường mở nên sử dụng thuật toán tìm kiếm theo chiều rộng để đường mở tìm được là đường đi ngắn nhất, giảm bớt công việc cho bước tăng cặp ghép. Để tìm đường mở bắt đầu tại đỉnh x*ÎX, ta khởi tạo một hàng đợi (Queue) ban đầu chỉ có một đỉnh x*. Thuật toán tìm kiếm theo chiều rộng