Проблема Земля-Луна

Нерешенная задача по математике :

Сколько цветов нужно для раскраски бипланарных графов?

Проблема Земля-Луна — нерешенная проблема раскраски графов в математике. Это расширение проблемы раскраски плоских карт (решаемой теоремой о четырех цветах ) и было поставлено Герхардом Рингелем в 1959 году. ^{[ 1 ]} Интуитивная форма задачи спрашивает, сколько цветов необходимо для раскрашивания политических карт Земли и Луны в гипотетическом будущем, когда каждая земная страна будет иметь лунную колонию, которой необходимо придать один и тот же цвет. Говоря математическим языком, он ищет хроматическое число графов бипланарных . Известно, что это число составляет минимум 9 и максимум 12.

Задача Земля-Луна была распространена на аналогичные задачи раскраски карт любого числа планет. Для этого расширения нижняя и верхняя границы числа цветов ближе, в пределах двух друг от друга. Одно из реальных применений проблемы Земля-Луна включает в себя тестирование печатных плат .

Формулировка и история

В задаче о раскраске карты конечное число односвязных областей на евклидовой плоскости или в топологически эквивалентном пространстве, например страны на поверхности Земли, должны быть раскрашены так, чтобы, когда две области имеют границу ненулевой длины, они имели разные цвета. Ее можно преобразовать в задачу о раскраске графа , создав вершину для каждой области и ребро для каждых двух соседних областей, создав планарный граф , вершины которого необходимо раскрасить. В соответствии с требованием, чтобы смежные области имели разные цвета, смежные вершины (две конечные точки любого ребра) должны иметь разные цвета. Согласно теореме о четырех цветах , полученный плоский граф (или любой плоский граф) можно раскрасить не более чем в четыре разных цвета, независимо от того, сколько регионов задано. ^{[ 2 ]}

В 1959 году Герхард Рингель опубликовал книгу о раскрасках поверхностей, в которой обобщил результаты того времени по задаче четырех цветов и гипотезе Хивуда о картах раскраски неплоских поверхностей, таких как тор и бутылка Клейна . ^{[ 1 ]} Обе проблемы давно предполагались, но на тот момент так и не были решены. Сам Рингель позднее доказал гипотезу Хивуда в статье 1968 года, написанной совместно с Дж. У.Т. Янгсом ; ^{[ 2 ]}^{[ 3 ]} теорема о четырех цветах ускользала от доказательства до 1976 года. ^{[ 2 ]}^{[ 4 ]} Другой темой книги Рингеля была работа Перси Джона Хивуда 1890 года о «проблеме империи»: раскрашивание карт, на которых каждая империя имеет определенное число. $m$ отдельных регионов на Земле (родная страна и $m-1$ колонии). Как показал Хивуд для $m=2$ , а Рингель позже выступил с Джексоном в 1984 году за $m>2$ , $6m$ цвета необходимы и достаточны. ^{[ 2 ]}^{[ 5 ]}^{[ 6 ]}^{[ 7 ]} Возможно, вдохновленный этой проблемой и началом космической эры , Рингель включил в свою книгу проблему Земля-Луна как вариант проблемы империи, в которой колонии находятся на Луне, а не на Земле. ^{[ 1 ]}^{[ 2 ]} По формулировке Мартина Гарднера , колонии находятся на Марсе. ^{[ 6 ]}

В задаче Рингеля Земля-Луна каждая страна на Земле имеет соответствующую колонию на поверхности Луны, которой необходимо придать одинаковый цвет. Эти колонии могут иметь границы, совершенно отличные от устройства границ на Земле. Страны должны быть раскрашены, используя один и тот же цвет для каждой страны и ее колонии, чтобы, когда две страны имеют общую границу на Земле или на Луне, им были присвоены разные цвета. Задача Рингеля спрашивает: сколько цветов необходимо, чтобы гарантировать, что все страны могут быть раскрашены, независимо от того, как расположены их границы? ^{[ 2 ]} Рингель доказал, что количество необходимых цветов было не менее 8 и не более 12, предположив, что правильный ответ — 8. ^{[ 6 ]}

