Число Хивуда

Перейти к навигации Перейти к поиску

Число Хивуда поверхности — это определённая верхняя граница для максимального числа цветов, необходимых для раскраски любого графа, вложенного в поверхность. В 1890 году Хивуд доказал для всех поверхностей, за исключением сферы, что не более чем

H(S)=\left\lfloor {\frac {7+{\sqrt {49-24e(S)}}}{2}}\right\rfloor

цветов необходимо для раскраски любого графа, вложенного в поверхность с эйлеровой характеристикой $e(S)$ ^[1]. Случай сферы соответствует гипотезе о четырёх красках, которую доказали Кеннет Аппель^[англ.] и Вольфганг Хакен в 1976 году^[2]^[3]. Число $H(S)$ стало известно как число Хивуда в 1976 году.

Франклин доказал, что хроматическое число графа, вложенного в бутылку Кляйна, может достигать $6$ , но никогда его не превосходит^[4]. Позднее было доказано в работах Герхарда Рингеля и Дж. У. Т. Янгса, что полный граф с $H(S)$ вершинами можно вложить в поверхность $S$ , за исключением случая, когда $S$ является бутылкой Кляйна^[5]. Это показывает, что граница Хивуда не может быть улучшена.

Например, полный граф с $7$ вершинами можно вложить в тор следующим образом:

Примечания

↑ Heawood, 1890, с. 322–339.
↑ Appel, Haken, 1977, с. 429–490.
↑ Appel, Haken, Koch, 1977, с. 491–567.
↑ Franklin, 1934, с. 363–379.
↑ Ringel, Youngs, 1968, с. 438–445.

Литература

Béla Bollobás. Graph Theory: An Introductory Course. — Springer-Verlag, 1979. — Т. volume 63. — (GTM). — ISBN 0-387-90399-2.
Thomas L. Saaty, Paul Chester Kainen. The Four-Color Problem: Assaults and Conquest. — Dover, 1986.
Heawood P. J. Map colouring theorems // Quarterly J. Math. Oxford Ser.. — 1890. — Т. 24.
Kenneth Appel, Wolfgang Haken. Every Planar Map is Four Colorable. I. Discharging // Illinois Journal of Mathematics. — 1977. — Т. 21, вып. 3.
Kenneth Appel, Wolfgang Haken, John Koch. Every Planar Map is Four Colorable. II. Reducibility // Illinois Journal of Mathematics. — 1977. — Т. 21, вып. 3.
Franklin P. A Six Color Problem // Journal of Mathematics and Physics. — 1934. — Т. 13, вып. 1–4. — doi:10.1002/sapm1934131363.
Gerhard Ringel, Youngs J. W. T. Solution of the Heawood Map-Coloring Problem // Proceedings of the National Academy of Sciences. — 1968. — Т. 60, № 2. — ISSN 0027-8424. — doi:10.1073/pnas.60.2.438.

Похожие исследовательские статьи

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

Раскраска графа — теоретико-графовая конструкция, частный случай разметки графа. При раскраске элементам графа ставятся в соответствие метки с учётом определённых ограничений; эти метки традиционно называются «цветами». В простейшем случае такой способ окраски вершин графа, при котором любым двум смежным вершинам соответствуют разные цвета, называется раскраской вершин. Аналогично раскраска рёбер присваивает цвет каждому ребру так, чтобы любые два смежных ребра имели разные цвета. Наконец, раскраска областей планарного графа назначает цвет каждой области, так, что каждые две области, имеющие общую границу, не могут иметь одинаковый цвет.

Рёберная раскраска — назначение «цветов» рёбрам графа таким образом, что никакие два смежных ребра не имеют один и тот же цвет. Рёберная раскраска — это один из видов различных типов раскраски графов. Задача рёберной раскраски задаётся вопросом, можно ли раскрасить рёбра заданного графа максимум в $\text{[math]}$ различных цветов для заданного значения $\text{[math]}$ или для минимального возможного числа цветов. Минимальное требуемое число цветов для раскраски рёбер заданного графа называется хроматическим индексом графа. Например, рёбра графа на иллюстрации можно раскрасить в три цвета, но нельзя раскрасить в два, так что граф имеет хроматический индекс 3.

