Граф Голомба Граф Голомба — это полиэдральный граф с 10 вершинами и 18 рёбрами, названный в честь математика Соломона Вольфа Голомба. Он относится к классу графов единичных расстояний: его можно изобразить на плоскости так, что длина каждого ребра будет равна 1.
Суть и роль в математике Граф Голомба тесно связан с задачей о хроматическом числе плоскости (задачей Нелсона — Эрдёша — Хадвигера). Её формулировка удивительно проста: сколько цветов нужно, чтобы раскрасить все точки плоскости так, чтобы любые две точки на расстоянии 1 оказались разного цвета? При этом ответ остаётся одной из интригующих загадок математики.
Граф Голомба даёт важный фрагмент ответа: он показывает, что трёх цветов точно недостаточно. Его хроматическое число равно 4 — то есть для раскраски его 10 вершин так, чтобы соединённые ребром вершины имели разные цвета, нужно минимум 4 цвета. Отсюда следует, что и для всей плоскости потребуется не менее 4 цветов.
Этот результат похож на эффект от другого известного примера — веретена Мозера: оно тоже требует 4 цвета и служит нижней оценкой для хроматического числа плоскости. Позже, в 2018 году, Обри ди Грей построил более сложный граф, который потребовал уже 5 цветов, тем самым повысив нижнюю оценку. Но именно компактные и изящные конструкции вроде графа Голомба ценятся за наглядность: они демонстрируют, как локальные геометрические ограничения (расстояние 1) приводят к жёстким комбинаторным последствиям.
Основные свойства
Вершины: 10. Рёбра: 18. Хроматическое число: 4. Дробное хроматическое число: 310. Тип: граф единичных расстояний, полиэдральный (соответствует скелету выпуклого многогранника). Геометрическая реализация: допускает вложение на плоскость с единичными рёбрами; координаты вершин выражаются через квадратичное поле Q.
Конструкция Граф можно построить, комбинируя внешний многоугольный контур с внутренней структурой — например, повёрнутым многоугольником или звездой. Такой приём создаёт симметричную фигуру, где все рёбра имеют длину 1. Эта идея близка к построению обобщённых графов Петерсена и помогает наглядно показать, как геометрия задаёт структуру связей.
Полиэдральность графа означает, что он соответствует рёберному скелету некоторого выпуклого многогранника. То есть граф Голомба можно воспринимать не только как плоскую схему, но и как «каркас» трёхмерного тела: вершины — углы, рёбра — линии, соединяющие их.
Мнения экспертов Александр Сойфер в книге The Mathematical Coloring Book подчёркивает, что именно небольшие, но тщательно подобранные конфигурации способны радикально менять интуицию о бесконечных объектах: иногда достаточно аккуратного рисунка на листе бумаги, чтобы увидеть, что простая идея сталкивается с неожиданной сложностью.
Пол Эрдёш любил задачи, которые легко объяснить даже школьнику, но которые десятилетиями остаются нерешёнными. Задача о хроматическом числе как раз из таких: её формулировка понятна всем, а решение ускользает от математиков, и именно примеры вроде графа Голомба помогают шаг за шагом продвигаться вперёд.
Значение Граф Голомба важен сразу в нескольких смыслах:
Как нижняя оценка. Он строго доказывает, что хроматическое число плоскости не меньше 4. Как иллюстрация метода. На его примере удобно объяснять, как графы единичных расстояний связывают геометрию и комбинаторику. Как учебный и демонстрационный объект. Компактность (всего 10 вершин) и симметрия делают его отличным примером для лекций, олимпиад и популяризации математики.
Таким образом, граф Голомба — это не просто набор точек и линий, а маленький, но выразительный аргумент в большой математической дискуссии. Он показывает, как простые правила (расстояние 1 между точками) могут порождать нетривиальные ограничения и открывать путь к глубоким результатам.
Построение
Метод построения графа Голомба как графа единичных расстояний, заключающийся в рисовании внешнего правильного многоугольника, соединённого с внутренним повёрнутым многоугольником или звездой, используется также для представления графа Петерсена и обобщённых графов Петерсена. Как и в случае веретена Мозера, координаты вложения графа Голомба с единичными расстояниями могут быть представлены в квадратичном поле .
Дробная раскраска Дробное хроматическое число графа Голомба равно 10/3. Факт, что это число не меньше указанного значения, следует из того, что граф имеет 10 вершин и максимум три из них могут быть в каком-либо независимом множестве. Факт, что это значение не превосходит этой величины, следует из того, что можно найти 10 независимых множеств из трёх вершин, таких, что каждая вершина находится ровно в трёх таких множествах. Это дробное хроматическое число меньше, чем 7/2 у веретена Мозера и меньше, чем дробное хроматическое число графа единичных расстояний плоскости, которое лежит между 3,6190 и 4,3599.
Литература
Ссылки
Категория:Планарные графы Категория:Графы, имеющие собственные названия