Раскраска планарных графов
Раскраска графов Примеры и применение
Отправьте статью сегодня! Журнал выйдет 13 апреля , печатный экземпляр отправим 17 апреля. Автор : Моторина Екатерина Алексеевна. Дата публикации : Статья просмотрена: раз.
В теории топологических графов , 1-планарный граф - это граф, который можно нарисовать в евклидовой плоскости таким образом, чтобы каждое ребро имело не более одной точки пересечения, где он пересекает одну дополнительную кромку. Если 1-планарный граф, одно из наиболее естественных обобщений планарных графов , нарисован таким образом, рисунок называется 1-плоскостным графом или 1-планарным. Позже было показано, что точное количество цветов, необходимых для раскраски этих графиков, в худшем случае, равно шести. Пример полного графа K6, который является 1-плоским, показывает, что для 1-планарного графа иногда может потребоваться шесть цветов. Однако доказать, что шести цветов всегда достаточно, сложнее. Рингель мотивировал попытку решить вариант полной раскраски для плоских графов , в котором один одновременно окрашивает вершины и грани плоского графа таким образом, чтобы никакие две соседние вершины не имели одинаковый цвет, никакие две смежные грани не имели одинаковый цвет и никакие вершины и грани, смежные друг с другом, не имели одного цвета.
Теорема о четырех цветах — это математический вопрос, который возник еще в 19 веке. Он заключается в том, можно ли раскрасить любую карту, используя только четыре цвета, таким образом, чтобы ни одна из двух соседних областей не имела одинакового цвета. В этом материале мы расскажем, у кого впервые возник этот вопрос, причем тут теория графов, кто и как пытался доказать эту теорему и что из этого вышло. Первоначально вопросом четырех цветов заинтересовался студент Фредерик Гатри, который изучал карту графств Англии.
