 | Эта статья требует дополнительных ссылок для проверки . ( декабрь 2009 г. ) ( Узнайте, как и когда удалить этот шаблон сообщения ) |
В математике , цепь Кемпе это устройство , используемое в основном в изучении теоремы четыре цвета . Интуитивно это связная цепочка точек на графике с чередованием цветов.
История [ править ]
Цепи Кемпе были впервые использованы Альфредом Кемпе в его попытке доказательства теоремы о четырех цветах. [1] Несмотря на то, что его доказательство оказалось неполным, метод цепей Кемпе имеет решающее значение для успешных современных доказательств (Аппель и Хакен, Робертсон и др.). Кроме того, метод используется в доказательстве теоремы пяти цветов по Перси Джона Хевуд , более слабой формой теоремы четыре цвета. [1]
Формальное определение [ править ]
Термин «цепь Кемпе» используется двумя разными, но взаимосвязанными способами.
Предположим, что G - граф с множеством вершин V , и нам задана функция раскраски
где S - конечный набор цветов, содержащий как минимум два различных цвета a и b . Если v - вершина с цветом a , то ( a , b ) -цепь Кемпе графа G, содержащая v, является максимальным связным подмножеством V, которое содержит v и все вершины которого окрашены либо в a, либо в b .
Вышеупомянутое определение - это то, с чем работал Кемпе. Обычно набор S состоит из четырех элементов (четыре цвета теоремы о четырех цветах), а c - правильная раскраска , то есть каждой паре смежных вершин в V назначаются разные цвета.
Более общее определение, которое используется в современных компьютерных доказательствах теоремы о четырех цветах, следующее. Предположим снова, что G - граф с множеством ребер E , и на этот раз у нас есть функция раскраски
Если e - ребро, которому назначен цвет a , то ( a , b ) -цепь Кемпе группы G, содержащая e, является максимальным связным подмножеством E, которое содержит e, и все ребра которого окрашены в a или b .
Это второе определение обычно применяется, когда S имеет три элемента, скажем, a , b и c , и где V - кубический граф , то есть каждая вершина имеет три инцидентных ребра. Если такой граф правильно раскрашен, то каждая вершина должна иметь ребра трех разных цветов, а цепи Кемпе в конечном итоге оказываются путями , что проще, чем в случае первого определения.
Что касается карт [ править ]
![[икона]](/wiki/File:Wiki_letter_w_cropped.svg){kind=small} | Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( Июнь 2008 г. ) |
Приложение к теореме четырех цветов [ править ]
В теореме о четырех цветах Кемпе удалось доказать, что все графы обязательно имеют вершину из пяти или меньше или содержат вершину, которая касается пяти других вершин, называемых ее соседями . Таким образом, чтобы доказать теорему о четырех цветах, достаточно доказать, что все вершины из пяти или менее можно было раскрасить в четыре цвета. Кемпе удалось доказать случай четвертой степени и дать частичное доказательство пятой степени, используя цепи Кемпе. [2]
В этом случае цепи Кемпе используются для доказательства идеи о том, что никакая вершина не должна касаться четырех цветов, отличных от себя, т.е. иметь степень 4. Во-первых, можно создать граф с вершиной v и четырьмя вершинами в качестве соседей. Если мы удалим вершину v, оставшиеся вершины можно раскрасить в четыре цвета. Мы можем установить следующие цвета (по часовой стрелке): красный, желтый, синий и зеленый. В этой ситуации может существовать цепочка Кемпе, соединяющая красных и синих соседей, или цепь Кемпе, соединяющая зеленых и желтых соседей, но не обе, поскольку эти два пути обязательно пересекаются, а вершина, где они пересекаются, не может быть окрашена. Предположим, что цепочка Кемпе соединяет зеленых и желтых соседей, тогда красный и синий обязательно не должны иметь цепочку Кемпе между собой. Итак, помещая исходную вершину v обратно в граф, мы можем просто поменять местами цвета красной вершины и ее соседей (включая красную вершину, сделав ее синей) и покрасить вершину v в красный цвет. В результате получается четырехцветный график. [3]
Другие приложения [ править ]
Цепи Кемпе использовались для решения задач при раскраске . [4] [5]
Ссылки [ править ]
- ^ а б «Красочная математика: Часть I» . Американское математическое общество . Проверено 10 июля, 2020 .
- ^ Аппель, Кеннет; Хакен, Вольфганг (1989), Каждую плоскую карту можно раскрашивать в четыре цвета, Contemporary Mathematics, 98, В сотрудничестве с Дж. Кохом, Провиденс, Род-Айленд: Американское математическое общество, DOI: 10.1090 / conm / 098, ISBN 0-8218- 5103-9 , MR 1025335
- ↑ Kempe, AB (1879), «О географической проблеме четырех цветов», Американский журнал математики, издательство Johns Hopkins University Press, 2 (3): 193–220
- Перейти ↑ Albertson, MO (1998). «Ты не можешь закрасить себя в угол». Журнал комбинаторной теории, серии B . 73 (2): 189–194. DOI : 10.1006 / jctb.1998.1827 .
- ^ Альбертсон, Миссури; Мур, EH (1999). «Расширение раскраски графов». Журнал комбинаторной теории, серии B . 77 : 83–95. DOI : 10.1006 / jctb.1999.1913 .
