Luận văn Các bài toán tối ưu trên đồ thị và ứng dụng

Tóm tắt Luận văn Các bài toán tối ưu trên đồ thị và ứng dụng: ... phải tham gia đúng pi nhĩm, hãy tìm cách phân phối với số người trong nhĩm cĩ nhiều sinh viên tham gia nhất là nhỏ nhất cĩ thể được. 3.1.5. Bài tốn lập lịch cho hội nghị Một hội nghị cĩ m tiểu ban, mỗi tiểu ban cần sinh hoạt trong một ngày tại phịng họp phù hợp với nĩ. Cĩ n phịng họp dàn...o trước nhỏ nhất cĩ thể. Điểm cần tìm được gọi là điểm Torricelli cho hệ n điểm cho trước. 14 Hình 3.3 Bài tốn Steiner: Cho trước một tập hợp hữu hạn n điểm trên mặt phẳng (hoặc trong khơng gian metric nào đĩ), hãy tìm mạng giao thơng với tổng độ dài nhỏ nhất nối các điểm này với nhau...t cơ sở nào đặt chân để chứng tỏ được rằng chỉ cĩ thể thêm tối đa 2 điểm Steiner để thiết kế được mạng giao thơng tối ưu cho hệ 4 điểm đã cho. Để thấy rằng quả thật mạng tối ưu với bài tốn n = 4 điểm chỉ cĩ khơng quá 2 điểm Steiner, ta buộc phải sử 19 dụng các kiến thức về cây. Trong phần...