В теории графов , разделе математики, веретено Мозера (также называемое веретеном Мозера или графом Мозера ) представляет собой неориентированный граф , названный в честь математиков Лео Мозера и его брата Уильяма [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]