GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - BÀI TẬP CHƯƠNG 4

Chia sẻ: Nguyễn Nhi | Ngày: | Loại File: PDF | Số trang:4

Thêm vào BST

Báo xấu

92
lượt xem 10
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài 1: Hội nghị bàn tròn Tổng thư ký Đại hội đồng Liên hợp quốc triệu tập một cuộc họp có N nhà ngoại giao của N tổ chức tham gia. Các đại diện ngoại giao được bố trí ngồi quanh một bàn tròn. Giữa một số tổ chức có quan hệ căng thẳng, vì vậy không thể xếp họ ngồi cạnh nhau được.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - BÀI TẬP CHƯƠNG 4

BÀI TẬP CHƯƠNG 4 Bài 1: Hội nghị bàn tròn Tổng thư ký Đại hội đồng Liên hợp quốc triệu tập một cuộc họp có N nhà ngoại giao của N tổ chức tham gia. Các đại diện ngoại giao được bố trí ngồi quanh một bàn tròn. Giữa một số tổ chức có quan hệ căng thẳng, vì vậy không thể xếp họ ngồi cạnh nhau được. Thông tin về quan hệ giữa các tổ chức được cho dưới dạng cặp số nguyên i, j nếu giữa 2 tổ chức này có quan hệ căng thẳng. Hãy lập trình giúp Tổng thư ký Liên hợp quốc bố trí chỗ ngồi quanh bàn họp. Các tổ chức được đánh số từ 1 tới N, 0 < N
57 10 7 10 8 10 9 34 00 Bài 2: Domino Cho trước N con cờ domino, hãy viết chương trình cho biết rằng có cách sắp N con cờ đó theo đúng luật domino sao cho các con cờ hình thành vòng tròn hay không, nếu có hãy chỉ ra một cách sắp. Dữ liệu vào: file DOMINO.INP Dòng đầu chứa số N N dòng tiếp theo, mỗi dòng chứa 2 số từ 0 đến 6 mang giá trị đại diện cho 2 đầu của domino. Dữ liệu ra: file DOMINO.OUT Dòng đầu chứa số 1 hoặc 0 tương ứng với sắp được quân domino thành vòng tròn và không sắp được. Nếu dòng đầu là 1 (tương ứng với sắp được) thì dòng thứ hai liệt kê ra N chỉ số của N con cờ domino theo thứ tự để sắp
thành vòng tròn. Nếu dòng đầu là 0 thì không có dòng thứ hai. Ví dụ: DOMINO.INP 4 53 56 23 62 DOMINO.OUT 1 1342 Bài 3: Kiểm tra đường Một trạm quảng đường giao thông phải chịu trách nhiêm về tình trạng của một mạng lưới giao thông nối giữa các điểm dân cư. Hàng tháng, họ phải cử một đội đi kiểm tra một vòng qua khắp mạng lưới để xem xét tình trạng hiện thời của các đường giao thông nhằm báo sửa chữa kịp thời nếu có nhu cầu. Hãy viết chương trình nhập vào mạng lưới giao thông và giúp trạm quyết định lộ trình của đội kiểm tra sao cho có thể thăm tất cả các con đường mà tổng chiều dài đoạn đường đi qua là nhỏ nhất.
Bài 4: Mã đi tuần Hãy cài đặt chương trình xác định lộ trình của con mã trên bàn cờ 8x8 ô bắt đầu từ ô (i, j) đi qua tất cả các ô của bàn cờ vàmỗi ô chỉ 1 lần duy nhất. Mở rộng với trường hợp bàn cờ kích thước NxN. Bài 5: Hội nghị bàn tròn Có 12 người ngồi chung 1 bàn tiệc tròn. Mỗi người có ít nhất 6 người quen. Hãy chỉ ra cách sắp xếp sao cho mỗi người đều ngồi cạnh người mình quen . Tổng quát, hãy sắp N người ngồi chung quanh bàn tròn sao cho mỗi người đều ngồi cạnh người mình quen. Biết mỗi người có ít nhất (N + 1)/2 người quen.