В теории графов , разделе математики, веретено Мозера (также называемое веретеном Мозера или графом Мозера ) — неориентированный граф , названный в честь математиков Лео Мозера и его брата Уильяма [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 должна иметь не более двух белых точек, поскольку белые точки в каждой копии должны образовывать независимое множество , а наибольшее независимое множество в веретене Мозера имеет размер два. Следовательно, среди семи вершин веретена Мозера не более шести имеют белую копию в M + T , поэтому должна быть одна из семи вершин, все копии которой черные. Но тогда три копии этой вершины образуют трансляцию T. [7 ]