TAILIEUCHUNG - Giáo trình đồ thị - Một số tính chất về Đường đi trên đồ thị

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ý : 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. Chứng minh: Giả sử có đường đi từ đỉnh a tới đỉnh b | 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ý 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 Xj x2 . xk b là đường đi có độ dài ngắn nhất. Hình . 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 xj 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ý và 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 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 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

• Toán học
• đồ thị
• giáo trình đồ thị
• tài liệu về đồ thị
• ứng dụng của đồ thị
• tài liệu về đồ thị
• Lý thuyết đồ thị
• Bài giảng Lý thuyết đồ thị
• Đại cương về đồ thị
• Các mô hình đồ thị
• Thuật ngữ cơ bản của đồ thị
• Đường đi của đồ thị
• Sự liên thông đồ thị
• Đồ thị phẳng
• định lý Kemple
• định lý heawood
• đồ thị vô hướng
• đồ thị Euler
• đồ thị hamiton
• bài giảng đồ thị phẳng
• biểu diễn đồ thị
• bậc của đỉnh trong đồ thị
• đại cương đồ thị
• bài giảng về đồ thị
• Biểu diễn đồ thị trên máy tính
• Sự đẳng cấu của đồ thị
• Phương pháp biểu diễn đồ thị
• Biểu diễn đồ thị bằng ma trận kề
• Đồ thị Hamilton
• Chu trình Hamilton
• Kiểm tra đồ thị Hamilton
• Đơn đồ thị đặc biệt
• Đồ thị bánh xe
• Đồ thị con
• Mô hình đồ thị
• Khái niệm đồ thị
• đồ thị riêng
• sự đẳng hình của đồ thị
• cách biểu diễn đồ thị
• định nghĩa đồ thị
• toán rời rạc
• nguyên lý đồ thị
• tự học đồ thị
• cách vẽ đồ thị
• tô màu đồ thị
• Vẽ đồ thị
• bài toán luồng trên mạng
• tài liệu học đại học
• bài giảng toán học
• toán đồ thị
• đơn đồ thị
• đa đồ thị
• giả đồ thị
• đồ thị có hướng