Перенумерация городов: задача для теории графов
Каждому городу в некоторой стране присвоен индивидуальный номер. Имеется список, в котором для каждой пары номеров указано, соединены города с данными номерами железной дорогой или нет. Оказалось, что, какие ни взять два номера M и N из списка, можно так перенумеровать города, что город с номером M получит номер N, но список по-прежнему будет верным. Верно ли, что, какие ни взять два номера M и N из списка, можно так перенумеровать города, что город с номером M получит номер N, город с номером N получит номер M, но список по-прежнему будет верным?
Показать ответ
Неверно.
Разобрать решение
Рассмотрим страну из 12 городов, соединённых дорогами так, как показано на рисунке.
Заметим, что рисунок симметричен относительно каждого диаметра, проходящего через середины малых хорд окружности, на которой лежат все города. Этими симметриями мы можем поменять номерами любую пару соседних по кругу городов. А с помощью нескольких симметрий каждый номер можно перевести в любой другой, то есть условие выполнено. Предположим, что нам удалось поменять номерами города 1 и 3 с сохранением списка соседних городов. Тогда их единственный общий сосед 2 обязан сохранить свой номер. Оставшемуся соседу 9 города 2 тоже придётся сохранить номер. Но у городов 3 и 9 два общих соседа (2 и 8), а у 1 и 9 – только один. Противоречие.
Обсуждение
0Комментариев пока нет.