khoahoc.vietjack.com
Xin chào! Vào học

Câu hỏi:

11/07/2024 332 Lưu

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.

Quảng cáo

Trả lời:

verified Giải bởi Vietjack

Để 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.

 

 


 

Đang tải chế độ Học...

Dành cho bạn Hot

Lớp 12 Vật lý
210 người thi tuần này

Trắc nghiệm Mô hình động học phân tử chất khí lớp 12 (có đáp án)

15 câu 1.9 K lượt thi Thi ngay →
Lớp 12 Tiếng Anh
138 người thi tuần này

Đề cương ôn tập giữa kì 1 Tiếng Anh 12 Global Success có đáp án

45 câu 1.3 K lượt thi Thi ngay →
Lớp 12 Sinh học
158 người thi tuần này

10 câu trắc nghiệm Sinh học 12 Kết nối tri thức Bài 8 có đáp án

10 câu 2 K lượt thi Thi ngay →
Lớp 12 Lịch sử
2,339 người thi tuần này

20 câu trắc nghiệm Lịch sử 12 Kết nối tri thức Bài 1 có đáp án

20 câu 22.4 K lượt thi Thi ngay →
Lớp 12 Địa lý
406 người thi tuần này

20 câu Trắc nghiệm Địa lý 12 Kết nối tri thức Bài 2 có đáp án

25 câu 6 K lượt thi Thi ngay →
Lớp 12 Tin học
574 người thi tuần này

15 câu Trắc nghiệm Tin học 12 Kết nối tri thức có đáp án

15 câu 13.2 K lượt thi Thi ngay →
Lớp 12 Giáo dục Kinh tế và Pháp luật
656 người thi tuần này

15 Câu trắc nghiệm KTPL 12 Kết nối tri thức Bài 1 có đáp án

15 câu 8.9 K lượt thi Thi ngay →

CÂU HỎI HOT CÙNG CHỦ ĐỀ

Lời giải

Ý tưởng chính của DFS: 

DFS hoạt động bằng cách bắt đầu từ một đỉnh nguồn, đánh dấu nó là đã thăm, sau đó tiếp tục đi sâu vào các đỉnh kề chưa thăm cho đến khi không thể đi tiếp được nữa. Khi không thể đi tiếp, thuật toán quay lui về các đỉnh trước đó để tiếp tục tìm kiếm các đường đi mới.

Lời giải

Để sửa đổi chương trình của thuật toán DFS không đệ quy sao cho nó in ra thông tin ngăn xếp hiện thời, phần tử được lấy ra từ ngăn xếp, và phần tử được đánh dấu để chuẩn bị cho bước sau, bạn có thể thực hiện như sau:

def dfs(graph, start):

   stack = [start]  # Ngăn xếp khởi tạo với đỉnh bắt đầu

   visited = set()  # Tập hợp các đỉnh đã được thăm

   while stack:

       # In thông tin ngăn xếp hiện thời

       print("Stack hiện thời:", stack)

       vertex = stack.pop()  # Lấy phần tử từ ngăn xếp

       print("Phần tử lấy ra từ ngăn xếp:", vertex)

       if vertex not in visited:

           print("Phần tử được đánh dấu để chuẩn bị cho bước sau (mark):", vertex)

           visited.add(vertex)  # Đánh dấu phần tử đã thăm

           # Thêm các đỉnh kề vào ngăn xếp

           for neighbor in reversed(graph[vertex]):

               if neighbor not in visited:

                    stack.append(neighbor)

   return visited

# Đồ thị mẫu dưới dạng danh sách kề

graph = {

    'A': ['B', 'C'],

    'B': ['A', 'D', 'E'],

    'C': ['A', 'F'],

    'D': ['B'],

    'E': ['B', 'F'],

    'F': ['C', 'E']

}

# Thực hiện DFS từ đỉnh 'A'

dfs(graph, 'A')

Giải thích:

- Ngăn xếp (Stack): Ban đầu ngăn xếp chứa đỉnh bắt đầu. Mỗi vòng lặp, bạn in ra ngăn xếp hiện thời.

- Phần tử được lấy ra từ ngăn xếp (vertex): Phần tử trên đỉnh ngăn xếp được lấy ra và in ra.

- Phần tử được đánh dấu (mark): Nếu phần tử chưa được thăm, nó được đánh dấu (thêm vào tập visited) và in ra.

Các bước thực hiện:

- Khởi tạo ngăn xếp với đỉnh bắt đầu (start).

- Trong khi ngăn xếp không rỗng:

In thông tin ngăn xếp hiện thời.

Lấy phần tử từ ngăn xếp và in ra.

Nếu phần tử chưa được thăm:

+ Đánh dấu phần tử đã thăm và in ra.

+ Thêm các đỉnh kề vào ngăn xếp theo thứ tự ngược lại để duyệt đúng thứ tự DFS.

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Lời giải

Bạn cần đăng ký gói VIP ( giá chỉ từ 250K ) để làm bài, xem đáp án và lời giải chi tiết không giới hạn.

Nâng cấp VIP

Xem trọn bộ đề thi 15 câu hỏi
Xem thêm