tailieunhanh - Cấu trúc dữ liệu và giải thuật part 6

Tham khảo tài liệu 'cấu trúc dữ liệu và giải thuật part 6', công nghệ thông tin, cơ sở dữ liệu phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Bài toán bao đóng truyền ứng trasitive closure Bài toán nêu trên có thể giải quyết được dỗ dàng bằng cách sử dụng ma trận lân cân của dồ thị. Trước hốt ta thấy có thể coi ma trận làn cận như một ma trận Bool. Như vậy có thổ tác động lên ma trận đó các phép toán lôgic đối với ma trận Bool được. Ta nhác lại hai phép toán logic - Phép cộng hay phép tuyển phép hoạc V - Phép nhân hay phép hội phép và A mà định nghĩa được cho bơi bảng sau a b a V b a A b 0 0 0 0 0 1 1 0 1 0 1 0 1 1 1 1 Đối với ma trận Bool A và B kích thước n X n phép cộng A với B để cho ma trận tổng c c A vB được thực hiện bằng cách tính C-J ajj V bjj với 1 i n 1 j n Phép nhân A với B để cho ma trân tích D được thực hiện bằng phép tính du kv aik Abk với l i n 1 j n Ta đã biết với ma trân lân cận A nếu a- 1 thì nghĩa là có một cung hay một đường đi độ dài 1 từ đỉnh i tới đỉnh j. Bây giờ thử xét A 2 A A A rõ ràng nếu phần tử ở hàng i cột j của A bằng 1 thì ít nhất cũng có một đường đi có độ dài 2 tù đỉnh i tới đỉnh j vì Aakj l thì ít nhất cũng có một giá trị k mà ajk Aakj 1 mà aik Aakj chỉ bằng 1 khi 158 và chỉ khi cả alk 1 và akj 1 nghĩa là khì có đường đi độ dài 1 từ đỉnh i tới đỉnh k và có đường đi có độ dài 1 từ đĩnh k tới đỉnh j. Từ đó suy ra điều tương tự cho A l A A Aư với r 3 4. nghĩa là nếu tijj - 1 thì ít nhất có một đường đi độ dài r từ đỉnh i tới đỉnh J. Như vậy nếu ta lập ma trận p A V Aí2 vv A n V A k k-1 thì p sẽ cho biết có hay không đường di có độ dài lớn nhất là n từ đỉnh i tới đỉnh j. p được gọi là ma trân đường đi path matricc của đồ thị G. Ví dụ Với đổ thị Hỉnh i ta se có 0 0 10 0 0 10 0 0 11 0 10 0 0 0 11 0 0 11 0 111 0 0 10 0 111 0 111 0 111 0 0 11 A 2 A 0 111 0 111 0 111 0 111 0 111 0 111 0 111 0 111 Aơ p Việc tính p có thổ dễ dàng thực hiện bởi giải thuật Warshall sau đây 159 Procedure WARSHALL A p n 1 p A Đây là phép gán quy ước thay vào cho việc gán lần lượt các phần tử của A cho các phần tử tương ứng của PJ 2 for k 1 to n do for i 1 to n do for j 1 to n do p i j pfi j