WikiDer > Число Хивуда

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

В 1890 году компания Heawood доказала свою пригодность для любых поверхностей. Кроме то сфера это не более чем

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

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

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

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

Примечания

• Боллобаш, Бела, Теория графов: вводный курс, том 63 GTM, Springer-Verlag, 1979. Zbl 0411.05032.
• Саати, Томас Л. и Кайнен, Пол К.; Четырехцветная проблема: нападения и завоевание, Дувр, 1986. Zbl 0463.05041.

В этой статье использованы материалы из номера Heawood по PlanetMath, который находится под лицензией Лицензия Creative Commons Attribution / Share-Alike.

Рекомендации