Теорема Гринберга (Mykjybg IjnuQyjig)

Перейти к навигации Перейти к поиску
Граф, негамильтоновость которого можно доказать с помощью теоремы Гринберга

Теорема Гринберга — необходимое условие для планарного графа, чтобы он содержал гамильтонов цикл, основанное на длинах циклов граней. Результат широко используется для построения негамильтоновых графов с дополнительными свойствами. Например, были построены новые контрпримеры гипотезе Тэйта (которую опроверг Татт в 1946 году). Теорему доказал латвийский математик Эмануэль Гринберг[англ.] в 1968 году.

Формулировка

[править | править код]

Пусть G — конечный планарный граф с гамильтоновым циклом C с фиксированным планарным вложением. Обозначим через ƒk и gk число k-угольных граней вложения, которые находятся внутри и вне C соответственно. Тогда

Эта формула является простым следствием формулы Эйлера.

Следствие этой теоремы — если планарный граф может быть вложен таким образом, что все грани, кроме одной, сравнимы с 2 по модулю 3, а одна грань не равна 2 по модулю 3, то граф не гамильтонов. Например, в графе на рисунке все грани имеют 5 или 8 сторон, а внешняя грань имеет 9 сторон, так что он удовлетворяет условию теоремы, а потому он не гамильтонов. Для любого планарного графа, грани, в которых число сторон сравнимо с 2 по модулю 3, дают 0 по модулю 3 в сумму в теореме Гринберга, поскольку множитель k − 2 в сумме для них обращается в нуль. Однако другие грани дают ненулевое по модулю 3 значение, независимо от того, находятся ли они внутри или вне гамильтонова цикла. И если имеется лишь одна такая грань, общая сумма не может быть нулевой и граф должен быть негамильтонов.

Приложения

[править | править код]

Гринберг использовал свою теорему для поиска негамильтоновых кубических полиэдральных графов с высокой циклической рёберной связностью. Циклическая рёберная связность графа — это наименьшее число рёбер, которое можно удалить так, чтобы оставшийся граф содержал более чем одну циклическую компоненту. Граф Татта с 46 вершинами и меньшие кубические негамильтоновы полиэдральные графы, полученные из него, имеют циклическую рёберную связность три. Гринберг использовал свою теорию для поиска негамильтонова кубического полиэдрального графа с 44 вершинами, 24 гранями и циклической рёберной связностью четыре, а также другого примера (показанного на рисунке) с 46 вершинами, 25 гранями и циклической рёберной связностью пять, максимально возможной рёберной связностью для кубических планарных графов, отличных от K4. В приведённом примере все ограниченные грани имеют пять или восемь рёбер, в обоих случаях число граней сравнимо с 2 по модулю 3, но внешняя грань имеет девять рёбер, что даёт ненулевой вклад в формуле в теореме Гринберга по модулю 3. Таким образом, граф не может быть гамильтоновым.

Теорема Гринберга используется также для поиска планарных гипогамильтоноввых графов, снова путём построения графа, в котором все грани имеют число рёбер, сравнимых с 2 по модулю 3[1][2]. Томассен[3] использовал теорему несколько более сложным образом, чтобы найти планарный кубический гипогамильтонов граф — построенный им граф включает грань с 4 рёбрами, смежную граням с 7 рёбрами, а все остальные грани имеют пять или восемь рёбер. Чтобы граф удовлетворял теореме Гринберга, нужно было бы отделить одну из граней с 4 или 7 рёбрами от остальных четырёх, что невозможно.

Ограничения

[править | править код]

Существуют планарные негамильтоновы графы, в которых все грани имеют пять или восемь сторон. Для этих графов формула Гринберга, взятая по модулю три, всегда удовлетворяет любому разбиению граней на два подмножества, что не даёт использовать теорему для доказательства негамильтоновости в этом случае (Zaks 1977).

Невозможно использовать теорему Гринберга для поиска контрпримеров гипотезе Барнетта, что любой кубический двудольный полиэдральный граф гамильтонов. В этих графах всегда существует разбиение граней на два подмножества, удовлетворяющих теореме Гринберга, независимо от гамильтоновости (Krooss 2004).

Примечания

[править | править код]

Литература

[править | править код]
  • Э. Я. Гринберг. Плоские однородные графы степени три без гамильтоновых циклов. // Латв. матем. ежегодник. — Т. 4. — С. 51—58..
  • André Krooss. Die Barnette'sche Vermutung und die Grinberg'sche Formel (нем.) // Analele Universităţii din Craiova. Seria Matematică-Informatică. — 2004. — Bd. 31. — S. 59–65.
  • Joseph Malkevitch. Euler's Polyhedral Formula: Part II. — American Mathematical Society, 2005. — (Feature Column).
  • Carsten Thomassen. Planar and infinite hypohamiltonian and hypotraceable graphs // Discrete Mathematics. — 1976. — Т. 14, вып. 4. — С. 377–389. — doi:10.1016/0012-365X(76)90071-6.
  • Carsten Thomassen. Planar cubic hypo-Hamiltonian and hypotraceable graphs // Journal of Combinatorial Theory. — 1981. — Т. 30, вып. 1. — С. 36–44. — doi:10.1016/0095-8956(81)90089-7.
  • Gábor Wiener, Makoto Araya. The ultimate question. — 2009. — arXiv:0904.3012.
  • W. T. Tutte. Chapter 2: Knights Errant // Graph theory as I have known it. — New York: The Clarendon Press Oxford University Press, 1998. — Т. 11. — (Oxford Lecture Series in Mathematics and its Applications). — ISBN 0-19-850251-6.
  • Joseph Zaks. Non-Hamiltonian non-Grinbergian graphs // Discrete Mathematics. — 1977. — Т. 17, вып. 3. — С. 317–321. — doi:10.1016/0012-365X(77)90165-0.