Википедия

Веретено Мозера

Веретено Мозера (веретено Мозеров, граф Мозера) — неориентированный граф, названный в честь математиков Лео Мозера[англ.] и его брата Вильяма, имеющий семь вершин и одиннадцать рёбер. Он является графом единичных расстояний, требующим четыре цвета в любой раскраске, и его существование используется для доказательства того, что хроматическое число плоскости равно по меньшей мере четырём.

Веретено Мозера
Назван в честь Лео Мозера[англ.], Вильяма Мозера
Вершин 7
Рёбер 11
Радиус 2
Диаметр 2
Обхват 3
Автоморфизмы 8
Хроматическое число 4
Хроматический индекс 4
Свойства планарен
граф единичных расстояний
ламанов

Называют также в честь Дьёрдя Хайоша, поскольку его можно получить в результате построения Хайоша[1], однако название «граф Хайоша» относится также и к другим графам, имеющим вид треугольника, вписанного в шестиугольник.[2]

Построение

править
 
Веретено Мозера, вложенное как граф единичных расстояний в плоскость, на фоне раскраски плоскости в семь цветов

Как граф единичных расстояний, веретено Мозера образуется двумя ромбами с углами 60 и 120 градусов, так что стороны и короткие диагонали ромбов образуют равносторонние треугольники. Два ромба располагаются на плоскости так, что две вершины их острых углов совпадают, а другая пара вершин острых углов располагаются на расстоянии единица. Одиннадцать рёбер графа — это восемь рёбер ромбов, две короткие диагонали, и ребро между двумя острыми вершинами ромбов.

 
Построение Хайоша веретена Мозера

Веретено Мозера можно построить только с точки зрения теории графов, без ссылки на геометрическое вложение, с помощью конструкции Хайоша, начав с двух полных графов по четыре вершины в каждом. Построение удаляет по ребру из каждого полного графа, объединяет две вершины удалённых рёбер в одну вершину, и добавляет новое ребро, соединяющее оставшиеся две конечные вершины удалённых рёбер.[3]

Другой способ построения веретена Мозера — это дополнение графа, образованного из графа   путём разделения одного из его рёбер.[4]

Приложение к задаче Нелсона — Эрдёша — Хадвигера

править

Задача Нелсона — Эрдёша — Хадвигера спрашивает, сколько цветов требуется для такой раскраски точек евклидовой плоскости, чтобы любые две точки плоскости, лежащие на единичном расстоянии, были покрашены в разные цвета. Фактически это задача о хроматическом числе бесконечного графа, вершинами которого служат все точки плоскости, а рёбрами — все пары точек, лежащих на расстоянии единица[5].

Веретено Мозера требует четыре цвета для любой раскраски: при любой раскраске в три цвета острые вершины ромбов будут иметь один и тот же цвет, а тогда ребро, соединяющее две острые вершины ромбов, будет соединять вершины одного цвета. Это противоречие показывает, что трёх цветов недостаточно и потребуется по меньшей мере четыре цвета. Достаточность четырёх цветов для раскраски веретена Мозера следует также, например, из того факта, что его вырожденность равна трём.

Другое доказательство того, что для раскраски веретена Мозера нужно четыре цвета, следует из построения Хайоша. Оба полных графа, из которых веретено Мозера образовано, требуют четыре цвета, а построение Хайоша сохраняет это свойство[3]. Более того, любое независимое множество в веретене Мозера имеет максимум две вершины[6], так что нужно не менее четырёх независимых множеств для покрытия всех семи вершин.

Поскольку веретено Мозера является подграфом бесконечного графа единичных расстояний плоскости, для раскраски плоскости нужно по меньшей мере четыре цвета. По теореме де Брёйна — Эрдёша (в предположении, что аксиома выбора верна) хроматическое число плоскости равно максимальному хроматическому числу всех конечных подграфов. В 2018 году Обри ди Грей показал, что существует граф единичных расстояний, для покраски которого требуется как минимум 5 цветов[7]. Лучшая верхняя граница хроматического числа плоскости равна семи, что существенно больше числа цветов, требуемых для раскраски веретена Мозера[5].

Другие свойства и приложения

править

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

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

Добавление любого ребра к веретену Мозера приведёт к графу, который нельзя вложить в плоскость в виде графа единичных расстояний, и не существует гомоморфизма веретена Мозера в любой меньший граф единичных расстояний. Эти два свойства веретена Мозера были использованы в 2011 году[11], чтобы показать, что проверка графа на существование двумерного представления в виде графа единичных расстояний является NP-трудной задачей. Доказательство использует преобразование из 3SAT, в котором веретено Мозера используется в качестве решающего устройства, устанавливающего истинность формулы.[8]

