Сеть Кемпе
В математике цепочка Кемпе — это устройство, используемое в основном при изучении теоремы о четырёх цветах . Интуитивно это представляет собой связную цепочку вершин графа с чередующимися цветами.
История
[ редактировать ]Цепи Кемпе впервые были использованы Альфредом Кемпе в его попытке доказать теорему о четырех цветах. [1] Несмотря на то, что его доказательство оказалось неполным, метод цепей Кемпе имеет решающее значение для успеха действительных современных доказательств, таких как первое успешное доказательство Кеннета Аппеля и Вольфганга Хакена . [2] [3] Кроме того, этот метод используется при доказательстве теоремы о пяти цветах Перси Джона Хивуда , более слабой, но более легко доказуемой версии теоремы о четырех цветах. [1]
Формальное определение
[ редактировать ]Термин «цепь Кемпе» используется в двух разных, но связанных между собой смыслах.
Предположим, G — граф с вершин множеством V с заданной функцией раскраски.
где S — конечное множество цветов, содержащее как минимум два различных цвета a и b . Если v — вершина цвета a , то ( a , b )-цепь Кемпе группы G , содержащая v , является максимальным связным подмножеством V , которое содержит v и все вершины которого окрашены в цвет a или b .
Приведенное выше определение — это то, с чем работал Кемпе. Обычно набор S состоит из четырех элементов (четыре цвета из теоремы о четырех цветах), а c — правильная раскраска , то есть каждой паре соседних вершин в V присвоены разные цвета. С этими дополнительными условиями a и b являются двумя из четырех доступных цветов, и каждый элемент ( a , b )-цепи Кемпе имеет соседей в цепочке только другого цвета.
Более общее определение, которое используется в современных компьютерных доказательствах теоремы о четырех цветах, заключается в следующем. Предположим снова, что G — граф с множеством ребер E , и на этот раз у нас есть функция раскраски
Если e — ребро, которому присвоен цвет a , то ( a , b )-цепь Кемпе G , содержащая e, является максимальным связным подмножеством E , которое содержит e и все ребра которого окрашены либо в a, либо в b .
Это второе определение обычно применяется там, где S имеет три элемента, скажем, a , b и c , и где V — кубический граф , то есть каждая вершина имеет три инцидентных ребра. Если такой граф правильно раскрашен, то каждая вершина должна иметь ребра трёх различных цветов, и цепи Кемпе в конечном итоге становятся путями , что проще, чем в случае первого определения.
В плане карт
[ редактировать ]![[икона]](http://upload.wikimedia.org/wikipedia/commons/thumb/1/1c/Wiki_letter_w_cropped.svg/20px-Wiki_letter_w_cropped.svg.png){kind=small} | Этот раздел нуждается в расширении . Вы можете помочь, добавив к нему . ( июнь 2008 г. ) |
Приложение к теореме о четырех цветах
[ редактировать ]В теореме о четырех цветах Кемпе смог доказать, что все графы обязательно имеют вершину с числом пять или меньше или содержат вершину, которая касается пяти других вершин, называемых ее соседями . Таким образом, чтобы доказать теорему о четырех цветах, достаточно доказать, что все вершины с пятью или меньшим количеством цветов можно раскрасить в четыре цвета. Кемпе смог доказать случай четвертой степени и дать частичное доказательство пятой степени, используя цепи Кемпе. [4]
В этом случае цепи Кемпе используются для доказательства идеи о том, что ни одна вершина четвертой степени не должна касаться четырех различных цветов, отличных от нее самой. Во-первых, можно создать граф с вершиной v и четырьмя вершинами в качестве соседей. Если мы удалим вершину v , мы сможем раскрасить оставшиеся вершины в четыре цвета. Мы можем установить цвета (по часовой стрелке): красный, желтый, синий и зеленый. В этой ситуации может существовать цепь Кемпе, соединяющая красных и синих соседей, или цепочка Кемпе, соединяющая зеленых и желтых соседей, но не обе, поскольку эти два пути обязательно пересекутся, а вершина, где они пересекаются, не может быть раскрашена обоими красный или синий и одновременно с зеленым или желтым. Предположим, что цепь Кемпе соединяет зеленых и желтых соседей, тогда между красным и синим обязательно не должно быть цепи Кемпе. Итак, помещая исходную вершину v обратно в граф, мы можем просто поменять местами цвета красной вершины и ее соседей (включая красную вершину, сделав ее синей), в результате чего вершина останется v с двумя синими соседями, одним зеленым и одним желтым. Это означает, что вершина v имеет только три различных цвета в качестве соседей и что теперь мы можем раскрасить вершину v в красный цвет. В результате получается четырехцветный график. [5]
Другие приложения
[ редактировать ]Цепи Кемпе использовались для решения задач расширения окраски . [6] [7] Цепочки Кемпе могут использоваться для распределения регистров . [ нужна ссылка ]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Jump up to: а б «Красочная математика: Часть I» . Американское математическое общество . Проверено 10 июля 2020 г.
- ^ Аппель, К.; Хакен, В. (1 сентября 1977 г.). «Каждая планарная карта раскрашивается в четыре цвета. Часть I: Разрядка» . Иллинойсский математический журнал . 21 (3). дои : 10.1215/ijm/1256049011 . ISSN 0019-2082 .
- ^ Робертсон, Нил; Сандерс, Дэниел; Сеймур, Пол; Томас, Робин (1 мая 1997 г.). «Теорема четырех цветов» . Журнал комбинаторной теории, серия B. 70 (1): 2–44. дои : 10.1006/jctb.1997.1750 . ISSN 0095-8956 .
- ^ Аппель, Кеннет; Хакен, Вольфганг (1989), Каждая плоская карта раскрашивается в четыре цвета, Современная математика, 98, При сотрудничестве Дж. Коха, Провиденс, Род-Айленд: Американское математическое общество, doi: 10.1090/conm/098, ISBN 0-8218-5103-9 , МР 1025335
- ^ Кемпе, AB (1879), «О географической проблеме четырех цветов», Американский математический журнал, The Johns Hopkins University Press, 2 (3): 193–220
- ^ Альбертсон, Миссури (1998). «Нельзя загонять себя в угол» . Журнал комбинаторной теории, серия B. 73 (2): 189–194. дои : 10.1006/jctb.1998.1827 .
- ^ Альбертсон, Миссури; Мур, Э.Х. (1999). «Расширение раскрасок графа» . Журнал комбинаторной теории, серия B. 77 : 83–95. дои : 10.1006/jctb.1999.1913 .