Bài tập chương 3 - Lý thuyết đồ thị

BÀI TẬP CHƢƠNG 3
1. Cho ví dụ một đồ thị vô hƣớng G=(V,E), |V|=n.
a) Ghi ra danh sách thứ tự các đỉnh bằng cách duyệt theo chiều sâu.
b) Ghi ra danh sách thứ tự các đỉnh bằng cách duyệt theo chiều rộng.
2. Viết chƣơng trìnth nhập ma trận kề của đồ thị vô hƣớng G=(V,E), |V|=n.
a) In ra màn hình danh sách thứ tự các đỉnh bằng cách duyệt theo chiều sâu.
b) In ra màn hình danh sách thứ tự các đỉnh bằng cách duyệt theo chiều rộng.
3. Viết chƣơng trình ứng dụng duyệt đồ thị để giải bài toán đong rƣợu:
Có một can đang chứa a lít rƣợu và hai can rỗng có với dung tích là b và c lít.
Cần đong n lít vào một can rỗng.
a) Nhập a, b, c và n.
b) Phát sinh đồ thị gồm mỗi đỉnh là một trạng thái, lƣợng rƣợu trong mỗi can. Hai đỉnh
kề nhau nếu có thể chuyển từ trạng thái này sang trạng thái khác bằng cách đổ k lít rƣợu
đƣợc từ can A sang can B nếu hoặc A đang có k lít hoặc B đổ thêm k lít thì đầy.
c) Dùng một phƣơng pháp duyệt đồ thị để tìm một đƣờng đi từ đỉnh là trạng thái đầu
sang đỉnh là trạng thái cần có, nghĩa là một can có chứa đúng n lít.
d) In ra màn hình đƣờng đi chính là cách đong rƣợu cần tìm.
Lời giải không cần là cách đong nhanh nhất.
4. Viết chƣơng trình ứng dụng duyệt đồ thị để giải bài toán “Sói-Dê-Cải”:
Một ngƣời nông dân muốn đƣa ba thứ qua sông là: sói, dê và cải. Nhƣng có chiếc ghe
nhỏ chỉ chở đƣợc mỗi lần tối đa một thứ. Nếu không có ngƣời thì sói ăn dê, dê ăn cải.
Hãy chỉ ra cách để ngƣời nông dân đƣa ba thứ qua sông an toàn.
Lời giải không cần là cách qua lại sông ít nhất.
5. Viết chƣơng trình nhập ma trận kề của đồ thị vô hƣớng G=(V,E), |V|=n. Nhập đỉnh v và
in ra danh sách các đỉnh trong cùng một thành phần liên thông với đỉnh v.
6. Viết chƣơng trìnth nhập ma trận kề của đồ thị vô hƣớng G=(V,E), |V|=n. In ra danh sách
các đỉnh trong từng thành phần liên thông của G.
_______________________________________________________________________