MathNet 2005 — Phần 03 Câu hỏi 76

Ở một quốc gia có các thành phố $n+1$, có các chuyến bay hai chiều giữa một số thành phố này. Chuyến bay hai chiều giữa các thành phố $A$ và $B$ có nghĩa là trong cùng ngày có một chuyến bay từ $A$ đến $B$ cũng như một chuyến bay từ $B$ đến $A$, trong khi không có chuyến bay một chiều từ thành phố này đến thành phố khác. Có thể có nhiều hơn một chuyến bay hai chiều giữa hai thành phố. Chúng tôi biểu thị tổng số lần cất cánh từ thành phố $A$ trong vòng một ngày bằng $d_A$. Đối với tất cả các thành phố $A$ ngoại trừ thủ đô, một thành phố có $d_A \le n$. Hơn nữa, đối với hai thành phố bất kỳ $A$, $B$ đều khác thủ đô, một thành phố có $d_A + d_B \le n$, nếu không có chuyến bay hai chiều giữa $A$ và $B$. Không có hạn chế về số lượng chuyến bay từ thủ đô, điều này đương nhiên được bao gồm trong các thành phố $n+1$.
Tìm số lượng chuyến bay hai chiều tối đa có thể được thực hiện trong một ngày ở quốc gia này và xác định tất cả các lịch trình chuyến bay có số lượng chuyến bay hai chiều tối đa này.