Đang chuẩn bị liên kết để tải về tài liệu:
BÀI 02: Một số tính chất về Đường đi trên đồ thị

Trong phần này chúng ta xét một số tính chất của đường đi nối hai đỉnh trong một đồ thị cũng như sự tồn tại của chúng. Định lý 1.2: Giả sử đồ thị G có n đỉnh. Tồn tại đường đi từ đỉnh a đến đỉnh b trên đồ thị G khi và chỉ khi tồn tại một đường đi từ a đến b trên đồ thị này với độ dài không vượt quá n-1. | BÀI 02 1.2. Một số tính chất về Đường đi trên đồ thị Trong phần này chúng ta xét một số tính chất của đường đi nối hai đỉnh trong một đồ thị cũng như sự tồn tại của chúng. Định lý 1.2 Giả sử đồ thị Gcó n đỉnh. Tồn tại đường đi từ đỉnh a đến đỉnh b trên đồ thị G khi và chỉ khi tồn tại một đường đi từ a đến b trên đồ thị này với độ dài không vượt quá n-1. Chứng minh Giả sử có đường đi từ đỉnh a tới đỉnh b. Ta có thể chọn a x1 x2 . xk b là đường đi có độ dài ngắn nhất. Hình 1.6. Một đường đi từ đỉnh a đến đỉnh b Độ dài của đường đi là k-1. Nếu k-1 n-1 thì định lý được chứng minh. Nếu ngược lại k-1 n-1 nghĩa là k n thì trong dãy đỉnh của đường đi sẽ có ít nhất hai đỉnh trùng nhau chẳng hạn xi xj . Khi đó thì a x x2 . xi xj i . xk b cũng là đường đi từ a tới b nhưng với độ dài ngắn hơn. Suy ra mâu thuân với giả thiết của đường đi ngắn nhất. Định lý được chứng minh xong. Chúng ta xét bài toán đường đi trên đồ thị như sau. Bài toán Cho đồ thị G và hai đỉnh a b thuộc G. Có hay không một đường đi từ đỉnh a đến đỉnh b trên đồ thị G Dựa vào Định lý 1.1 và 1.2 ta xây dựng thuật toán sau đây để trả lời cho bài toán trên. Thuật toán 1.3 1 Xây dựng ma trận kề A cho đồ thị G. 2 Tính ma trận tổng các luỹ thừa T A1 A2 . An-1 3 Nếu T a b 1 thì kết luận là có đường đi từ đỉnh a đến đỉnh b ngược lại thì kết luận là không có. Chú ý 1. Ma trận tổng T còn được gọi là bao đóng bắc cầu của ma trận kề A. 2. Các phần tử của ma trận T có thể rất lớn hơn nữa chúng ta chỉ quan tâm đến tính chất khác 0 của các phần tử nên có thể xem ma trận kề A như ma trận logic và trong phép nhân ma trận ta thay các phép toán số học bằng các phép toán logic OR và AND. Khi đó ta dùng thuật toán Warshall sau đây để tính ma trận bao đóng bắc cầu logic AS. Các phần tử logic của ma trận AS cho biết có hay không đường đi giữa tất cả các cặp đỉnh của đồ thị đã cho. Thuật toán 1.4 Warshall Dữ liệu Ma trận kề logic A của đồ thị G. Kết quả Ma trận bao đóng bắc cầu logic AS. 1 Begin 2 for i 1 to n do 3 for j 1 to n do AS