Опять же, можно сформулировать тот же вопрос так же, как и в теории графов, с одной вершиной для каждой пары страна и ее колония и ребром для каждой смежности между странами или колониями. Как и в плоском случае, после этого преобразования необходимо раскрасить вершины, причем конечные точки каждого ребра будут окрашены в разные цвета. Графы, которые приводят к этой версии проблемы, являются бипланарными графами или, что то же самое, графами толщины два: их ребра могут быть разделены на два подмножества (ребра, исходящие из соседних с Землей и ребра, исходящие из прилегающих к Луне) таких, что соответствующие два подграфа оба плоские. С математической точки зрения, проблема Рингеля требует максимального хроматического числа бипланарных графов. ^{[ 2 ]}

Границы

Бипланарный граф на $n$ вершин имеет не более $6n-12$ ребер (вдвое больше, чем может иметь планарный граф), откуда по формуле суммы степеней следует , что он имеет хотя бы одну вершину с не более чем 11 соседями. Удаление этой вершины, рекурсивная раскраска оставшегося графа, а затем использование неиспользуемого цвета с наименьшим номером для удаленной вершины приводит к раскраске не более чем в 12 цветов; это жадная раскраска для упорядочивания графа по вырождению. Следовательно, для бипланарных графов требуется не более 12 цветов. ^{[ 2 ]}

Пример бипланарного графа, требующего 9 цветов, можно построить как объединение с 6 вершинами полного графа с 5 вершинами и графа циклов . Это означает, что эти два подграфа соединены всеми возможными ребрами из одного подграфа в другой. Полученный граф имеет 11 вершин и требует 6 цветов для полного подграфа и 3 цвета для подграфа цикла, что дает всего 9 цветов. ^{[ 2 ]} Эта конструкция, предложенная Томом Суланке в 1974 году, опровергла гипотезу Рингеля о том, что 8 цветов всегда будет достаточно. ^{[ 6 ]} Впоследствии было построено бесконечное семейство бипланарных 9-критических графов (минимальных графов, требующих девяти цветов). ^{[ 8 ]}^{[ 9 ]}

Несмотря на отсутствие дальнейшего прогресса в решении этой проблемы, в 2018 году Эллен Гетнер предположила, что правильное количество цветов для этой проблемы — 11. Она предлагает несколько кандидатов на 10-хроматические бипланарные графы, включая граф $C_{7}\boxtimes K_{4}$ полученный как сильное произведение графа циклов с кликой, и граф, полученный удалением любой вершины из $C_{5}\boxtimes K_{4}$ . Можно показать, что для этих графов требуется 10 цветов, поскольку у них нет независимого набора, достаточно большого, чтобы быть самым большим цветовым классом в раскраске с меньшим количеством цветов. Кроме того, они соответствуют ограничениям на количество ребер, которые может иметь бипланарный граф. Однако представление их в виде бипланарных графиков (или карт Земли–Луны) остается неясным. ^{[ 10 ]}

Приложение

Одно из применений раскраски бипланарных графов включает проверку печатных плат на наличие коротких замыканий. Электрические проводники внутри этих плат содержат пересечения, но (для двусторонних печатных плат) можно предположить, что их примыкания образуют бипланарный граф. После раскраски этого графика можно обнаружить короткие замыкания между соседними проводниками, добавив дополнительную схему для соединения всех проводников одного цвета друг с другом и проверив соединения между парами разных цветов. При некоторой осторожности эту идею можно использовать для сокращения количества тестов, необходимых для каждой цепи, до четырех. ^{[ 2 ]}^{[ 11 ]}

Обобщения

Также рассматривались различные обобщения проблемы, в том числе варианты проблемы с более чем двумя планетами или со странами, которые могут иметь более одного региона на планете. ^{[ 12 ]}^{[ 13 ]} Карты с одной планетой и несколькими регионами в каждой стране создают проблему империи Хивуда. ^{[ 2 ]}^{[ 7 ]} Карты с более чем двумя планетами, но только с одним регионом на планету, соответствуют графам, толщина которых не более чем равна числу планет. Для этих графиков известны более точные (хотя и неполные) результаты. Для графиков толщины $t\geq 3$ и соответствующий $t$ -карты планет, хроматическое число не более $6t$ по тому же аргументу вырождения, который использовался в проблеме Земля-Луна. Также для $t\geq 3$ , полный граф с $6t-2$ вершины имеют толщину $t$ , чтобы показать некоторые из этих графиков, требуется $6t-2$ цвета. Таким образом, в этом случае верхняя и нижняя границы находятся в пределах двух цветов друг от друга. ^{[ 14 ]}

Ссылки

