Cho đồ thị G = V, E và hai đỉnh s, t bất kì. Chứng minh tính chất
Cho đồ thị G = (V, E) và hai đỉnh s, t bất kì. Chứng minh tính chất: Tồn tại đường đi từ s đến t khi và chỉ khi quá trình duyệt theo chiều sâu từ đỉnh s sẽ duyệt qua đỉnh t, hay nói cách khác, quá trình duệt theo chiều sâu từ đỉnh s sẽ đi qua tất cả các đỉnh nằm trong thành phần liên thông chứa đỉnh s, trong đó có đỉnh t.
Giải Chuyên đề Tin 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu - Kết nối tri thức
Vận dụng 3 trang 71 Chuyên đề Tin học 12: Cho đồ thị G = (V, E) và hai đỉnh s, t bất kì. Chứng minh tính chất: Tồn tại đường đi từ s đến t khi và chỉ khi quá trình duyệt theo chiều sâu từ đỉnh s sẽ duyệt qua đỉnh t, hay nói cách khác, quá trình duệt theo chiều sâu từ đỉnh s sẽ đi qua tất cả các đỉnh nằm trong thành phần liên thông chứa đỉnh s, trong đó có đỉnh t.
Lời giải:
Để chứng minh tính chất: "Tồn tại đường đi từ đỉnh s đến đỉnh t khi và chỉ khi quá trình duyệt theo chiều sâu từ đỉnh s sẽ duyệt qua đỉnh t", chúng ta cần chứng minh hai điều sau:
- Nếu tồn tại đường đi từ đỉnh s đến đỉnh t, thì quá trình duyệt DFS từ đỉnh s sẽ duyệt qua đỉnh t.
- Nếu quá trình duyệt DFS từ đỉnh s duyệt qua đỉnh t, thì tồn tại đường đi từ đỉnh s đến đỉnh t.
Chứng minh điều 1: Nếu tồn tại đường đi từ đỉnh s đến đỉnh t, thì quá trình duyệt DFS từ đỉnh s sẽ duyệt qua đỉnh t
- Giả sử tồn tại đường đi từ đỉnh s đến đỉnh t. Điều này có nghĩa là có một dãy các đỉnh s = v0,v1,v2,…,vk=t sao cho (vi,vi+1) ∈ E với mọi 0 ≤ i< k Khi thực hiện DFS từ đỉnh s, DFS sẽ thăm tất cả các đỉnh mà nó có thể truy cập được từ s. Điều này bao gồm các đỉnh v1,v2,…,vk vì chúng liên tiếp nhau trong đường đi từ s đến t.
- Do đó, nếu tồn tại đường đi từ đỉnh s đến đỉnh t, DFS sẽ chắc chắn thăm đỉnh t trong quá trình duyệt.
Chứng minh điều 2: Nếu quá trình duyệt DFS từ đỉnh s duyệt qua đỉnh t, thì tồn tại đường đi từ đỉnh s đến đỉnh t
- Giả sử quá trình duyệt DFS từ đỉnh s duyệt qua đỉnh t. Điều này có nghĩa là DFS đã bắt đầu từ đỉnh s và theo các cạnh của đồ thị, nó đã đến đỉnh t.
- DFS duyệt đồ thị bằng cách đi theo các cạnh của đồ thị, nên mỗi bước từ đỉnh hiện tại đến đỉnh tiếp theo trong quá trình duyệt DFS đều là di chuyển qua các cạnh của đồ thị.
- Nếu DFS đã thăm đỉnh t từ đỉnh s, điều đó có nghĩa là có một dãy các đỉnh bắt đầu từ s và kết thúc tại t sao cho mỗi đỉnh trong dãy này đều có cạnh nối với đỉnh tiếp theo trong dãy.
- Do đó, tồn tại một đường đi từ đỉnh s đến đỉnh t.
Kết luận
Từ hai phần chứng minh trên, ta có thể kết luận rằng:
- Tồn tại đường đi từ đỉnh s đến đỉnh t khi và chỉ khi quá trình duyệt theo chiều sâu từ đỉnh s sẽ duyệt qua đỉnh t.
- Điều này cũng có nghĩa là quá trình duyệt theo chiều sâu từ đỉnh s sẽ đi qua tất cả các đỉnh nằm trong thành phần liên thông chứa đỉnh s, trong đó có đỉnh t.
Nói cách khác, DFS từ đỉnh s sẽ duyệt qua tất cả các đỉnh thuộc cùng một thành phần liên thông với đỉnh s.
Lời giải bài tập Chuyên đề Tin 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu hay, ngắn gọn khác: