GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - CÁC BÀI TẬP KHÁC

Bài 1: Một khóa học gồm N môn học, môn học i phải học trong ti ngày. Giữa các môn học có mối quan hệ trước/sau: có môn học chỉ học được sau khi đã học một số môn học khác.
Nội dung trích xuất từ tài liệu:
GIÁO TRÌNH LÝ THUYẾT ĐỒ THỊ - CÁC BÀI TẬP KHÁC CÁC BÀI TẬP KHÁC Bài 1:Một khóa học gồm N môn học, môn học i phải học trong ti ngày. Giữa các mônhọc có mối quan hệ trước/sau: có môn học chỉ học được sau khi đã học một sốmôn học khác. Mối quan hệ đó được thể hiện bởi một mảng hai chiều A[i, j];i, j = 1, …, N trong đó A[i, j] = 1/0 và A[i, i] bằng 0 với mọi i, A[i, j] = 1 khi vàchỉ khi môn học i phải được dạy xong trước khi học môn j (ngày kết thúc môn iphải trứơc ngày bắt đầu môn j). Môn học i phải dạy trước môn học j nếu có mộtdãy môn học i1, i2, …, ik sao cho a[it, it+1] = 1, 1 Dữ liệu vào được cho bởi file text có tên MH.DAT trong đó số N ghi ở dòng thứnhất, trong nhóm N dòng tiếp theo, dòng thứ i ghi N số A[i, 1], …, A[i, N] dòngcuối cùng ghi N số nguyên dượng ti không lớn hơn 30, 1 4 1 0100 0010 0001 1000 1111Ví d ụ 2 MH.DAT TKB.DAT 7 010000 0 0 000100 0 22 000100 1 2 0 3 4 000011 0 1 8 0 0 0 0 0 0 12 0 13 22 000000 13 14 1 15 17 000000 0 1 2 2 2 8 4 10 1 3 23Bài 2:Giám đốc một công ty quyết định tổ chức buổi tiệc trà gặp gỡ toàn thể nhân viêntrong công ty. Công ty đựơc tổ chức theo mô hình phân cấp lãnh đạo và mối quanhệ thủ trưởng – nhân viên tạo thành cây có gốc là giám đốc. Để đảm bảo khôngkhí tự nhiên, giám đốc quyết định không để thủ trưởng và nhân viên dưới quyềnngồi cùng một bàn. P gọi là thủ trưởng của Q, nếu P là thủ trưởng trực tiếp của Qhoặc tồn tại dãy P1, P2, …, Pk (1 < k), sao cho P = P1, Q = Pk và Pi là thủ trưởngtrực tiếp của Pi+1 (i = 1, 2, … , k -1). Tất cả mọi người trong công ty được đánh sốtừ 1 đến N (N là tổng số người trong công ty với giám đốc bắt đầu từ 1). Yêu cầu: tính số lượng bàn ít nhất cần thiết để có thể bố trí cho mọi người ngồitheo yêu cầu nêu trên và cho một phương án bố trí người ở mỗi bàn. Dữ liệu vào: file text COMPANY.INP, dòng đầu tiên là số nguyên m – số ghếtối đa cho một bàn, dòng thứ 2 – số nguyên N – số người trong công ty, dòng thứba (và các dòng sau nếu cần) là dãy số nguyên, các số cách nhau ít nhất một dấucách hoặc nhóm ký tự xuống dòng, số nguyên thứ i trong dãy cho biết ai là thủtrưởng trực tiếp của nhân viên i. Giám đốc không có thủ trưởng nên số này bằng 0.2 0 1 9 9 9 2 2 1 1 7 8 8 10File kết quả COMPANY.OUT có thể có nội dung:513 3 4 510 6 87 9 11 1221 Bài 3:Trên bàn cờ NxN, hãy tìm cách sắp xếp số lượng tối đa các con hậu sao cho khôngcon nào có thể ăn con nào. Bài 4:Cho 1 đồ thị có hướng G, hãy tìm một tập hợp X0 ít nhất các đỉnh của G sao chomọi đỉnh i của G hoặc thuộc X0 hoặc i nối trựctiếp với định j thuộc X0. Làm bài 14trong trường hợp G vô hướng. Bài 5:Trên bàn cờ NxN, hãy tìm cách sắp xếp số lượng tối thiểu các con hậu sao cho mọiô cờ trên bàn cờ bị chiếu bởi ít nhất 1 con. Bài 6:Một ký túc xá nuôi 15 cô gái. Hàng ngày các cô đi chơi với nhau theo bộ 3. Hỏi cóthể đưa các cô đi chơi trong tối đa bao nhiêu ngày để không có 2 cô nào đi chungtrong một bộ 3 quá 1 lần.Hãy tổng quát hóa bài toán. Bài 7:Trong 1 trại giam ở thành phố A, mỗi nhà giam có một trạm gác độc lập, nhưngngười đứng gác, chẳng hạn ở nhà giam x0, cũng có thể thấy những gì xảy ra ở cáctrại giam x1, x2, x3… khác do các nhà giam này thông với x0 bởi 1 hành langthẳng. Giả sử biết các thông tin trên, hãy xác định số lượng tối thiểu các lính canhđể có thể quan sát được mọi nhà giam. Bài 8:Một số hải cảng x1, x2, x3… có các mặt hàng mà các hải cảng y1, y2, y3…cần đến.Lượng hàng có ở xi là si và yêu cầu hàng hóa của yi là di. Nếu có tàu đi từ xi tới yjthì ta ký hiệu cij là tổng lượng hàng mà các tàu có thể vận chuyển từ xi tới yj. Vậycó thể thỏa mãn mọi yêu cầu không? Tổ chức vận chuyển ra sao? Hãy viết chươngtrình giải quyết bài toán trên. Bài 9:Trong một cuộc du lịch, m gia đình phân nhau đi trên n xe. Các gia đình tươngứng có r1, r2, …, rm người và các xe tương ứng có s1, s2, …, sn chỗ ngồi. Hãy tìmcách phân phối sao cho 2 người cùng gia đình không ngồi chung một xe hoặc chobiết không thể làm như vậy. Bài 10:Trong một trường trung học, mỗi học sinh nữ có m bạn nam và mỗi học sinh namcó m bạn nữ. Hãy chỉ ra cách sắp xếp để mỗi cô gái có thể lần lượt khiêu vũ vớicác bạn trai của mình và các chàng trai có thể lần lượt khiêu vũ với các bạn gái củamình. Bài 11:Một nhà in phải sản xuất n cuốn sách bằng 2 máy: một để in, một để đóng sách.Gọi ak là thời gian cần cho việc in c ...