Раскраска графика
В теории графов раскраска графов является частным случаем маркировки графов ; это присвоение меток, традиционно называемых «цветами», элементам графа с определенными ограничениями. В своей простейшей форме это способ раскрасить вершины графа таким образом, чтобы никакие две соседние вершины не были одного цвета; это называется раскраской вершин . Точно так же раскраска ребер назначает цвет каждому ребру, так что никакие два соседних ребра не могут быть одного цвета, а раскраска граней планарного графа назначает цвет каждой грани или области, так что никакие две грани, имеющие общую границу, не имеют одинакового цвета. такого же цвета.
Раскраска вершин часто используется для введения задач раскраски графа, поскольку другие задачи раскраски могут быть преобразованы в экземпляр раскраски вершин. Например, раскраска ребер графа — это просто раскраска вершин его линейного графа , а раскраска граней плоского графа — это просто раскраска вершин его двойственного графа . Однако задачи раскраски не вершин часто ставятся и изучаются как есть. Отчасти это педагогично , а отчасти потому, что некоторые задачи лучше всего изучать в их невершинной форме, как в случае раскраски ребер.
Условие использования цветов происходит от раскрашивания стран на карте , где каждое лицо буквально окрашено. Это было обобщено на раскрашивание граней графа, встроенного в плоскость. По планарной двойственности он стал раскрашивать вершины и в таком виде обобщается на все графы. В математических и компьютерных представлениях обычно в качестве «цветов» используются первые несколько положительных или неотрицательных целых чисел. В общем случае в качестве «набора цветов» можно использовать любое конечное множество . Природа проблемы окраски зависит от количества цветов, но не от того, что они собой представляют.
Раскраска графов имеет множество практических применений, а также решает теоретические задачи. Помимо классических типов задач, различные ограничения также могут быть установлены на граф, или на способ присвоения цвета, или даже на сам цвет. Он даже стал популярным среди широкой публики в виде популярной числовой головоломки Судоку . Раскраска графов по-прежнему является очень активной областью исследований.
Первые результаты о раскраске графов касаются почти исключительно планарных графов в виде раскраски карт . Пытаясь раскрасить карту графств Англии, Фрэнсис Гатри постулировал гипотезу о четырех цветах, отметив, что четырех цветов достаточно, чтобы раскрасить карту так, чтобы ни один регион, имеющий общую границу, не получил одинаковый цвет. Брат Гатри передал вопрос своему учителю математики Августу де Моргану из Университетского колледжа , который упомянул его в письме Уильяму Гамильтону в 1852 году . Артур Кейли поднял проблему на собрании Лондонского математического общества .в 1879 году. В том же году Альфред Кемпе опубликовал статью, в которой утверждал, что установил результат, и в течение десятилетия проблема четырех цветов считалась решенной. За свои достижения Кемпе был избран членом Королевского общества , а затем президентом Лондонского математического общества. [1]
В 1890 году Хивуд указал, что аргумент Кемпе неверен. Однако в этой статье он доказал теорему о пяти цветах , заявив, что каждую плоскую карту можно раскрасить не более чем в пять цветов, используя идеи Кемпе. В следующем столетии было разработано огромное количество работ и теорий, чтобы уменьшить количество цветов до четырех, пока теорема о четырех цветах не была окончательно доказана в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном . Доказательство восходит к идеям Хивуда и Кемпе и в значительной степени игнорирует промежуточные разработки. [2] Доказательство теоремы о четырех красках также примечательно тем, что оно является первым крупным компьютерным доказательством.
