BÀI TẬP CHƯƠNG 5 Bài 1 : Mạng an toàn Cho một mạng N (N | BÀI TẬP CHƯƠNG 5 ĩ Bài 1 Mạng an toàn 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 mạng máy tính mạng truyền tin nói trên thỏa mãn tính chất an toàn theo nghĩa là từ một máy bất kỳ luôn truyền được một cách an toàn thông điệp tới một máy bất kỳ khác. Khi một mạng an toàn người ta tính được đơn giá của mạng là tổng đơn giá mọi đường truyền từ một máy bất kỳ tới một máy bất kỳ khác. Ma trận đơn giá của mạng là mảng hai chiều A có N dòng và N cột mà giá trị phần tử A i j chính là đơn giá từ máy i sang máy j. Câu 1 Cho trước một mạng hãy kiểm ra tính an toàn của mạng đó. Câu 2 Khi mạng không an toàn được phép bổ sung một số kênh truyền để nó trở thành an toàn. Đơn giá mỗi kênh truyền bổ sung theo được coi bằng hai lần giá trị cực đại đơn giá các kênh đã có. Mọi kênh bổ sung được coi có đơn giá như nhau. Hãy tìm cách bổ sung các kênh mới mà đơn giá mạng là nhỏ nhất. Câu 3 Khi mạng an toàn hoặc sau khi bổ sung kênh để mạng an toàn hãy in ra đơn giá mạng và ma trận đơn giá. Dữ liệu vào cho trong file với cấu trúc như sau Dòng đầu tiên ghi 2 số n m cách nhau bởi dấu cách. Mỗi dòng thứ i trong số m dòng tiếp theo ghi thông tin về kênh nối thứ i
