Топологическая теория графов: род и вложения

Топология позволяет рисовать графы на поверхностях разного рода без пересечений рёбер. Род определяет, сколько цветов достаточно - и это точная формула Хайвуда.

• **Печатные платы (PCB):** минимизация числа слоёв равносильна оценке рода графа соединений
• **Картографические задачи:** теорема о четырёх красках для плоскости, теорема Хайвуда для других поверхностей
• **Мобильные сети:** планарные подграфы соответствуют бесконфликтным частотным назначениям

Предварительные знания

• Extremal Graph Theory

Формула Эйлера и род поверхности

Картографы XIX века установили эмпирически: для карты на торе можно использовать до 7 цветов. Хайвуд в 1890 году доказал это строго. Для сравнения, на плоскости четырёх цветов всегда достаточно (теорема Эппела-Хакена, 1977, первое доказательство с проверкой ~1200 конфигураций на компьютере).

Раскраска карт и теорема Хайвуда

Формула Хайвуда 1890 года даёт верхнюю оценку на хроматическое число для графов рода g. Рингель и Юнгс в 1968 году доказали точность этой оценки для всех g >= 1, проверив 12 серий конструкций.

Ключевые идеи

• **Формула Эйлера:** V-E+F = 2-2g; g=0 сфера/плоскость, g=1 тор
• **Теорема Куратовского:** G непланарен тогда и только тогда, когда содержит подразбиение K_5 или K_{3,3}
• **Граница Хайвуда:** chi(G) <= H(g) = floor((7+sqrt(1+48g))/2); точна для g>=1 (Рингель-Юнгс)
• **Род K_n:** gamma(K_n) = ceil((n-3)(n-4)/12) по теореме Рингеля-Юнгса (1968)

Вопросы для размышления

• Как формула Эйлера V-E+F=2-2g позволяет доказать непланарность K_5?
• Почему граница Хайвуда не доказывает теорему о четырёх красках (случай g=0 отдельный)?
• Что означает вложение K_7 в тор - как конкретно расположить 7 вершин и 21 ребро без пересечений?

Связанные уроки

• alg-17-mst