Теорема Гринберга

В теории графов теорема Гринберга является необходимым условием для того, чтобы планарный граф содержал гамильтонов цикл , на основе длин его гранных циклов. Если граф не удовлетворяет этому условию, он не является гамильтоновым. Результат широко использовался для доказательства того, что некоторые планарные графы, построенные так, чтобы иметь дополнительные свойства, не являются гамильтоновыми; например, он может доказать негамильтоновость некоторых контрпримеров к гипотезе Тейта о том, что кубические полиэдральные графы являются гамильтоновыми.

Теорема Гринберга названа в честь латвийского математика Эмануэля Гринберга , который доказал ее в 1968 году.

Планарный граф — это граф, который можно нарисовать без пересечений на евклидовой плоскости . Если точки, принадлежащие вершинам и ребрам, удалить из плоскости, связные компоненты оставшихся точек образуют многоугольники, называемые гранями , включая неограниченную грань, простирающуюся до бесконечности. Грань является -угольником, если ее граница образована циклом вершин и ребер рисунка графа. Гамильтонов цикл в графе — это цикл, который проходит через каждую вершину ровно один раз. Пусть — конечный планарный граф с гамильтоновым циклом , с фиксированным планарным рисунком. По теореме о кривой Жордана , разделяет плоскость на подмножество внутри и подмножество снаружи ; каждая грань принадлежит одному из этих двух подмножеств. Обозначим через и число -угольных граней рисунка, которые находятся внутри и снаружи соответственно . Тогда теорема Гринберга утверждает, что Доказательство является простым следствием формулы Эйлера . ^{[1] [2]}${\displaystyle к}$${\displaystyle к}$${\displaystyle к}$${\displaystyle G}$${\displaystyle С}$${\displaystyle С}$${\displaystyle С}$${\displaystyle С}$${\displaystyle f_{k}}$${\displaystyle g_{k}}$${\displaystyle к}$${\displaystyle С}$$${\displaystyle \sum _{k\geq 3}(k-2)(f_{k}-g_{k})=0.}$$

Как следствие этой теоремы, если вложенный планарный граф имеет только одну грань, число сторон которой не равно 2 mod 3, а все остальные грани имеют число сторон, равное 2 mod 3, то граф не является гамильтоновым. Чтобы убедиться в этом, рассмотрим сумму формы, указанной в формулировке теоремы, для произвольного разбиения граней на два подмножества, подсчитанных числами и . Каждая грань, число сторон которой равно 2 mod 3, вносит в сумму кратный трем вклад из-за множителя в члене, в который она вносит вклад, в то время как одна оставшаяся грань — нет. Следовательно, сумма не кратна трем и, в частности, не равна нулю. Поскольку нет способа разбить грани на два подмножества, которые дадут сумму, подчиняющуюся теореме Гринберга, не может быть гамильтонова цикла. ^[1] Например, для графа на рисунке все ограниченные грани имеют 5 или 8 сторон, но неограниченная грань имеет 9 сторон, поэтому она удовлетворяет этому условию по числу сторон и не является гамильтоновой.${\displaystyle f_{k}}$ ${\displaystyle g_{k}}$${\displaystyle к-2}$

Гринберг использовал свою теорему для поиска негамильтоновых кубических полиэдральных графов с высокой циклической связностью ребер. Циклическая связность ребер графа — это наименьшее число ребер, удаление которых оставляет подграф с более чем одним циклическим компонентом. Граф Тутта с 46 вершинами и меньшие кубические негамильтоновы полиэдральные графы, полученные из него, имеют циклическую связность ребер три. Гринберг использовал свою теорему для поиска негамильтонова кубического полиэдрального графа с 44 вершинами, 24 гранями и циклической связностью ребер четыре, а также еще один пример (показанный на рисунке) с 46 вершинами, 25 гранями и циклической связностью ребер пять, максимально возможной циклической связностью ребер для кубического планарного графа, отличного от .${\displaystyle К_{4}}$ В показанном примере все ограниченные грани имеют либо пять, либо восемь ребер, оба из которых являются числами, равными 2 mod 3, но неограниченная грань имеет девять ребер, не равных 2 mod 3. Следовательно, по следствию из теоремы Гринберга, граф не может быть гамильтоновым. ^[1]

Теорема Гринберга также использовалась для поиска плоских гипогамильтоновых графов , графов, которые не являются гамильтоновыми, но которые можно сделать гамильтоновыми, удалив любую одну вершину. Конструкция снова делает все грани, кроме одной, имеющими число ребер, конгруэнтное 2 mod 3. ^[3] Томассен (1981) использует теорему несколько более сложным способом для поиска плоского кубического гипогамильтонова графа: граф, который он строит, включает грань с 4 ребрами, смежную с четырьмя гранями с 7 ребрами, а все остальные грани имеют пять или восемь ребер. Чтобы удовлетворить теореме Гринберга, гамильтонов цикл должен был бы отделить одну из граней с 4 или 7 ребрами от остальных четырех, что невозможно . ^[4]

Его также можно применять для анализа гамильтоновых циклов некоторых непланарных графов, таких как обобщенные графы Петерсена , путем нахождения больших планарных подграфов этих графов, используя теорему Гринберга, чтобы показать, что эти подграфы являются негамильтоновыми, и сделать вывод, что любой гамильтонов цикл должен включать некоторые из оставшихся ребер, которые не являются частью этих подграфов. ^[5]

Существуют планарные негамильтоновы графы, в которых все грани имеют пять или восемь сторон. Для этих графов формула Гринберга, взятая по модулю три, всегда удовлетворяется любым разбиением граней на два подмножества, что препятствует применению его теоремы для доказательства негамильтоновости в этом случае. ^[6]

Невозможно использовать теорему Гринберга для поиска контрпримеров к гипотезе Барнетта о том, что каждый кубический двудольный полиэдральный граф является гамильтоновым. Каждый кубический двудольный полиэдральный граф имеет разбиение граней на два подмножества, удовлетворяющее теореме Гринберга, независимо от того, имеет ли он также гамильтонов цикл. ^[7]

• Графы Гринберга из MathWorld .