Цепи Кемпе: математический инструмент доказательства теоремы о четырёх красках
Kempe chain
Цепи Кемпе – математический инструмент, используемый в доказательстве теоремы о четырёх красках. Ключевой метод в современных доказательствах и теории графов.
Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Содержание
Введение
Математический инструмент, используемый в доказательстве теоремы о четырёх цветах.
Mathematical device used in proof of the four colour theorem
В математике цепочка Кемпе — это инструмент, используемый главным образом при изучении теоремы о четырёх цветах. Интуитивно, это связная цепочка вершин графа, окрашенных в чередующиеся цвета.
In mathematics, a Kempe chain is a device used mainly in the study of the four colour theorem. Intuitively, it is a connected chain of vertices on a graph with alternating colours.
История
Цепи Кемпе впервые использовал Альфред Кемпе в своей попытке доказать теорему о четырех красках. Несмотря на то, что его доказательство оказалось неполным, метод цепей Кемпе имеет решающее значение для успеха корректных современных доказательств, таких как первое успешное доказательство Кеннета Аппеля и Вольфганга Хакена. Более того, этот метод используется в доказательстве теоремы о пяти красках Перси Джона Хьювуда, более слабой, но более легко доказуемой версии теоремы о четырех красках. В этом случае цепи Кемпе используются для доказательства идеи о том, что ни одна вершина степени четыре не должна быть связана с четырьмя различными цветами, отличными от её собственного. Сначала можно создать граф с вершиной v и четырьмя вершинами в качестве соседей. Если удалить вершину v, оставшиеся вершины можно раскрасить в четыре цвета. Можно установить цвета (по часовой стрелке) как красный, желтый, синий и зеленый. В этой ситуации может существовать цепь Кемпе, соединяющая красных и синих соседей, или цепь Кемпе, соединяющая зеленых и желтых соседей, но не одновременно, поскольку эти два пути неизбежно пересеклись бы, а вершина, в которой они пересекаются, не может быть окрашена одновременно в красный или синий и в зеленый или желтый. Предположим, что цепь Кемпе соединяет зеленых и желтых соседей, тогда красные и синие соседи не должны иметь цепь Кемпе между собой. Следовательно, когда исходная вершина v возвращается в граф, мы можем просто изменить цвета красной вершины и её соседей (включая саму красную вершину, окрасив её в синий цвет), что оставит вершину v с двумя синими соседями, одним зеленым и одним желтым. Это означает, что у v только три различных цвета в качестве соседей, и теперь мы можем раскрасить вершину v в красный цвет. В результате получается граф, раскрашенный в четыре цвета.
Kempe chains were first used by Alfred Kempe in his attempted proof of the four colour theorem. Even though his proof turned out to be incomplete, the method of Kempe chains is crucial to the success of valid modern proofs, such as the first successful one by Kenneth Appel and Wolfgang Haken. Furthermore, the method is used in the proof of the five colour theorem by Percy John Heawood, a weaker but more easily proven version of the four colour theorem. In this case, Kempe chains are used to prove the idea that no vertex of degree four has to be touching four distinct colours different from itself. First, one can create a graph with a vertex v and four vertices as neighbours. If we remove the vertex v, we can four colour the remaining vertices. We can set the colours as (in clockwise order) red, yellow, blue, and green. In this situation, there can be a Kempe chain joining the red and blue neighbours or a Kempe chain joining the green and yellow neighbours, but not both, since these two paths would necessarily intersect, and the vertex where they intersect cannot be coloured with both red or blue and with green or yellow at the same time. Supposing that the Kempe chain is connecting the green and yellow neighbours, red and blue must then necessarily not have a Kempe chain between them. So, when placing the original vertex v back into the graph, we can simply reverse the colours of the red vertex and its neighbours (including the red vertex, making it blue), which leaves vertex v with two blue neighbours, one green, and one yellow. This means v has only three distinct colours as neighbours, and that we can now colour vertex v as red. This results in a four coloured graph.
Другие применения
Цепи Кемпе использовались для решения задач расширения раскраски. Цепи Кемпе могут быть использованы для выделения регистров.
Kempe chains have been used to solve problems in colouring extension. Kempe chains can be used for register allocation.