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ị 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. Ta có thể chọn:
< a = x
1, x
2 , ... , x
k = 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
1, x
2, ... , x
i , x
j+1 , ... , x
k = 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:
Bạn đang xem 1. - BAI_02
