Спичечные графы

Ксения Пахомова
«Квантик» №8, 2015

В «Квантике» № 10 за 2014 год мы рассказывали о гороховом конструкторе. Надеемся, что ты, дорогой читатель, построил множество многогранников, замков, мостов и других замечательных вещей.

А знаешь ли ты, что с помощью гороха и зубочисток строятся красивые и ажурные графы на плоскости, да и сами задачи теории графов изучаются веселее? Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены отрезками или дугами. Точки называются вершинами графа, а отрезки (дуги) — его рёбрами. В нашем случае вершины — горошины, прямые рёбра — зубочистки. В ходе конструирования получаются элегантные и прочные конструкции.

Методы теории графов завоевали признание не только математиков, но и инженеров, экономистов, психологов, лингвистов, биологов, химиков. Последние часто с помощью графов изображают молекулы различных веществ. Попробуй построить сам, например, молекулы воды, бутана и циклогексана:

Ты уже заметил, что все рёбра этих трёх молекулярных графов имеют одинаковую длину и не пересекаются? Такие графы в математике называются спичечными. Получили они своё название, потому что легко выкладываются на плоскости с помощью спичек.

Построить спичечные графы несложно. В конце прошлого века появилось большое число математических результатов по спичечным графам, которые во многом связаны с такими характеристиками, как количество вершин, набор степеней и другие.

Степенью вершины называется количество выходящих из неё рёбер. Если все степени у графа одинаковые, то он называется регулярным. Ниже изображены регулярные спичечные графы степени 0, 1, 2 и 3, соответственно.

В 1986 году Хейко Харборт нашёл регулярный спичечный граф, который получил его имя — граф Харборта. В нём 104 ребра и 52 вершины, степени которых равны четырём.

Интересной математической задачей является поиск наименьших спичечных графов, то есть графов, обладающих наименьшим количеством вершин и имеющих наперёд заданный набор степеней. Из приведённых выше регулярных графов про первые четыре доказано, что они наименьшие. А регулярных спичечных графов степени 5 и выше не существует.

Рассмотрим спичечные графы, у которых вершины имеют два различных значения степени {m, n}. Наименьший спичечный граф со степенями {0, n} — это объединение одной вершины и наименьшего спичечного графа степени n. Наименьший спичечный граф со степенями {1, n} — это граф-звезда с n + 1 вершинами.

Ниже в таблице представлены наименьшие известные спичечные графы со степенями {m, n}:

Минимальность графов из первой строки доказана. Попробуйте продолжить эту строку — постройте для каждого n = 9, 10, 11, ... граф со степенями {2, n}.

Посмотрите, как красивы наименьшие известные спичечные графы со степенями {4, 5}, {4, 6}, {4, 8}:

Кстати, попробуйте-ка быстро отыскать на первом из этих графов вершину степени 5.

Гэвин Теобальд нашёл наименьший известный спичечный граф со степенями {4, 7}:

Перед вами примеры наименьших известных спичечных графов со степенями {4, 9}, {4, 10}, {4, 11}:

Спичечный граф со степенями {4, 12} пока не найден. Возможно, что при n ≥ 12 спичечных графов со степенями {4, n} нет. А вот графов со степенями {m, n}, где m и n больше 5, точно не существует.

Имеются и другие задачи со спичечными графами, причём как на плоскости, так и в пространстве¹. И многие вопросы ещё остаются открытыми. Замечательно, что такое простое занятие, как конструирование из гороха, позволяет прикоснуться к серьёзным проблемам, которые волнуют современных математиков.

Напоследок приведём несколько не минимальных, но очень красивых спичечных графов.

¹ Подробнее о других задачах на спичечных графах можно прочитать на сайте Math Magic.

Художник Елена Цветаева