В Межгалактическую Империю входят n планет. Каждая планета управляется губернатором, подчиняющимся непосредственно Императору. Недавно Император объявил об открытии межпланетного…
В Межгалактическую Империю входят n планет. Каждая планета управляется губернатором, подчиняющимся непосредственно Императору. Недавно Император объявил об открытии межпланетного сообщения. В рамках этого проекта будут построены межпланетные космодромы и некоторые пары космодромов будут соединены двунаправленными рейсами. Каждый губернатор хочет, чтобы его планета была соединена ровно одним двунаправленным рейсом с какой-либо другой планетой (при отсутствии рейсов губернатор не получит финансирование из имперской казны на межпланетный космодром, при наличии рейсов с разных планет у губернатора возникнут проблемы с контролем транзитных потоков). По заданному n определите, какому наибольшему числу губернаторов удастся удовлетворить свои пожелания.
Для решения этой задачи можно представить ее как поиск максимального числа пар в графе, где вершины представляют планеты, а ребра — двунаправленные рейсы между ними. Каждый губернатор хочет, чтобы его планета была соединена с ровно одной другой планетой.
Чтобы максимизировать количество губернаторов, удовлетворённых их пожеланиям, давайте разберёмся с основными понятиями:
- Число планет: Обозначим количество планет как \( n \).
- Двунаправленные рейсы: Каждый назначенный рейс будет соединять две планеты.
Каждый губернатор хочет связать свою планету с точно одной другой. Это означает, что мы можем соединять планеты парами. Таким образом, чтобы удовлетворить как можно больше губернаторов, мы можем разделить все планеты на пары.
Анализ
- Если \( n \) — чётное число, то мы можем создать \( \frac{n}{2} \) пар.
- Если \( n \) — нечётное число, то мы сможем создать \( \frac{n - 1}{2} \) пар, а одна планета останется без пары.
Вывод
Таким образом, максимальное число губернаторов, чьи желания могут быть удовлетворены, формально можно описать так:
- Если \( n \) чётное: максимальное число губернаторов \( = \frac{n}{2} \)
- Если \( n \) нечётное: максимальное число губернаторов \( = \frac{n - 1}{2} \)
Эта логика позволит каждому губернатору из пары сохранить связь только с одной другой планетой, что удовлетворит требования каждого из них.
