В теории графов , Гринберг это теорема является необходимым условием для плоского графа содержать гамильтонов цикл , основанный на длин ее циклов лица. Результат был широко используется для построения негамильтоновых планарных графов с дальнейшим свойствами, такими как дать новые контрпримеры к гипотезе Тейта (первоначально опровергнуто WT Татта в 1946 году). Эта теорема была доказана латвийским математиком Эмануэлем Гринбергом в 1968 году.
Формулировка
Пусть G - конечный планарный граф с гамильтоновым циклом C с фиксированным планарным вложением. Обозначим через ƒ k и g k количество k -угольных граней вложения, находящихся внутри и вне C соответственно. потом
Доказательство легко следует из формулы Эйлера .
Как следствие этой теоремы, если вложенный плоский граф имеет только одну грань, количество сторон которой не равно 2 mod 3, а все остальные грани имеют номера сторон, равные 2 mod 3, то граф не является гамильтоновым. В этом случае только первая грань вносит вклад в значение mod-3 суммы, и это приводит к тому, что сумма не равна нулю. Коэффициент k - 2 во вкладах для других граней приводит к тому, что их вклады равны нулю по модулю 3. Например, для графа на рисунке все ограниченные грани имеют 5 или 8 сторон, но неограниченная грань имеет 9 сторон, поэтому он удовлетворяет этому условию и не является гамильтоновым.
Приложения
Гринберг использовал свою теорему, чтобы найти негамильтоновы кубические многогранные графы с высокой циклической связностью ребер. Циклическая связность ребер графа - это наименьшее количество ребер, удаление которых оставляет подграф с более чем одним циклическим компонентом. Граф Тутте с 46 вершинами и меньшие кубические негамильтоновы многогранные графы, производные от него, имеют циклическую связность ребер три. Гринберг использовал свою теорему, чтобы найти негамильтонов кубический многогранный граф с 44 вершинами, 24 гранями и четырьмя циклическими связностями ребер, а также другой пример (показанный на рисунке) с 46 вершинами, 25 гранями и пятью циклическими связностями ребер, максимум возможная циклическая связность ребер для кубического плоского графа, отличного от K 4 . В показанном примере все ограниченные грани имеют пять или восемь ребер, оба из которых являются числами, равными 2 по модулю 3, но неограниченная грань имеет девять ребер, не равных 2 по модулю 3. Следовательно, по следствию теоремы Гринберга , граф не может быть гамильтоновым.
Теорема Гринберга также использовалась для поиска плоских гипогамильтоновых графов , графов, которые не являются гамильтоновыми, но которые можно сделать гамильтоновыми, удалив любую единственную вершину. Конструкция снова заставляет все грани, кроме одной, иметь несколько ребер, соответствующих 2 mod 3 ( Thomassen 1976 , Wiener & Araya 2009 ). Томассен (1981) использует теорему несколько более сложным способом, чтобы найти плоский кубический гипогамильтонов граф: построенный им граф включает грань с 4 ребрами, смежную с четырьмя гранями с 7 ребрами, а все остальные грани имеют пять или восемь ребер. Чтобы удовлетворить теорему Гринберга, гамильтонов цикл должен отделить одну из четырех или семи граней от четырех других, что невозможно.
Ограничения
Существуют плоские негамильтоновы графы, в которых все грани имеют пять или восемь сторон. Для этих графов формула Гринберга, взятая по модулю три, всегда удовлетворяется любым разбиением граней на два подмножества, что препятствует применению его теоремы для доказательства негамильтонности в этом случае ( Zaks 1977 ).
Невозможно использовать теорему Гринберга, чтобы найти контрпримеры к гипотезе Барнетта о том , что каждый кубический двудольный многогранный граф является гамильтоновым. Каждый кубический двудольный многогранный граф имеет разбиение граней на два подмножества, удовлетворяющих теореме Гринберга, независимо от того, имеет ли он также гамильтонов цикл ( Krooss 2004 ).
Рекомендации
- Гринберг, È. Ja. (1968), "Плоские однородные графы степени три без гамильтоновых схем", Latvian Math. Ежегодник 4 , Рига: Издат. «Зинатне», стр. 51–58, MR 0238732. Английский перевод Дайниса Зепса, arXiv : 0908.2563 .
- Кросс, Андре (2004), "Die Barnette'sche Vermutung und die Grinberg'sche Formel", Analele Universităţii в Крайове. Seria Matematică-Informatică (на немецком языке), 31 : 59–65, MR 2153849.
- Малькевич, Джозеф (январь 2005 г.), Многогранная формула Эйлера: Часть II , Feature Column, Американское математическое общество.
- Томасно, Карстен (1976), "плоскостной и бесконечное hypohamiltonian и hypotraceable графики", дискретная математика , 14 (4): 377-389, DOI : 10.1016 / 0012-365X (76) 90071-6 , МР 0422086.
- Томассен, Карстен (1981), «Плоские кубические гипогамильтоновы графы и отслеживаемые гипотезы», Журнал комбинаторной теории , серия B, 30 (1): 36–44, DOI : 10.1016 / 0095-8956 (81) 90089-7 , MR 0609592.
- Винер, Габор; Арая, Макото (2009), Последний вопрос , arXiv : 0904.3012 , Bibcode : 2009arXiv0904.3012W.
- Тутт, В. Т. (1998), «Глава 2: Странствующие рыцари», Теория графов, как я ее знал , Оксфордская серия лекций по математике и ее приложениям, 11 , Нью-Йорк: The Clarendon Press Oxford University Press, ISBN 0-19-850251-6, Руководство по ремонту 1635397.
- Закс, Джозеф (1977), "негамильтонов без Grinbergian графов", Дискретная математика , 17 (3): 317-321, DOI : 10.1016 / 0012-365X (77) 90165-0 , MR 0460189.
Внешние ссылки
- Графики Гринберга , из MathWorld .