Полезная информация

Решали с учениками олимпиадную задачку:

В стране N городов, некоторые города соединены дорогами, причём из каждого города выходит ровно 3 дороги. Известно, что по дорогам страны можно добраться из любого города в любой другой город этой страны, заезжая по пути не более чем в 1 другой город. Какое наибольшее количество городов может быть в этой стране?

Смогли найти подходящий циклический граф из 8 городов (вершин). Это была замкнутая цепочка вершин, соединенных также и перекрестно. Однако в ответе было - 10 городов!

Решение начали искать с новой силой, но кавалерийская атака (в виде метода проб и ошибок) не помогла. Сменили подход - от циклического представления графа перешли к представлению в виде дерева, незамкнутые вершины которого на нижнем ярусе замыкались опять-таки комбинаторно. Очевидно, что не было смысла рассматривать деревья с количеством ярусов от вершины более двух, т.к. в этом случае переезд из города в город становился заведомо длиннее двух ребер. 

Начали осаду задачи с помощью регулярного подхода. Стали рассматривать варианты деревьев с количеством вершин на ярусах в виде следующих троек - (1, 3, 6), (1, 5, 4), (1, 4, 5) и т.д.

Некоторые из неудачных вариантов показаны на рисунке:

И наконец, вариант (1, 7, 2) сработал. Вот решение:

Фигура получилась не очень красивая и стремление к эстетичности заставило поискать изоморфные варианты графа. Тем более, геометрический калькулятор GeoGebra позволяет это делать легко и увлекательно.

Результат последовательных трансформаций представлен на рисунках:

Согласитесь, граф получился очень красивый. Естественно, мы поискали его через Яндекс. И вот он - оказывается, это известный граф Петерсена, - минимальный 10-вершинный кубический граф с индексом самопересечения 2.

Появился стимул изучить и другие красивые графы, перекликающиеся с данной темой.