Сірникові графи

У «Квантиці» № 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, точно не існує.

Є й інші завдання із сірниковими графами, причому як на площині, так і в ^{просторі 1}. І багато питань ще залишаються відкритими. Чудово, що таке просте заняття, як конструювання з гороху, дозволяє доторкнутися до серйозних проблем, які хвилюють сучасних математиків.

Наостанок наведемо кілька не мінімальних, але дуже красивих сірникових графів.

¹ Докладніше про інші завдання на сірникових графах можна прочитати на сайті Math Magic.

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