Элементы Элементы большой науки

Поставить закладку

Напишите нам

Карта сайта

Содержание
Энциклопедия
Новости науки
LHC
Картинка дня
Библиотека
Методология науки
Избранное
Публичные лекции
Лекции для школьников
Библиотека «Династии»
Интервью
Опубликовано полностью
В популярных журналах
«В мире науки»
«Знание — сила»
«Квант»
«Квантик»
«Кот Шрёдингера»
«Наука и жизнь»
«Наука из первых рук»
«Популярная механика»
«Потенциал»: Химия. Биология. Медицина
«Потенциал»: Математика. Физика. Информатика
«Природа»
«Троицкий вариант»
«Химия и жизнь»
«Что нового...»
«Экология и жизнь»
Из Книжного клуба
Статьи наших друзей
Статьи лауреатов «Династии»
Выставка
Происхождение жизни
Видеотека
Книжный клуб
Задачи
Масштабы: времена
Детские вопросы
Плакаты
Научный календарь
Наука и право
ЖОБ
Наука в Рунете

Поиск

Подпишитесь на «Элементы»



ВКонтакте
в Твиттере
в Фейсбуке
на Youtube
в Instagram



Новости науки

 
20.02
Экстракт из старых сородичей ускоряет старение

16.02
Открыт бензольный дикатион — пирамида с шестикоординационным углеродом

15.02
Детектор ATLAS увидел рассеяние света на свете

14.02
Кембрийское ископаемое Saccorhytus поместили в основание эволюционной линии вторичноротых

13.02
Эволюционные последствия генных дупликаций удалось оценить количественно






Главная / Библиотека / В популярных журналах / «Квантик» версия для печати

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

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

"Спичечные графы" («Квантик» №8, 2015)

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

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

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

Молекулы воды, бутана и циклогексана («Квантик» №8, 2015)

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

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

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

Регулярные спичечные графы степени 0, 1, 2 и 3 («Квантик» №8, 2015)

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

Граф Харборта («Квантик» №8, 2015)

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

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

Наименьшие спичечные графы со степенями {0, n} и {1, n} («Квантик» №8, 2015)

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

Наименьшие известные спичечные графы со степенями {m, n} («Квантик» №8, 2015)

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

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

Наименьшие известные спичечные графы со степенями {4, 5}, {4, 6}, {4, 8} («Квантик» №8, 2015)

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

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

Наименьший известный спичечный граф со степенями {4, 7} («Квантик» №8, 2015)

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

Наименьшие известные спичечные графы со степенями {4,9}, {4,10}, {4,11} («Квантик» №8, 2015)

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

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

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

Примеры неминимальных спичечных графов («Квантик» №8, 2015)

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

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


Комментировать


 


при поддержке фонда Дмитрия Зимина - Династия