Обхват графа — длина наименьшего цикла, содержащегося в данном графе. Если граф не содержит циклов, его обхват по определению равен бесконечности. Например, 4-цикл (квадрат) имеет обхват 4. Квадратная решётка имеет также обхват 4, а треугольная сетка имеет обхват 3. Граф с обхватом четыре и более не имеет треугольников.

В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы.

В теории графов под ациклической раскраской понимается (правильная) раскраска вершин, в которой любой двуцветный подграф не имеет циклов. Ациклическим хроматическим числом A(G) графа G называется наименьшее число цветов, необходимое в любой ациклической раскраске G.

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

Веретено Мозера — неориентированный граф, названный в честь математиков Лео Мозера и его брата Вильяма, имеющий семь вершин и одиннадцать рёбер. Он является графом единичных расстояний, требующим четыре цвета в любой раскраске, и его существование используется для доказательства того, что хроматическое число плоскости равно по меньшей мере четырём.

Граф Хивуда — ненаправленный граф с 14 вершинами и 21 ребром, названный в честь Перси Джона Хивуда.

Куби́ческий граф — граф, в котором все вершины имеют степень три. Другими словами, кубический граф является 3-регулярным. Кубические графы называются также тривалентными.

Теорема Визинга — утверждение теории графов, согласно которому рёбра любого простого неориентированного графа могут быть раскрашены в число цветов, максимум на единицу большее максимальной степени вершин $\text{[math]}$ графа. Поскольку $\text{[math]}$ цветов достаточно всегда, все неориентированные графы можно разбить на два класса — графы «первого класса», для которых $\text{[math]}$ цветов достаточно, и «второго класса», для которых необходимо $\text{[math]}$ цветов.

<span class="mw-page-title-main">Тороидальный граф</span> граф, который можно уложить на тор

Тороида́льный граф — граф, который можно нарисовать на торе так, что его рёбра пересекаются только по общим вершинам.

Многогранник Силаши (Силашши) — пример невыпуклого многогранника, топологически эквивалентного тору. Назван по имени венгерского математика Лайоша Силаши, обнаружившего многогранник в 1977 году.

В теории графов граф Франклина — это 3-регулярный граф с 12 вершинами и 18 рёбрами.

Гипотеза Хивуда, или теорема Рингеля — Янгса даёт нижнюю границу для числа цветов, которые необходимы для раскраски графа на поверхности с заданным родом. Эта граница называется хроматическим числом поверхности или числом Хивуда. Для поверхностей рода 0, 1, 2, 3, 4, 5, 6, 7, ..., требуемое число цветов равно 4, 7, 8, 9, 10, 11, 12, 12, .... A000934,.

1-планарный граф — граф, который может быть нарисован в евклидовой плоскости таким образом, что каждое ребро имеет максимум одно пересечение с единственным другим ребром. Естественное обобщение — $\text{[math]}$ -планарный граф.

Однозначно раскрашиваемый граф — это k-цветный граф, допускающий только одну (правильную) k-раскраску.

Герхард Рингель — немецкий математик; один из родоначальников теории графов. Внёс значительный вклад в доказательство гипотезы Хивуда, задачи тесно связаной с задачей четырёх красок.

Граф Пуссена — это планарный граф с 15 вершинами и 39 рёбрами. Он назван именем Шарля Жана де Ла Валле-Пуссена.

Вольфганг Хакен — немецкий и американский математик, специалист по топологии, профессор Иллинойсского университета в Урбане-Шампейне, лауреат премии Фалкерсона (1979).

Эта страница основана на статье Википедии.
Текст доступен на условиях лицензии CC BY-SA 4.0; могут применяться дополнительные условия.
Изображения, видео и звуки доступны по их собственным лицензиям.