Таблицы Брадиса

Дужина Комбинаторные структуры в топологии

Дужина Комбинаторные структуры в топологии

Элементы математики в задачах - Г. А. Мерзон

3 ■ 9 = 27, то есть нечетна, что невозможно. Следовательно, Я(3, 4) ^ 9.

Приведем теперь пример графа с 8 вершинами, в котором нет ни трех попарно соединенных, ни четырех попарно несоединенных вершин:

 

Итак, Я(3, 4) = 9.

Определение 9. Назовем расстоянием между вершинами связного графа наименьшую длину пути, соединяющего эти вершины (длина каждого ребра считается равной 1). Диаметром графа называется наибольшее расстояние между его вершинами.

Определение 10. Граф называется регулярным графом валентности к, если степень каждой его вершины равна к.

Определение 11. Графом Мура называется регулярный граф валент­ности к, диаметр которого не превосходит двух, а число вершин равно к2 +1.

Задача 20*. а) Докажите, что в регулярном графе валентности к и диаметра 2 не может быть больше к2 + 1 вершины.

б) Приведите примеры графов Мура при к = 1, 2, 3.

в) Существует ли граф Мура при к = 7? г**) Существует ли граф Мура при к = 57?

д)     Докажите, что ни при каких других значениях к не существует графов Мура.

Решение. а) Рассмотрим какую-нибудь вершину регулярного графа валентности к и диаметра 2. Она соединена с к вершинами, каждая из которых соединена еще с к — 1 вершиной. Если предположить, что все вышеупомянутые вершины различны, то мы получим, что их было к + к ■ (к — 1) + 1 = к2 + 1. Так как мы рассматриваем граф диаметра 2, то никаких других вершин в нашем графе быть не может.

б)     к = 1             к = 2                  к = 3

 

 

Є

 

в) Пока это открытая проблема.

г) Элементарное решение этой задачи авторам неизвестно. Набро­сок решения есть в материалах курса С. В. Дужина «Комбинаторные структуры в топологии» (НМУ, осенний семестр 1998 г.; см. http: //ium.mccme.ru/f98/combtop.html).