шпиндель Мозера
| шпиндель Мозера | |
|---|---|
 | |
| Назван в честь | Лео Мозер , Уильям Мозер |
| Вершины | 7 |
| Края | 11 |
| Радиус | 2 |
| Диаметр | 2 |
| Обхват | 3 |
| Автоморфизмы | 8 |
| Хроматическое число | 4 |
| Хроматический индекс | 4 |
| Характеристики | плоский единица расстояния Граф Ламана |
| Таблица графиков и параметров | |
В теории графов , разделе математики, веретено Мозера (также называемое веретеном Мозера или графом Мозера ) представляет собой неориентированный граф , названный в честь математиков Лео Мозера и его брата Уильяма, [1] с семью вершинами и одиннадцатью ребрами. Это граф единичных расстояний, требующий четырех цветов в любой раскраске графа , и его существование можно использовать для доказательства того, что хроматическое число плоскости не менее четырех. [2]
Веретено Мозера также называют графом Хайоша в честь Дьёрдя Хайоша , поскольку его можно рассматривать как пример конструкции Хайоша . [3] Однако название «график Хаджоса» также применялось к другому графику в форме треугольника, вписанного в шестиугольник. [4]
Строительство
[ редактировать ]
В качестве графа единичных расстояний веретено Мозера образовано двумя ромбами с углами 60 и 120 градусов, так что стороны и короткие диагонали ромбов образуют равносторонние треугольники. Два ромба расположены на плоскости, разделяя одну остроугольную вершину, так что оставшиеся две остроугольные вершины находятся на расстоянии единицы друг от друга. Одиннадцать ребер графа — это восемь сторон ромба, две короткие диагонали ромба и ребро между парой остроугольных вершин единичного расстояния.
Веретено Мозера также может быть построено теоретико-графовым методом, без ссылки на геометрическое вложение, с использованием конструкции Хайоса , начиная с двух полных графов на четырех вершинах. Эта конструкция удаляет ребро из каждого полного графа, объединяет две конечные точки удаленных ребер в одну вершину, общую для обеих клик, и добавляет новое ребро, соединяющее оставшиеся две конечные точки удаленного ребра. [5]
Другой способ построения веретена Мозера — это граф дополнения к графу, образованному из графа полезности K 3,3 путем разделения одного из его ребер. [6]
Приложение к задаче Хадвигера – Нельсона.
[ редактировать ]Задача Хадвигера -Нельсона спрашивает, сколько цветов необходимо, чтобы раскрасить точки евклидовой плоскости таким образом, чтобы каждой паре точек, находящихся на единичном расстоянии друг от друга, были присвоены разные цвета. То есть он запрашивает хроматическое число бесконечного графа, вершинами которого являются все точки плоскости, а ребрами — пары точек на единичном расстоянии. [2]
Веретено Мозера требует четырех цветов при любой раскраске графа: при любой трехраскраске одного из двух ромбов, из которых оно образовано, две остроугольные вершины ромба обязательно будут иметь один и тот же цвет. Но если общая вершина двух ромбов имеет тот же цвет, что и две противоположные остроугольные вершины, то эти две вершины имеют одинаковый цвет друг с другом, что нарушает требование, чтобы соединяющее их ребро имело концы разного цвета. Это противоречие показывает, что три цвета невозможны, поэтому необходимо как минимум четыре цвета. Четырех красок также достаточно, чтобы раскрасить веретено Мозера, что следует, например, из того факта, что его вырождение равно трем.
Альтернативное доказательство того, что веретено Мозера требует четырех цветов, следует из конструкции Хайоса. Оба полных графа, из которых формируется веретено Мозера, требуют четырех цветов, и конструкция Хайоса сохраняет это свойство. [5] Более того, каждое независимое множество в веретене Мозера имеет не более двух вершин: [7] поэтому для покрытия всех семи вершин требуется как минимум четыре независимых набора.
Поскольку веретено Мозера является подграфом бесконечного графа единичных расстояний плоскости, граф плоскости также требует не менее четырех цветов в любой раскраске. По теореме де Брейна-Эрдеша (при условии, что выбранная аксиома верна), хроматическое число плоскости такое же, как и наибольшее хроматическое число любого из ее конечных подграфов; до открытия семейства 5-хроматических графов единичных расстояний в 2018 году не было найдено ни одного подграфа графа бесконечных единичных расстояний, который требовал бы большего количества цветов, чем веретено Мозера. Однако лучшая верхняя граница хроматического числа плоскости — семь, что значительно превышает количество цветов, необходимое для веретена Мозера. [2]
Другие свойства и приложения
[ редактировать ]Веретено Мозера представляет собой плоский граф , то есть его можно нарисовать без пересечений на плоскости. Однако невозможно сформировать такой рисунок с прямыми краями, который также является рисунком на единицу расстояния; то есть это не график из спичек . Веретено Мозера также является графом Ламана , что означает, что оно образует минимально жесткую систему при вложении в плоскость. [8] Как планарный граф Ламана, это граф точечной псевдотриангуляции, что означает, что его можно вложить в плоскость таким образом, что неограниченная грань является выпуклой оболочкой вложения, а каждая ограниченная грань представляет собой псевдотреугольник только с тремя выпуклыми вершины. [9]
Граф дополнений графа Мозера представляет собой граф без треугольников . Таким образом, встраивание графа Мозера на единичное расстояние можно использовать для решения задачи о размещении семи точек на плоскости таким образом, чтобы каждая тройка точек содержала хотя бы одну пару на единичном расстоянии друг от друга. [2] [10]
Добавление любого ребра к веретену Мозера приводит к образованию графа, который не может быть вложен в плоскость как граф единичных расстояний, и не существует гомоморфизма графа от веретена Мозера к какому-либо меньшему графу единичных расстояний. Эти два свойства веретена Мозера были использованы Хорватом, Кратохвилом и Пизански (2011), чтобы показать NP-трудность проверки того, имеет ли данный граф двумерное представление единичного расстояния; в доказательстве используется редукция из 3SAT , в которой веретено Мозера используется в качестве центрального устройства для установления истины в редукции. [8]
Веретено Мозера также можно использовать для доказательства результата евклидовой теории Рамсея : если T — любой треугольник на плоскости, а точки плоскости — двухцветные, черно-белые, то существует либо черный перевод T , либо пара белых точек на единичном расстоянии друг от друга. Действительно, пусть M единичное расстояние, и пусть M + T — сумма Минковского M — и T. вложение веретена Мозера на Если M + T не имеет пары белых единичных расстояний, то каждая из трех копий веретена Мозера в M + T должна иметь не более двух белых точек, поскольку белые точки в каждой копии должны образовывать независимый набор и наибольшую независимую точку. установленный в шпинделе Moser имеет второй размер. Следовательно, среди семи вершин веретена Мозера не более шести имеют белую копию в M + T , поэтому из семи вершин должна быть одна, все копии которой черные. тогда три копии этой вершины образуют трансляцию T. Но [7]
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Мозер, Л .; Мозер, В. (1961), «Решение проблемы 10», кан. Математика. Бык. , 4 : 187–189, doi : 10.1017/S0008439500025753 , S2CID 246244722 .
- ^ Jump up to: Перейти обратно: а б с д Сойфер, Александр (2008), Математическая книжка-раскраска: математика раскраски и красочная жизнь ее создателей , Нью-Йорк: Springer, стр. 14–15, ISBN. 978-0-387-74640-1 .
- ^ Бонди, Дж.А.; Мурти, USR (2008), Теория графов , Тексты для выпускников по математике, том. 244, Спрингер, с. 358, номер домена : 10.1007/978-1-84628-970-5 , ISBN 978-1-84628-969-9 .
- ^ Берге, К. (1989), «Минимаксные соотношения для частичных q -раскрасок графа», Discrete Mathematics , 74 (1–2): 3–14, doi : 10.1016/0012-365X(89)90193-3 , МР 0989117 .
- ^ Jump up to: Перейти обратно: а б Хайос, Г. (1961), «О конструкции не -n- раскрашиваемых графов», Wiss. З. Мартина Лютера Univ. Галле-Виттенберг Математика-Природа. Серия , 10 : 116–117 .
- ^ Джервасио, Северино В.; Лим, Иветт Ф.; Маэхара, Хироши (2008), «Плоские графы единичных расстояний, имеющие плоское дополнение единичных расстояний», Discrete Mathematics , 308 (10): 1973–1984, doi : 10.1016/j.disc.2007.04.050 , MR 2394465 .
- ^ Jump up to: Перейти обратно: а б Буркерт, Джеффри; Джонсон, Питер (2011), «Лемма Шлама: мутантное потомство евклидовой проблемы Рамсея 1973 года, с многочисленными приложениями», Теория Рэмси , Progr. Матем., вып. 285, Биркхойзер/Спрингер, Нью-Йорк, стр. 97–113, номер документа : 10.1007/978-0-8176-8092-3_6 , MR 2759046 . См. также Сойфер (2008) , Задача 40.26, с. 496.
- ^ Jump up to: Перейти обратно: а б Хорват, Борис; Краточвил, Ян; Писански, Томаж (2011), «О вычислительной сложности вырожденных представлений графов на единичном расстоянии», Комбинаторные алгоритмы: 21-й международный семинар, IWOCA 2010, Лондон, Великобритания, 26–28 июля 2010 г., Переработанные избранные статьи , Конспекты лекций на компьютере Наука, том. 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 , S2CID 17585590 .
- ^ Хаас, Рут ; Орден, Дэвид; Роте, Гюнтер; Сантос, Франциско ; Серватиус, Бриджит ; Серватий, Герман; Сувен, Диана ; Стрейну, Илеана ; Уайтли, Уолтер (2005), «Плоские минимально жесткие графы и псевдотриангуляции», Теория и приложения вычислительной геометрии , 31 (1–2): 31–61, arXiv : math/0307347 , doi : 10.1016/j.comgeo.2004.07 .003 , МР 2131802 .
- ^ Винклер, Питер (ноябрь 2011 г.), «Загадка: расстояния между точками на плоскости», Communications of the ACM , 54 (11): 120, doi : 10.1145/2018396.2018422 , S2CID 195633418 . Решение, выпуск 12, декабрь 2011 г., дои : 10.1145/2043174.2043200 .