Веретено Мозера может быть использовано также в доказательстве результатов в теории Рамсея для евклидовой плоскости — если   является треугольником на плоскости и все точки плоскости выкрашены в два цвета (белый и чёрный), то либо существует треугольник с чёрными вершинами, получаемый из   движением, либо существует пара белых точек, находящихся на расстоянии единица. Для доказательства используется вложение   веретена Мозера в плоскость, при котором все рёбра имеют длину единица. Пусть   — это сумма Минковского множества   и вершин треугольника  . Если в   нет белых точек, находящихся на расстоянии единица, то каждая из трёх копий веретена Мозера в   должна иметь максимум две белые вершины, поскольку белые вершины должны образовать независимсое множество, а максимальное независимое множество в веретене Мозера имеет размер два. Таким образом, среди семи вершин веретена Мозера максимум шесть могут иметь белые вершины из  , так что по меньшей мере все копии одной из вершин должны быть чёрными. Вот они и образуют треугольник, получающийся из   движением.[6][12]

Примечания

править
  1. ↑ Bondy & Murty, 2008, p. 358.
  2. ↑ Berge, 1989, pp. 3—14.
  3. ↑ 1 2 Hajós, 1961, pp. 116—117.
  4. ↑ Gervacio et al, 2008, pp. 1973—1984.
  5. ↑ 1 2 3 Soifer, 2008, pp. 14—15.
  6. ↑ 1 2 Burkert & Johnson, 2011, pp. 97—113.
  7. ↑ Владимир Королёв. Математикам не хватило четырех цветов для раскраски плоскости. N+1 (10 апреля 2018). Дата обращения: 10 апреля 2018. Архивировано 10 апреля 2018 года.
  8. ↑ 1 2 Horvat et al, 2011, pp. 274—285.
  9. ↑ Haas et al, 2005, pp. 31—61.
  10. ↑ Winkler, 2011.
  11. ↑ Horvat et al, 2011.
  12. ↑ Soifer, 2008, Problem 40.26, p. 496.

Литература

править
  • Alexander Soifer. The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators. — New York: Springer-Verlag New York, 2008. — 607 p. — ISBN 978-0387746401.
  • Jeffrey Burkert, Peter Johnson. Ramsey theory. — New York: Birkhäuser/Springer, 2011. — Т. 285. — С. 97—113. — (Progr. Math.).
  • G. Hajós. Über eine Konstruktion nicht n-färbbarer Graphen. — 1961. — Vol. 10. — С. 116—117.
  • Boris Horvat, Jan Kratochvíl, Tomaž Pisanski. On the Computational Complexity of Degenerate Unit Distance Representations of Graphs // Combinatorial Algorithms: 21st International Workshop, IWOCA 2010, London, UK, July 26—28, 2010, Revised Selected Papers / Editors: Iliopoulos, Costas S., Smyth, William F.. — Springer-Verlag Berlin Heidelberg, 2011. — Vol. 6460. — P. 274—285. — 418 p. — (Theoretical Computer Science and General Issues). — ISBN 978-3-642-19222-7. — doi:10.1007/978-3-642-19222-7_28..
  • Ruth Haas, David Orden, Günter Rote, Francisco Santos, Brigitte Servatius, Herman Servatius, Diane Souvaine, Ileana Streinu, Walter Whiteley. Planar minimally rigid graphs and pseudo-triangulations // Computational Geometry Theory and Applications. — 2005. — Т. 31, вып. 1–2. — С. 31—61. — doi:10.1016/j.comgeo.2004.07.003.
  • Peter Winkler. Puzzled: Distances Between Points on the Plane // Communications of the ACM. — 2011. — Ноябрь (т. 54, вып. 11). — doi:10.1145/2018396.2018422.
  • Severino V. Gervacio, Yvette F. Lim, Hiroshi Maehara. Planar unit-distance graphs having planar unit-distance complement // Discrete Mathematics. — 2008. — Т. 308, вып. 10. — С. 1973—1984. — doi:10.1016/j.disc.2007.04.050.
  • Claude Berge. Minimax relations for the partial q-colorings of a graph // Discrete Mathematics. — 1989. — Т. 74, вып. 1—2. — С. 3—14. — doi:10.1016/0012-365X(89)90193-3.
  • J. A. Bondy, U. S. R. Murty. Graph Theory. — Springer, 2008. — Т. 244. — С. 358. — doi:10.1007/978-1-84628-970-5.
  • L. Moser, W. Moser. Solution to problem 10 // Can. Math. Bull.. — 1961. — Т. 4. — С. 187—189.

Ссылки

править
Источник — https://ru.wiki.x.io/w/index.php?title=Веретено_Мозера&oldid=140158969