Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску
Шпиндель Мозера
Псевдотриангуляция шпинделя Мозера.svg
Названный в честьЛео Мозер , Уильям Мозер
Вершины7
Края11
Радиус2
Диаметр2
Обхват3
Автоморфизмы8
Хроматическое число4
Хроматический индекс4
Характеристикипланарное
единичное расстояние
Граф Ламана
Таблица графиков и параметров

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

Веретено Мозера также называют графом Хаджоша в честь Дьердя Хаджоса , поскольку его можно рассматривать как пример конструкции Хаджоса . [3] Однако название «граф Хайоша» также применялось к другому графу в форме треугольника, вписанного в шестиугольник. [4]

Строительство [ править ]

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

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

Конструкция веретена Мозера Hajós

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

Другой способ построения веретена Мозера - это дополнительный граф графа, образованный из графа полезности K 3,3 путем подразделения одного из его ребер. [6]

Приложение к проблеме Хадвигера – Нельсона [ править ]

Задача Хадвигера – Нельсона спрашивает, сколько цветов необходимо, чтобы раскрасить точки евклидовой плоскости таким образом, чтобы каждой паре точек на единичном расстоянии друг от друга были присвоены разные цвета. То есть он запрашивает хроматическое число бесконечного графа, вершинами которого являются все точки на плоскости, а ребрами - все пары точек на единичном расстоянии. [2]

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

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

Поскольку веретено Мозера является подграфом графа бесконечных единичных расстояний плоскости, граф плоскости также требует как минимум четырех цветов любой раскраски. По теореме де Брейна – Эрдеша (в предположении, что выбранная аксиома верна) хроматическое число плоскости совпадает с наибольшим хроматическим числом любого из ее конечных подграфов; до открытия семейства 5-хроматических графов единичных расстояний в 2018 году не было найдено ни одного подграфа бесконечного графа единичных расстояний, который требует большего количества цветов, чем веретено Мозера. Однако наилучшая верхняя граница для хроматического числа плоскости - семь, что значительно превышает количество цветов, необходимое для веретена Мозера. [2]

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

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

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

Добавление любого ребра к веретену Мозера приводит к графу, который нельзя вложить в плоскость как граф единичных расстояний, и не существует гомоморфизма графа от веретена Мозера к какому-либо меньшему графу единичных расстояний. Эти два свойства веретена Мозера использовали Horvat, Kratochvíl & Pisanski (2011), чтобы показать NP-трудность проверки того, имеет ли данный граф двумерное представление единичного расстояния; доказательство использует сокращение от 3SAT , в котором шпиндель Moser используются в качестве центральной истины устанавливающих гаджет в сокращении. [8]

Веретено Мозера также можно использовать для доказательства результата в теории Евклида Рамсея : если T - любой треугольник на плоскости, а точки на плоскости двухцветные: черный и белый, то существует либо черный перевод T, либо пара белых точек на единичном расстоянии друг от друга. Действительно, пусть М быть единицей расстояния вложение шпинделя Moser, и пусть М  +  Т быть сумма Минковского из M и  T . Если у M  +  T нет белой пары единиц измерения расстояния, то каждая из трех копий веретена Мозера в M  +  Tдолжно иметь не более двух белых точек, потому что белые точки в каждой копии должны образовывать независимый набор, а самый большой независимый набор в шпинделе Мозера имеет размер два. Следовательно, среди семи вершин веретена Мозера не более шести имеют белую копию в M  +  T , поэтому должна быть одна из семи вершин, все копии которых черные. Но тогда три копии этой вершины образует транслят Т . [7]

См. Также [ править ]

  • Граф Голомба

Ссылки [ править ]

  1. ^ Мозер, Л .; Мозер, В. (1961), "Решение проблемы 10", Can. Математика. Бык. , 4 : 187–189.
  2. ^ a b c d Сойфер, Александр (2008), Математическая книжка-раскраска: математика раскраски и красочная жизнь ее создателей , Нью-Йорк: Спрингер, стр. 14–15, ISBN 978-0-387-74640-1.
  3. ^ Бонди, JA; Мурти, USR (2008), Теория графов , Тексты для выпускников по математике, 244 , Springer, стр. 358, DOI : 10.1007 / 978-1-84628-970-5 , ISBN 978-1-84628-969-9.
  4. ^ Berge, C. (1989), "Минимаксные отношения для частичных q- раскраски графа", Дискретная математика , 74 (1-2): 3-14, DOI : 10.1016 / 0012-365X (89) 90193-3 , Руководство по ремонту 0989117  CS1 maint: discouraged parameter (link).
  5. ^ a b Hajós, G. (1961), "Über eine Konstruktion nicht n -färbbarer Graphen", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Рейхе , 10 : 116–117 CS1 maint: discouraged parameter (link).
  6. ^ Gervacio, Severino V .; Лим, Иветт Ф .; Маэхара, Hiroshi (2008), "Planar единицы расстояние графика , имеющая планарный блок-расстояние дополнения", дискретная математика , 308 (10): 1973-1984, DOI : 10.1016 / j.disc.2007.04.050 , МР 2394465 .
  7. ^ а б Беркерт, Джеффри; Джонсон, Питер (2011), «Лемма Шлама: мутантное потомство евклидовой проблемы Рамсея 1973 года с многочисленными приложениями», Теория Рамсея , Progr. . Математика, 285 ., Birkhäuser / Springer, Нью - Йорк, стр 97-113, DOI : 10.1007 / 978-0-8176-8092-3_6 , MR 2759046 . См. Также Soifer (2008) , Problem 40.26, p. 496.
  8. ^ a b Хорват, Борис; Кратохвил, Ян; Писанский, Томаж (2011), "О вычислительной сложности вырожденных представлений графов на единичном расстоянии", Комбинаторные алгоритмы: 21-й международный семинар, IWOCA 2010, Лондон, Великобритания, 26-28 июля 2010 г., Пересмотренные избранные статьи , Лекционные заметки на компьютере Science, 6460 , стр. 274–285, arXiv : 1001.0886 , Bibcode : 2011LNCS.6460..274H , doi : 10.1007 / 978-3-642-19222-7_28 , ISBN 978-3-642-19221-0.
  9. ^ Хаас, Рут ; Орден, Дэвид; Роте, Гюнтер; Сантос, Франциско ; Серватиус, Бриджит ; Серватий, Герман; Сувейн, Дайан ; Стрейну, Илеана ; Уайтли, Уолтер (2005), «Плоские минимально жесткие графы и псевдотриангуляции», Теория вычислительной геометрии и приложения , 31 (1-2): 31–61, arXiv : math / 0307347 , doi : 10.1016 / j.comgeo.2004.07 .003 , Руководство по ремонту 2131802 .
  10. ^ Winkler, Питер (ноябрь 2011), "недоумевает: Расстояния между точками на плоскости", коммуникации АСМА , 54 (11): 120, DOI : 10,1145 / 2018396,2018422 CS1 maint: discouraged parameter (link). Решение, выпуск 12, декабрь 2011, DOI : 10,1145 / 2043174,2043200 .

Внешние ссылки [ править ]

  • Вайсштейн, Эрик В. «Шпиндель Мозера» . MathWorld .