Hàm kiểm tra chu trình của đồ thị trên còn đúng không nếu đồ thị ban đầu là vô hướng?

Giải Chuyên đề Tin 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu - Kết nối tri thức

Luyện tập 1 trang 74 Chuyên đề Tin học 12: Hàm kiểm tra chu trình của đồ thị trên còn đúng không nếu đồ thị ban đầu là vô hướng?

Lời giải:

Để kiểm tra chu trình trong một đồ thị vô hướng, cách tiếp cận có thể khác so với đồ thị có hướng. Trong trường hợp đồ thị vô hướng, mỗi cạnh được coi là một liên kết giữa hai đỉnh, không có khái niệm đỉnh cha và đỉnh con.

Một cách để kiểm tra chu trình trong đồ thị vô hướng là sử dụng duyệt DFS nhưng cần phải theo dõi đỉnh trước đó mà không phải là đỉnh hiện tại (cha của đỉnh hiện tại) để tránh lặp lại qua cùng một cạnh. Nếu trong quá trình duyệt, gặp một đỉnh đã được thăm trước đó và không phải là đỉnh cha của đỉnh hiện tại, thì có thể kết luận rằng đồ thị chứa chu trình.

Lời giải bài tập Chuyên đề Tin 12 Bài 15: Thực hành duyệt đồ thị theo chiều sâu hay, ngắn gọn khác:

• Luyện tập 1 trang 74 Chuyên đề Tin học 12: Hàm kiểm tra chu trình của đồ thị trên còn đúng không nếu đồ thị ban đầu ....

• Luyện tập 2 trang 74 Chuyên đề Tin học 12: Viết lại hàm kiểm tra chu trình DFS_acyclic(Adj,s) trong chương trình ....

• Vận dụng 1 trang 74 Chuyên đề Tin học 12: Sửa lại chương trình bổ sung thông báo nếu hệ thống chuyên đề không hợp lí ....

• Vận dụng 2 trang 74 Chuyên đề Tin học 12: Mở rộng bài tập trên cho đồ thị có hướng bất kì G = (V, E), được biểu diễn bởi ma trận kề A ....

Xem thêm lời giải bài tập Chuyên đề học tập Tin học 12 Kết nối tri thức hay, ngắn gọn khác:

• Chuyên đề Tin học 12 Bài 12: Biểu diễn đồ thị

• Chuyên đề Tin học 12 Bài 13: Thực hành thiết lập đồ thị

• Chuyên đề Tin học 12 Bài 14: Kĩ thuật duyệt đồ thị theo chiều sâu

• Chuyên đề Tin học 12 Bài 16: Kĩ thuật duyệt đồ thị theo chiều rộng

• Chuyên đề Tin học 12 Bài 17: Thực hành duyệt đồ thị tổng hợp

Xem thêm các tài liệu học tốt lớp 12 hay khác:

• Giải Chuyên đề Tin học 12 Kết nối tri thức
• Giải Chuyên đề Tin học 12 Chân trời sáng tạo
• Giải Chuyên đề Tin học 12 Cánh diều
• Giải lớp 12 Kết nối tri thức (các môn học)
• Giải lớp 12 Chân trời sáng tạo (các môn học)
• Giải lớp 12 Cánh diều (các môn học)

---