Изменения

Теорема Гринберга== Базовые определения =={{Определение|definition='''Подграф''' (англ. ''subgraph'') исходного графа {{---}} граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. По отношению к подграфу исходный граф называется суперграфом.}} {{Определение|definition='''Бонд''' (англ. 'Grinberg'bond'') графа {{- необходимое условие содержания --}} это минимальный (по включению) непустой [[Гамильтоновы графыРазрез,_лемма_о_потоке_через_разрез |гамильтонова цикларазрез графа]] <tex>G</tex>. }} {{Определение|definition='''Минимальный (по включению)''' (англ. ''minimal by inclusion'') разрез графа <tex>G</tex> {{---}} разрез, из которого нельзя выделить разрезы с меньшим количеством ребер. }} {{Лемма|statement=Разрез <tex>E(V_1, V_2)</tex> связного графа <tex>G</tex> является '''бондом''', если и только если оба графа <tex>G(V_1)</tex> и <tex>G(V_2)</tex> связны.|proof=Для удобства примем <tex>E = E(V_1, V_2)</tex>.  <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>\Leftarrow</tex>. Если оба графа <tex>G(V_1)</tex> и <tex>G(V_2)</tex> — связны, то добавление любого ребра из <tex>E</tex> даст нам связный подграф графа <tex>G</tex>, содержащий все его вершины. Значит, в этом случае разрез <tex>E</tex> минимален по включению. В силу связности <tex>G</tex> этот разрез непуст, то есть, является бондом.}} {{Определение|definition=Подграфы <tex>V_1</tex> и <tex>V_2</tex> из предыдущей леммы называются '''торцевыми графами''' (англ. ''end graph'').}}Также стоит отметить, что если граф <tex> G </tex> несвязен, то его '''бонд''' определим как бонд какой-либо его компоненты, а всякий [[Укладка графа на плоскостиМост,_эквивалентные_определения |планарныммост]] графомграфа образует однореберный бонд. Торцевые графы моста являются торцевыми графами соответствующего бонда. {{Определение|definition='''Гамильтоновым бондом''' (англ. ''hamiltonian bond'') называется бонд графа <tex> G </tex>, торцевыми графами которого являются деревья.}}

|aboutauthor=ГринбергаГринберг

Пусть связный граф <tex>G</tex> плоский граф без петель с гамильтоновым циклом имеет гамильтонов бонд <tex>CH </tex>, который делит плоскости на две области с торцевыми графами <tex>RX </tex> и <tex>R'Y </tex>. Пусть <tex>k_if_n^{X} </tex> и <tex>k'_if_n^{Y} </tex> {{---}} количества граней размера число вершин в графов <tex> X </tex> и <tex>iY </tex> соответственно, имеющих в <tex>RG </tex> и степень <tex>R'n ~ (n = 1, ~ 2, ~ 3, ~ \ldots) </tex> соответственно. Тогда:<mathcenter> <tex>\sum_sum\limits_{in=31}^{V(G)\infty}(in -2)(k_if_n^{X} -k'_if_n^{Y})=0~~~ \bf{(1)} </tex>. </mathcenter>

ОтметимТак как торцевые графы являются деревьями, что в гамильтоновом графе то количество их вершин на единицу больше количества ребер:<center> <tex> \sum\limits_{n=1}^{\infty} f_n^{X} = |V(X)| = |E(X)| + 1 ~~~ \textbf{(2)} </tex>G. </center>Посчитаем <tex>, очевидно, нет мостов и граница любой грани \sum\limits_{n=1}^{---\infty}n f_n^{X} простой цикл</tex>, то есть количество всех исходящих ребер из <tex>X</tex>. Поэтому размер границы каждой его грани не более По [[Лемма_о_рукопожатиях | лемме о рукопожатиях]] ребер, с обоих сторон прикрепленных к <tex>X</tex>, будет <tex>V2|E(GX)|</tex>. Пусть Количество ребер, прикрепленных и к <tex>eX</tex> , и к <tex>e'Y</tex> , по определению бонда {{---}} количества рёбер графа количество ребер в бонде <tex>GH</tex>, лежащих внутри областей то есть <tex>R|E(H)|</tex> и . Отсюда:<center> <tex>R'\sum\limits_{n=1}^{\infty} n f_n^{X} = |E(H)| + 2|E(X)| ~~~ \textbf{(3)} </tex> соответственно. Так как </center>Вычитаем дважды из формулы <tex>\textbf{(3)}</tex> формулу <tex>C\textbf{(2)}</tex> и получаем:<center> <tex>\sum\limits_{n=1}^{\infty} (n -2) f_n^{X} = |E(H)| --2 ~~~ \textbf{(4)}} гамильтонов цикл графа </tex>G. </texcenter>Полученная формула в правой части не зависит от подграфа, то область R разбита на поэтому вычитая вариант для <tex>e + 1Y </tex> граней. а область из <tex>R'\textbf{(4)}</tex> {{---}} на , приходим к <tex>e' + \textbf{(1)}</tex> граней. Получаем соотношения:}}

(1) <math>\sum_{i=3}^{V(G)}k_i=e+1</math>, <math>\sum_{iИспользование теоремы =3}^{V(G)}k'_i=e'+1</math>

Каждое внутреннее ребро области * Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические (все вершины имеют степень <tex>R3</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>R46</tex>вершинами, а каждое ребро цикла <tex>C25</tex> {{---}} в границу одной внутренней грани этой области. Аналогичное соотношение верно гранями и для циклической рёберной связностью пять, показанный на рисунке <tex>R'1</tex>. Следовательно,

(2) <math>\sum_{i|align=3}^{V(G)"center" |[[Файл: Гамильтонов граф.png|300px|center|thumb|Рис. 1]] |[[Файл: Новый гамильтонов_бонд.png|500x300px|thumb|Рис. 2]] |}i*k_i=2e+E(C)</math>, <math>\sum_{i=3}^{V(G)}i*k'_i=2e'+E(C)</math>

Из соотношений * Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа <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 (2in 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>.

<math>\sum_{i=3}^{V(G)}i(k_i-k'_i)=2(e - e')См. также =\sum_{i=3}^{V(G)}2(k_i-k'_i)</math>* [[Гамильтоновы графы]]* [[Разрез, лемма о потоке через разрез]]* [[Лемма о рукопожатиях]]* [[Дерево, эквивалентные определения]]

}}== Источники информации ==* У. Татт. Теория графов. М.: "Мир", 1988. с. 304. ISBN 5-03-001001-7* [https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf Д.В. Карпов. Теория графов. c. 301] [[Категория:Алгоритмы и структуры данных]][[Категория:Обходы графов]][[Категория:Гамильтоновы графы]]