Grinberg's theorem

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

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

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

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

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

Приложения

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

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

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

Ограничения

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

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

Примечания

^ Перейти обратно: ^а ^б ^с Grinberg 1968 .
^ Малкевич 2005 .
^ Томассен 1976 , Винер и Арайя 2009 .
^ Томассен 1981 .
^ Чиа и Томассен 2011 .
^ Зак 1977 .
^ Кроосс 2004 .

Ссылки

Чиа, GL; Томассен, Карстен (2011), «Критерий Гринберга, примененный к некоторым неплоским графам» (PDF) , Ars Combinatoria , 100 : 3–7, MR 2829474
Гринберг, Э. Джа. (1968), «Плоские однородные графы степени три без гамильтоновых схем», Латвийская математика. Ежегодник 4 (на русском языке), Рига: Издат. «Зинатне», стр. 51–58, МР 0238732 ; Английский перевод Дайниса Зепса, arXiv : 0908.2563
Кросс, Андре (2004), «Die Barnette'sche Vermutung und die Grinberg'sche Formel», Анналы Университета Крайовы. Серия «Математика-информатика» (на немецком языке), 31 : 59–65, MR 2153849.
Малкевич, Джозеф (январь 2005 г.), Многогранная формула Эйлера: Часть II , Тематическая колонка, Американское математическое общество
Томассен, Карстен (1976), «Плоские и бесконечные гипогамильтоновы и гипопрослеживаемые графы», Discrete Mathematics , 14 (4): 377–389, doi : 10.1016/0012-365X(76)90071-6 , MR 0422086
Томассен, Карстен (1981), «Плоские кубические гипогамильтоновы и гипопрослеживаемые графы», Журнал комбинаторной теории , серия B, 30 (1): 36–44, doi : 10.1016/0095-8956(81)90089-7 , MR 0609592
Винер, Габор; Арайя, Макото (2009), Самый главный вопрос , arXiv : 0904.3012 , Бибкод : 2009arXiv0904.3012W
Закс, Джозеф (1977), «Негамильтоновы негринберговы графы», Discrete Mathematics , 17 (3): 317–321, doi : 10.1016/0012-365X(77)90165-0 , MR 0460189

Внешние ссылки

Grinberg Graphs , from MathWorld .

[FOOTNOTEGrinberg1968-1] Перейти обратно: ^а ^б ^с Grinberg 1968 .

[FOOTNOTEMalkevitch2005-2] Малкевич 2005 .

[3] Томассен 1976 , Винер и Арайя 2009 .

[FOOTNOTEThomassen1981-4] Томассен 1981 .

[FOOTNOTEChiaThomassen2011-5] Чиа и Томассен 2011 .

[FOOTNOTEZaks1977-6] Зак 1977 .

[FOOTNOTEKrooss2004-7] Кроосс 2004 .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]