^ Jump up to: ^а ^б ^с Рингель, Герхард (1959), Проблемы раскраски поверхностей и графов , Математические монографии, том. 2, Берлин: Немецкое научное издательство VEB, MR 0109349
^ Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Хатчинсон, Джоан П. (октябрь 1993 г.), «Раскраска обычных карт, карт империй и карт Луны», Mathematics Magazine , 66 (4): 211–226, doi : 10.2307/2690733 , JSTOR 2690733
^ Рингель, Г .; Янгс, JWT (1968), «Решение проблемы раскраски карт Хивуда», Proc. Натл. акад. наук. США , том. 60, нет. 2, стр. 438–445, Бибкод : 1968PNAS...60..438R , doi : 10.1073/pnas.60.2.438 , PMC 225066 , PMID 16591648
^ Аппель, К.; Хакен, В. (1976), «Каждая плоская карта раскрашивается в четыре цвета», Бюллетень Американского математического общества , 82 (5): 711–712, doi : 10.1090/S0002-9904-1976-14122-5 , MR 0424602
^ Хивуд, П.Дж. (1890), «Теорема о цвете карты», Ежеквартальный журнал математики, Оксфорд , том. 24, стр. 332–338.
^ Jump up to: ^а ^б ^с ^д Гарднер, Мартин (февраль 1980 г.), «Раскраска необычных карт ведет на неизведанную территорию», Mathematical Games, Scientific American , 242 (2): 14–23, doi : 10.1038/scientificamerican0280-14 , JSTOR 24966248
^ Jump up to: ^а ^б Джексон, Брэд; Рингель, Герхард (1984), «Решение проблемы империи Хивуда на плоскости», Журнал чистой и прикладной математики , 347 : 146–153, doi : 10.1515/crll.1984.347.146 , MR 0733049
^ Бутин, Дебра Л .; Гетнер, Эллен ; Суланке, Том (2008), «Графы толщины два, I: новые графы с девятью критическими графами, графы перестановочных слоев и графы Кэтлина», Journal of Graph Theory , 57 (3): 198–214, doi : 10.1002/jgt. 20282 , МР 2384020 , С2КИД 39576387
^ Гетнер, Эллен ; Суланке, Том (2009), «Графы толщины два, II: больше новых девятикритических графов, коэффициент независимости, клонированные планарные графы, а также одиночные и двойные внешнепланарные графы», Graphs and Combinatorics , 25 (2): 197–217, дои : 10.1007/s00373-008-0833-5 , MR 2511878 , S2CID 2209541
^ Гетнер, Эллен (2018), «На Луну и дальше», в Гере, Ралукка ; Хейнс, Тереза В .; Хедетниеми, Стивен Т. (ред.), Теория графов: любимые гипотезы и открытые проблемы, II , задачники по математике, Springer International Publishing, стр. 115–133, номер документа : 10.1007/978-3-319-97686-0_11 , ISBN 978-3-319-97684-6 , МР 3930641
^ Гэри, М .; Джонсон, Д .; Итак, Хинг (октябрь 1976 г.), «Применение раскраски графов для тестирования печатных плат», IEEE Transactions on Circuits and Systems , 23 (10): 591–599, doi : 10.1109/tcs.1976.1084138
^ Стюарт, Ян (апрель 1993 г.), «Взлет и падение лунного М-пира», Mathematical Recreations, Scientific American , 268 (4): 120–121, Бибкод : 1993SciAm.268d.120S , doi : 10.1038/scientificamerican0493- 120 , JSTOR 24941454
^ Джексон, Брэд; Рингель, Герхард (2000), «Вариации проблемы Рингеля Земля-Луна», Discrete Mathematics , 211 (1–3): 233–242, doi : 10.1016/S0012-365X(99)00278-2 , MR 1735339
^ Алексеев В.Б.; Гончаков В.С. (1976), "Толщина произвольного полного графа", Математический сборник , Новая серия, 101 (143): 212–230, Бибкод : 1976SbMat..30..187A , doi : 10.1070/SM1976v030n02ABEH002267 , MR 0460162

Внешние ссылки

Вайсштейн, Эрик В. , «Проблема Земля-Луна» , MathWorld
«Проблема Земли-Луны» , Открытый проблемный сад

[ringel-1] Jump up to: ^а ^б ^с Рингель, Герхард (1959), Проблемы раскраски поверхностей и графов , Математические монографии, том. 2, Берлин: Немецкое научное издательство VEB, MR 0109349

