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

Bài 1 : Các miền trên bảng Cho một bảng chữ nhật chia thành MxN ô vuông (M dòng, N cột). Mỗi ô vuông ghi một số nguyên dương (trong khoảng từ 1 đến 255). Một miền của bảng là tập hợp tất cả các ô có cùng giá trị số sao cho chúng đi được sang nhau bằng cách đi qua các ô có chung cạnh và có cùng giá trị số đang xét. | BÀI TẬP CHƯƠNG 3 ĩ Bài 1 Các miền trên bảng Cho một bảng chữ nhật chia thành MxN ô vuông M dòng N cột . Mỗi ô vuông ghi một số nguyên dương trong khoảng từ 1 đến 255 . Một miền của bảng là tập hợp tất cả các ô có cùng giá trị số sao cho chúng đi được sang nhau bằng cách đi qua các ô có chung cạnh và có cùng giá trị số đang xét. Địa chỉ của một miền là tọa độ dòng cột của ô đầu tiên thuộc miền theo thứ tự duyệt từ trái sang phải và từ trên xuống dưới. Diện tích của một miền là số ô thuộc miền đó. Thí dụ bảng Cần xác định Số miền của mảng. . Miền có diện tích lớn nhất chỉ rõ giá trị diện tích và địa chỉ của miền . Dữ liệu vào cho trong file văn bản tên file đọc từ bàn phím có dạng M N A 1 1 A 1 2 .A 1 N A 2 1 A 2 2 .A 2 N A M 1 A M 2 .A M N trong đó A i j là giá trị số của ô i j các số trên cùng một dòng ghi cách nhau ít nhất một dấu trắng. Yêu cầu chương trình thiết kế theo menu gồm các chức năng Đọc dữ liệu vào từ file Giải bài toán bằng tìm kiếm theo chiều rộng. Giải bài toán bằng tìm kiếm theo chiều sâu. Kết thúc chương trình. Kết quả tìm đuợc đưa ra màn hình. Giới hạn kích thước M N 100. Bài 2. Cho một mạng N N 20 máy tính được đánh số từ 1 đến N. Sơ đồ mạng được cho bởi hệ gồm M kênh đoạn nối trực tiếp giữa một số cặp máy trong mạng m kênh tương ứng với m cặp. Cho biết chi phí truyền 1 đơn vị thông tin theo mỗi kênh của mạng. Người ta cần chuyển một bức thông điệp từ máy s đến máy t. Để đảm bảo an toàn người ta chuyển bức thông điện này theo hai đường truyền tin khác nhau tức không có kênh nào của mạng được sử dụng trong cả hai đường truyền tin cho phép hai đường truyền tin cùng đi qua một số máy tính . Chi phí của một đường truyền được hiểu là tổng chi phí trên các kênh của nó. Đơn giá đường truyền từ máy s sang máy t được tính như sau Với hai máy s và t cùng bức thông điệp có độ dài là 1 đơn vị thông tin đơn giá truyền cho cặp s t được tính bằng tổng chi phí chuyển thông điệp an toàn bằng tổng chi phí của hai đường truyền tin là nhỏ nhất. Người ta mong muốn .