78
правок
Изменения
→Использование теоремы
<tex>\Rightarrow</tex>. Пусть <tex>E</tex> {{---}} бонд. Докажем, что для любого ребра <tex>e \in E</tex> граф <tex>G - E + e</tex> связен. Действительно, пусть этот граф несвязен и имеет, скажем, компоненты связности <tex>U_1</tex> и <tex>U_2</tex>. Тогда <tex>E \supsetneq E(U_1, U_2)</tex>, а из связности графа <tex>G</tex> следует, что <tex>E(U_1, U_2) \neq \varnothing</tex>. Противоречие с минимальностью <tex>E</tex>.
Теперь докажем, что подграфы <tex>G(V_1) \text{ и } G(V_2)</tex> связны. Рассмотрим отдельно подграф <tex>G(V_1)</tex>, если он не связный, то имеет как минимум <tex>2</tex> компоненты связности, назовем их <tex>O_1 \text{ и } O_2</tex>.
<tex>e \in E </tex> можно также представить как <tex>e = (u, v) \text{ при этом } u \in G(V_1), v \in G(V_2)</tex>, то есть <tex>u \in O_1 \mid u \in O_2</tex>, и граф <tex> G - E + e </tex> состоит из <tex>2</tex> компонент {{---}} <tex>(O_1 \cup G(V_2), O_2) \mid (O_2 \cup G(V_2), O_1)</tex>, что противоречит условию связности. Так же доказывается связность <tex>G(V_2)</tex>.
== Использование теоремы ==
* Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические (все вершины имеют степень <tex>3</tex>) полиэдральные графы<ref>[https://ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%BB%D0%B8%D1%8D%D0%B4%D1%80%D0%B0%D0%BB%D1%8C%D0%BD%D1%8B%D0%B9_%D0%B3%D1%80%D0%B0%D1%84 полиэдральные графыВикипедия {{---}} Полиэдральный граф] </ref> с высокой циклической реберной связностью. Циклическая рёберная связность графа {{---}} это наименьшее число рёбер, которое можно удалить так, чтобы оставшийся граф содержал более чем одну циклическую компоненту. Например он нашел граф с <tex>46</tex> вершинами, <tex>25</tex> гранями и циклической рёберной связностью пять, показанный на рисунке <tex>1</tex>.
{|align="center"
* Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа <tex> G </tex>, кроме одной, имеют степени, сравнимые с <tex>2</tex> по модулю <tex>3</tex>. Тогда левая часть формулы <tex>\textbf{(1)}</tex> не делится на <tex>3</tex> и, следовательно, гамильтонова бонда в графе <tex> G </tex> не существует. Рисунок <tex>2</tex> иллюстрирует этот простой пример.
* Теорема Гринберга {{---}} необходимое условие для планарного графа, чтобы Чтобы планарный граф существовал и содержал гамильтонов цикл, основанное на длинах циклов гранейнеобходимо выполнение теоремы Гринберга.<ref>Grinberg, È. Ja. (1968), "Plane homogeneous graphs of degree three without Hamiltonian circuits", Latvian Math. Yearbook 4 (in Russian), Riga: Izdat. “Zinatne”, pp. 51–58, MR 0238732. English translation by Dainis Zeps, [https://arxiv.org/abs/0908.2563v1 arXiv:0908.2563.]</ref>* Теорема Гринберга используется также для поиска планарных гипогамильтоновых графов<ref>[https://ru.wikipedia.org/wiki/%D0%93%D0%B8%D0%BF%D0%BE%D0%B3%D0%B0%D0%BC%D0%B8%D0%BB%D1%8C%D1%82%D0%BE%D0%BD%D0%BE%D0%B2_%D0%B3%D1%80%D0%B0%D1%84 гипогамильтоновых графовВикипедия {{---}} Гипогамильтонов граф] </ref> путём построения графа, в котором все грани имеют число рёбер, сравнимых с <tex>2</tex> по модулю <tex>3</tex>.
== См. также ==
* [[Лемма о рукопожатиях]]
* [[Дерево, эквивалентные определения]]
== Примечания ==
<references />
== Источники информации ==