[hutchinson-2] Jump up to: ^а ^б ^с ^д ^и ^ж ^г ^час ^я ^дж ^к Хатчинсон, Джоан П. (октябрь 1993 г.), «Раскраска обычных карт, карт империй и карт Луны», Mathematics Magazine , 66 (4): 211–226, doi : 10.2307/2690733 , JSTOR 2690733

[ringel-youngs-3] Рингель, Г .; Янгс, JWT (1968), «Решение проблемы раскраски карт Хивуда», Proc. Натл. акад. наук. США , том. 60, нет. 2, стр. 438–445, Бибкод : 1968PNAS...60..438R , doi : 10.1073/pnas.60.2.438 , PMC 225066 , PMID 16591648

[appel-haken-4] Аппель, К.; Хакен, В. (1976), «Каждая плоская карта раскрашивается в четыре цвета», Бюллетень Американского математического общества , 82 (5): 711–712, doi : 10.1090/S0002-9904-1976-14122-5 , MR 0424602

[heawood-5] Хивуд, П.Дж. (1890), «Теорема о цвете карты», Ежеквартальный журнал математики, Оксфорд , том. 24, стр. 332–338.

[gardner-6] Jump up to: ^а ^б ^с ^д Гарднер, Мартин (февраль 1980 г.), «Раскраска необычных карт ведет на неизведанную территорию», Mathematical Games, Scientific American , 242 (2): 14–23, doi : 10.1038/scientificamerican0280-14 , JSTOR 24966248

[jr-empire-7] Jump up to: ^а ^б Джексон, Брэд; Рингель, Герхард (1984), «Решение проблемы империи Хивуда на плоскости», Журнал чистой и прикладной математики , 347 : 146–153, doi : 10.1515/crll.1984.347.146 , MR 0733049

[boutin-gethner-sulanke-8] Бутин, Дебра Л .; Гетнер, Эллен ; Суланке, Том (2008), «Графы толщины два, I: новые графы с девятью критическими графами, графы перестановочных слоев и графы Кэтлина», Journal of Graph Theory , 57 (3): 198–214, doi : 10.1002/jgt. 20282 , МР 2384020 , С2КИД 39576387

[gethner-sulanke-9] Гетнер, Эллен ; Суланке, Том (2009), «Графы толщины два, II: больше новых девятикритических графов, коэффициент независимости, клонированные планарные графы, а также одиночные и двойные внешнепланарные графы», Graphs and Combinatorics , 25 (2): 197–217, дои : 10.1007/s00373-008-0833-5 , MR 2511878 , S2CID 2209541

[gethner-10] Гетнер, Эллен (2018), «На Луну и дальше», в Гере, Ралукка ; Хейнс, Тереза В .; Хедетниеми, Стивен Т. (ред.), Теория графов: любимые гипотезы и открытые проблемы, II , задачники по математике, Springer International Publishing, стр. 115–133, номер документа : 10.1007/978-3-319-97686-0_11 , ISBN 978-3-319-97684-6 , МР 3930641

[garey-johnson-so-11] Гэри, М .; Джонсон, Д .; Итак, Хинг (октябрь 1976 г.), «Применение раскраски графов для тестирования печатных плат», IEEE Transactions on Circuits and Systems , 23 (10): 591–599, doi : 10.1109/tcs.1976.1084138

[stewart-12] Стюарт, Ян (апрель 1993 г.), «Взлет и падение лунного М-пира», Mathematical Recreations, Scientific American , 268 (4): 120–121, Бибкод : 1993SciAm.268d.120S , doi : 10.1038/scientificamerican0493- 120 , JSTOR 24941454

[jr-variations-13] Джексон, Брэд; Рингель, Герхард (2000), «Вариации проблемы Рингеля Земля-Луна», Discrete Mathematics , 211 (1–3): 233–242, doi : 10.1016/S0012-365X(99)00278-2 , MR 1735339

[alekseev-goncakov-14] Алексеев В.Б.; Гончаков В.С. (1976), "Толщина произвольного полного графа", Математический сборник , Новая серия, 101 (143): 212–230, Бибкод : 1976SbMat..30..187A , doi : 10.1070/SM1976v030n02ABEH002267 , MR 0460162

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[ 12 ]

[ 13 ]

[ 14 ]