Президент хочет достроить несколько дорог так, чтобы из каждого города выходило одинаковое количество дорог. Какое наименьшее количество дорог ему надо будет достроить?
Для того чтобы из каждого города выходило одинаковое количество дорог, необходимо сделать так, чтобы степень (количество исходящих дорог) каждого города стала равной некоторому четному числу. Это делается потому, что в графе (где города – это вершины, а дороги – это ребра) сумма степеней всех вершин всегда четная, так как каждое ребро увеличивает степень двух вершин на 1.
Чтобы решить задачу, нужно выполнить следующие шаги:
- Подсчитать текущее количество дорог (или степень) для каждого города.
- Определить, какие города имеют нечетную степень.
- Свести нечетные степени к четным, добавляя дороги.
Из теоремы о нечетных степенях в графах следует, что:
- Количество вершин с нечетной степенью всегда четно.
- Для каждого нечетного города мы можем добавить дорогу к другому нечетному городу.
Таким образом, если у нас есть n городов с нечетной степенью, нам нужно добавить n/2 дорог, чтобы сделать степени всех городов четными.
Пример:
- Пусть у нас есть 5 городов с нечетной степенью. Мы можем соединить их парами, добавив 2 дороги.
Таким образом, наименьшее количество дорог, которые нужно будет достроить, равно половине количества городов с нечетными степенями (округленное вверх):
Наименьшее количество дорог = (Количество нечетных степеней) / 2.
