Giả sử gọi BFS(Adj,s) là chương trình duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh s. Khi đó với mọi đỉnh v thuộc V, hàm BFS(Adj,s) sẽ duyệt qua đỉnh v khi và chỉ khi tồn tại đường đi từ s đến v.
Câu hỏi 1: Mệnh đề sau đúng hay sai?
Giả sử gọi BFS(Adj,s) là chương trình duyệt đồ thị theo chiều rộng bắt đầu từ đỉnh s. Khi đó với mọi đỉnh v thuộc V, hàm BFS(Adj,s) sẽ duyệt qua đỉnh v khi và chỉ khi tồn tại đường đi từ s đến v.
Mệnh đề sau là đúng.
- Lý do:
Mệnh đề này có thể được chứng minh tương tự như cách chứng minh tính chất của DFS đối với đường đi trong đồ thị. Cụ thể:
- Chứng minh:
Chúng ta cần chứng minh hai điều sau:
- Nếu tồn tại đường đi từ đỉnh sss đến đỉnh v, thì quá trình duyệt BFS từ đỉnh sss sẽ duyệt qua đỉnh v.
- Nếu quá trình duyệt BFS từ đỉnh sss duyệt qua đỉnh v, thì tồn tại đường đi từ đỉnh sss đến đỉnh v.
- Chứng minh điều 1:
Nếu tồn tại đường đi từ đỉnh s đến đỉnh v:
- Giả sử tồn tại một đường đi từ đỉnh sss đến đỉnhv. Điều này có nghĩa là có một dãy các đỉnh s=v0,v1,v2,…,vk sao cho (vi,vi+1) ∈ E
- Khi thực hiện BFS từ đỉnh sss, BFS sẽ thăm tất cả các đỉnh mà nó có thể truy cập được từ sss. BFS duyệt các đỉnh theo từng mức (level) một cách rộng nhất có thể trước khi chuyển sang mức tiếp theo.
- Đ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 v.
- Do đó, nếu tồn tại đường đi từ đỉnh s đến đỉnh v, BFS sẽ chắc chắn thăm đỉnh v trong quá trình duyệt.
- Chứng minh điều 2:
Nếu quá trình duyệt BFS từ đỉnh sss duyệt qua đỉnh v:
- Giả sử quá trình duyệt BFS từ đỉnh sss duyệt qua đỉnh v. Điều này có nghĩa là BFS đã bắt đầu từ đỉnh sss và theo các cạnh của đồ thị, nó đã đến đỉnh v.
- BFS 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 BFS đều là di chuyển qua các cạnh của đồ thị.
- Nếu BFS đã thăm đỉnh v từ đỉnh s, điều đó có nghĩa là có một dãy các đỉnh bắt đầu từ sss và kết thúc tại v 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 v.
Giải những bài tập khác
Giải bài tập những môn khác
Môn học lớp 12 kết nối tri thức
Soạn ngữ văn 12 kết nối tri thức
Văn mẫu 12 kết nối tri thức
Soạn ngữ văn 12 tập 1 kết nối tri thức
Soạn ngữ văn 12 tập 2 kết nối tri thức
Giải toán 12 kết nối tri thức
Giải toán 12 tập 1 kết nối tri thức
Giải toán 12 tập 2 kết nối tri thức
Giải vật lí 12 kết nối tri thức
Giải hóa học 12 kết nối tri thức
Giải sinh học 12 kết nối tri thức
Giải lịch sử 12 kết nối tri thức
Giải địa lí 12 kết nối tri thức
Giải kinh tế pháp luật 12 kết nối tri thức
Giải Công nghệ Lâm nghiệp - Thủy sản 12 kết nối tri thức
Giải Công nghệ điện - điện tử 12 Kết nối tri thức
Giải tin học 12 định hướng Tin học ứng dụng kết nối tri thức
Giải tin học 12 định hướng Khoa học máy tính kết nối tri thức
Giải âm nhạc 12 kết nối tri thức
Giải mĩ thuật 12 kết nối tri thức
Giải quốc phòng an ninh 12 kết nối tri thức
Giải hoạt động trải nghiệm hướng nghiệp 12 kết nối tri thức
Môn học lớp 12 chân trời sáng tạo
Soạn ngữ văn 12 chân trời sáng tạo
Văn mẫu 12 chân trời sáng tạo
Soạn ngữ văn 12 tập 1 chân trời sáng tạo
Soạn ngữ văn 12 tập 2 chân trời sáng tạo
Giải toán 12 chân trời sáng tạo
Giải toán 12 tập 1 chân trời sáng tạo
Giải toán 12 tập 2 chân trời sáng tạo
Giải vật lí 12 chân trời sáng tạo
Giải hóa học 12 chân trời sáng tạo
Giải sinh học 12 chân trời sáng tạo
Giải lịch sử 12 chân trời sáng tạo
Giải địa lí 12 chân trời sáng tạo
Giải kinh tế pháp luật 12 chân trời sáng tạo
Giải tin học 12 định hướng Tin học ứng dụng chân trời sáng tạo
Giải tin học 12 định hướng Khoa học máy tính chân trời sáng tạo
Giải âm nhạc 12 chân trời sáng tạo
Giải mĩ thuật 12 chân trời sáng tạo
Giải quốc phòng an ninh 12 chân trời sáng tạo
Giải hoạt động trải nghiệm hướng nghiệp 12 chân trời sáng tạo bản 1
Giải hoạt động trải nghiệm hướng nghiệp 12 chân trời sáng tạo bản 2
Môn học lớp 12 cánh diều
Soạn ngữ văn 12 cánh diều
Văn mẫu 12 cánh diều
Soạn ngữ văn 12 tập 1 cánh diều
Soạn ngữ văn 12 tập 2 cánh diều
Giải toán 12 cánh diều
Giải toán 12 tập 1 cánh diều
Giải toán 12 tập 2 cánh diều
Giải vật lí 12 cánh diều
Giải hóa học 12 cánh diều
Giải sinh học 12 cánh diều
Giải lịch sử 12 cánh diều
Giải địa lí 12 cánh diều
Giải kinh tế pháp luật 12 cánh diều
Giải Công nghệ điện - điện tử 12 Cánh diều
Giải Công nghệ Lâm nghiệp - Thủy sản 12 cánh diều
Giải tin học 12 định hướng Tin học ứng dụng cánh diều
Giải tin học 11 định hướng Khoa học máy tính cánh diều
Giải âm nhạc 12 cánh diều
Giải mĩ thuật 12 cánh diều
Giải quốc phòng an ninh 12 cánh diều
Giải hoạt động trải nghiệm hướng nghiệp 12 cánh diều
Giải chuyên đề học tập lớp 12 kết nối tri thức
Giải chuyên đề Ngữ văn 12 Kết nối tri thức
Giải chuyên đề Toán 12 Kết nối tri thức
Giải chuyên đề Vật lí 12 Kết nối tri thức
Giải chuyên đề Hóa học 12 Kết nối tri thức
Giải chuyên đề Sinh học 12 Kết nối tri thức
Giải chuyên đề Kinh tế pháp luật 12 Kết nối tri thức
Giải chuyên đề Lịch sử 12 Kết nối tri thức
Giải chuyên đề Địa lí 12 Kết nối tri thức
Giải chuyên đề Tin học ứng dụng 12 Kết nối tri thức
Giải chuyên đề Khoa học máy tính 12 Kết nối tri thức
Giải chuyên đề Công nghệ 12 Điện - điện tử Kết nối tri thức
Giải chuyên đề Công nghệ 12 Lâm nghiệp thủy sản Kết nối tri thức
Giải chuyên đề học tập lớp 12 chân trời sáng tạo
Giải chuyên đề Ngữ văn 12 Chân trời sáng tạo
Giải chuyên đề Toán 12 Chân trời sáng tạo
Giải chuyên đề Vật lí 12 Chân trời sáng tạo
Giải chuyên đề Hóa học 12 Chân trời sáng tạo
Giải chuyên đề Sinh học 12 Chân trời sáng tạo
Giải chuyên đề Kinh tế pháp luật 12 Chân trời sáng tạo
Giải chuyên đề Lịch sử 12 Chân trời sáng tạo
Giải chuyên đề Địa lí 12 Chân trời sáng tạo
Giải chuyên đề Tin học ứng dụng 12 Chân trời sáng tạo
Giải chuyên đề Khoa học máy tính 12 Chân trời sáng tạo
Giải chuyên đề Công nghệ 12 Điện - điện tử Chân trời sáng tạo
Giải chuyên đề Công nghệ 12 Lâm nghiệp thủy sản Chân trời sáng tạo
Giải chuyên đề học tập lớp 12 cánh diều
Giải chuyên đề Ngữ văn 12 Cánh diều
Giải chuyên đề Toán 12 Cánh diều
Giải chuyên đề Vật lí 12 Cánh diều
Giải chuyên đề Hóa học 12 Cánh diều
Giải chuyên đề Sinh học 12 Cánh diều
Giải chuyên đề Kinh tế pháp luật 12 Cánh diều
Giải chuyên đề Lịch sử 12 Cánh diều
Giải chuyên đề Địa lí 12 Cánh diều
Giải chuyên đề Tin học ứng dụng 12 Cánh diều
Giải chuyên đề Khoa học máy tính 12 Cánh diều
Giải chuyên đề Công nghệ 12 Điện - điện tử Cánh diều
Giải chuyên đề Công nghệ 12 Lâm nghiệp thủy sản Cánh diều
Bình luận