Кемпе цепь - Kempe chain

Граф, содержащий цепь Кемпе, состоящую из чередующихся синих и красных вершин

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

История

Цепи Кемпе были впервые использованы Альфред Кемпе в его попытке доказательства теоремы о четырех цветах.^[1] Несмотря на то, что его доказательство оказалось неполным, метод цепочек Кемпе имеет решающее значение для успешных современных доказательств (Аппель и Хакен, Робертсон и др.). Кроме того, этот метод используется при доказательстве теорема пяти цветов к Перси Джон Хивуд, более слабая форма теоремы о четырех цветах.^[1]

Формальное определение

Термин «цепь Кемпе» используется двумя разными, но взаимосвязанными способами.

Предполагать грамм это график с вершина набор V, и нам дана функция раскраски

{displaystyle c: V o S}

куда S конечный набор цветов, содержащий не менее двух различных цветов а и б. Если v это вершина с цветом а, то (а, б) -Кемпе цепочка грамм содержащий v - максимальное связное подмножество V который содержит v и все вершины которого окрашены а или же б.

Вышеупомянутое определение - это то, с чем работал Кемпе. Обычно набор S имеет четыре элемента (четыре цвета теоремы о четырех цветах), и c это правильная окраска, то есть каждая пара смежных вершин в V присваиваются различные цвета.

Более общее определение, которое используется в современных компьютерных доказательствах теоремы о четырех цветах, следующее. Снова предположим, что грамм - граф с множеством ребер E, и на этот раз у нас есть функция раскраски

{displaystyle c: E o S.}

Если е цвет, которому присвоено ребро а, то (а, б) -Кемпе цепочка грамм содержащий е - максимальное связное подмножество E который содержит е и все края которого окрашены а или же б.

Это второе определение обычно применяется там, где S имеет три элемента, скажем а, б и c, и где V это кубический граф, то есть каждая вершина имеет три инцидентных ребра. Если такой граф правильно раскрашен, то каждая вершина должна иметь ребра трех разных цветов, и цепи Кемпе в конечном итоге будут пути, что проще, чем в случае первого определения.

Что касается карт

Приложение к теореме четырех цветов

В теореме о четырех цветах Кемпе удалось доказать, что все графы обязательно имеют вершину из пяти или меньше или содержат вершину, которая касается пяти других вершин, что называется ее соседи. Таким образом, чтобы доказать теорему о четырех цветах, Кемпе смог доказать, что все вершины из пяти или менее можно раскрашивать в четыре цвета. Кемпе удалось доказать случай четвертой степени и дать частичное доказательство пятой степени с помощью цепей Кемпе.^[2]

В этом случае цепи Кемпе используются для доказательства идеи о том, что ни одна вершина не должна касаться четырех цветов, отличных от себя, т.е. степень из 4. Во-первых, можно создать граф с вершиной v и четыре вершины в качестве соседей. Если мы удалим вершину v, оставшиеся вершины можно раскрасить в четыре цвета. Мы можем установить цвета (по часовой стрелке): красный, желтый, синий и зеленый. В этой ситуации может существовать цепочка Кемпе, соединяющая красных и синих соседей, или цепь Кемпе, соединяющая зеленых и желтых соседей, но не то и другое вместе, поскольку эти два пути обязательно пересекаются, а вершина, в которой они пересекаются, не может быть окрашена. Предположим, что цепочка Кемпе соединяет зеленых и желтых соседей, тогда красный и синий обязательно не должны иметь цепочку Кемпе между ними. Итак, при размещении исходной вершины v обратно в граф, мы можем просто поменять местами цвета красной вершины и ее соседей (включая красную вершину, сделав ее синей) и раскрасить вершину v как красный. В результате получается четырехцветный график.^[3]

Другие приложения

Цепи Кемпе использовались для решения проблем в раскраска расширение.^[4]^[5]