Изменения

Теорема Гринберга== Базовые определения =={{Определение|definition='''Подграф''' (англ. ''subgraph'') исходного графа {{---}} граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. По отношению к подграфу исходный граф называется суперграфом.}} {{Определение|definition='''GrinbergБонд''' (англ. ''bond'') графа {{- необходимое условие содержания --}} это минимальный (по включению) непустой [[Гамильтоновы графыРазрез,_лемма_о_потоке_через_разрез |гамильтонова цикларазрез графа]] [[Укладка <tex>G</tex>. }} {{Определение|definition='''Минимальный (по включению)''' (англ. ''minimal by inclusion'') разрез графа на плоскости|планарным]] графом<tex>G</tex> {{---}} разрез, из которого нельзя выделить разрезы с меньшим количеством ребер.}}

{{Теорема|about=ГринбергаЛемма

Пусть Разрез <tex>GE(V_1, V_2)</tex> плоский граф без петель с гамильтоновым циклом связного графа <tex>CG</tex>является '''бондом''', который делит плоскости на две области <tex>R</tex> если и только если оба графа <tex>R'</tex>. Пусть <tex>k_i</tex> и <tex>k'_i</tex> {{---}} количества граней размера <tex>i</tex> в <tex>RG(V_1)</tex> и <tex>R'</tex> соответственно. Тогда <math>\sum\limits_{i=3}^{V(G)}(i-2)(k_i-k'_iV_2)=0</mathtex>связны.

[[Файл: HamiltonExampleR.png|300px|thumb|right|Пример. Рёбра из гамильтонова цикла выделены красным]]Отметим, что в гамильтоновом графе Для удобства примем <tex>G</tex>, очевидно, нет [[МостE = E(V_1, эквивалентные определения|мостов]] и граница любой грани {{---}} простой цикл. Поэтому размер границы каждой его грани не более <tex>V(GV_2)</tex>. Пусть <tex>e</tex> и <tex>e'</tex> {{---}} количества рёбер графа <tex>G</tex>, лежащих внутри областей <tex>R</tex> и <tex>R'</tex> соответственно. Так как <tex>C</tex> {{---}} гамильтонов цикл графа <tex>G</tex>, то область <tex>R</tex> разбита на <tex>e + 1</tex> граней. а область <tex>R'</tex> {{---}} на <tex>e' + 1</tex> граней. Получаем соотношения:

(1) <mathtex>\sum\limits_Rightarrow</tex>. Пусть <tex>E</tex> {{i=3---}^{V(G)}k_i=бонд. Докажем, что для любого ребра <tex>e\in E</tex> граф <tex>G - E +1e</mathtex>связен. Действительно, пусть этот граф несвязен и имеет, скажем, компоненты связности <tex>U_1</tex> и <mathtex>U_2</tex>. Тогда <tex>E \sum\limits_{i=3}^{Vsupsetneq E(U_1, U_2)</tex>, а из связности графа <tex>G</tex> следует, что <tex>E(U_1, U_2)}k'_i=e'+1\neq \varnothing</tex>. Противоречие с минимальностью <tex>E</mathtex>.

Каждое внутреннее ребро области Теперь докажем, что подграфы <tex>RG(V_1) \text{ и } G(V_2)</tex> входит в границы двух внутренних граней области связны. Рассмотрим отдельно подграф <tex>RG(V_1)</tex>, а каждое ребро цикла если он не связный, то имеет как минимум <tex>C2</tex> {{---}} в границу одной внутренней грани этой области. Аналогичное соотношение верно и для компоненты связности, назовем их <tex>R'O_1 \text{ и } O_2</tex>. Следовательно,

(2) <mathtex>e \sumin E </tex> можно также представить как <tex>e = (u, v) \limits_text{i=3при этом }^{Vu \in G(GV_1)}i , v \cdot k_i=2e+Ein G(CV_2)</mathtex>, то есть <mathtex>u \in O_1 \summid u \limits_in O_2</tex>, и граф <tex> G - E + e </tex> состоит из <tex>2</tex> компонент {{i=3---}}^{V<tex>(O_1 \cup G(V_2), O_2)}i \cdot k'_i=2e'+Emid (O_2 \cup G(V_2), O_1)</tex>, что противоречит условию связности. Так же доказывается связность <tex>G(CV_2)</mathtex>.

Из соотношений <tex>\Leftarrow</tex>. Если оба графа <tex>G(1V_1) </tex> и <tex>G(2V_2) получаем: </tex> — связны, то добавление любого ребра из <tex>E</tex> даст нам связный подграф графа <tex>G</tex>, содержащий все его вершины. Значит, в этом случае разрез <tex>E</tex> минимален по включению. В силу связности <tex>G</tex> этот разрез непуст, то есть, является бондом.}}

{{Определение|definition=Подграфы <tex>V_1</tex> и <tex>V_2<math/tex>\sum\limits_{i=3}^{Vиз предыдущей леммы называются '''торцевыми графами''' (G)}i(k_i - kангл. ''end graph'_i)=2(e - e')=\sum\limits_{i=3.}}^{V(Также стоит отметить, что если граф <tex> G)}2(k_i-k'_i)</mathtex>несвязен, то его '''бонд''' определим как бонд какой-либо его компоненты, а всякий [[Мост,_эквивалентные_определения | мост]] графа образует однореберный бонд. Торцевые графы моста являются торцевыми графами соответствующего бонда.

откуда немедленно следует доказываемое утверждение{{Определение|definition='''Гамильтоновым бондом''' (англ. ''hamiltonian bond'') называется бонд графа <tex> G </tex>, торцевыми графами которого являются деревья.

Используя свою теорему, == Теорема Гринберга =={{Теорема|author=Гринберг построил трёхсвязный кубический плоский |statement=Пусть связный граф, в котором ровно одна грань <tex> G </tex> имеет гамильтонов бонд <tex>9H </tex> с торцевыми графами <tex> X </tex> и <tex> Y </tex>. Пусть <tex> f_n^{X} </tex> и <tex> f_n^{Y} </tex> рёбер, а все остальные {{---}} по число вершин в графов <tex> X </tex> и <tex> Y </tex> соответственно, имеющих в <tex>5G </tex> или степень <tex>8n ~ (n = 1, ~ 2, ~ 3, ~ \ldots) </tex> рёбер. Тогда:Левая часть соотношения <mathcenter> <tex>\sum\limits_{in=31}^{V(G)\infty}(in -2)(k_if_n^{X} -k'_if_n^{Y})=0~~~ \bf{(1)} </mathtex>. </center>|proof=Так как торцевые графы являются деревьями, то количество их вершин на единицу больше количества ребер:<center> <tex> \sum\limits_{n=1}^{\infty} f_n^{X} = |V(X)| = |E(X)| + 1 ~~~ \textbf{(2)} </tex>. </center>Посчитаем <tex> \sum\limits_{n=1}^{\infty} n f_n^{X} </tex>, то есть количество всех исходящих ребер из <tex>X</tex>. По [[Лемма_о_рукопожатиях | лемме о рукопожатиях]] ребер, с обоих сторон прикрепленных к <tex>X</tex> в таком графе, очевиднобудет <tex>2|E(X)|</tex>. Количество ребер, не делится на прикрепленных и к <tex>X</tex>, и к <tex>3Y</tex>, так как сравнима по модулю определению бонда {{---}} количество ребер в бонде <tex>H</tex>, то есть <tex>|E(H)|</tex>. Отсюда:<center> <tex> \sum\limits_{n=1}^{\infty} n f_n^{X} = |E(H)| + 2|E(X)| ~~~ \textbf{(3)} </tex>. </center>Вычитаем дважды из формулы <tex> с \textbf{(3)}</tex> формулу <tex>\textbf{(2)}</tex> и получаем:<center> <tex>\sum\limits_{n=1}^{\infty} (9 n - 2)f_n^{X} = |E(k_9 H)| - k'_92 ~~~ \textbf{(4) } </tex>. </center>Полученная формула в правой части не зависит от подграфа, поэтому вычитая вариант для <tex> Y </tex> из <tex>\textbf{(4)}</tex>, приходим к <tex>\textbf{(1)}</tex>.}} = 7= Использование теоремы == * Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические (все вершины имеют степень <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" |[[Файл: Grinberg_Graph_numbersГамильтонов граф.png|300px|center|thumb|leftРис. 1]] |Граф Гринберга[[Файл: Новый гамильтонов_бонд. Проставлено количество ребер в граняхpng|500x300px|thumb|Рис.2]] |}

Придуманый Гринбергом * Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в 1968 году критерий негамильтоновисти графе. Пусть, например, все вершины связного графа<tex> G </tex>, кроме одной, имеют степени, позволил наконец построить контрпримеры к [http:сравнимые с <tex>2</tex> по модулю <tex>3</entex>.wikipedia.orgТогда левая часть формулы <tex>\textbf{(1)}</wikitex> не делится на <tex>3</Tait%27s_conjecture| гипотизе Тейта](1884г) о томtex> и, следовательно, что любой 3-регулярный трёхсвязный гамильтонова бонда в графе <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, [httphttps://enarxiv.org/abs/0908.2563v1 arXiv:0908.2563.]</ref>* Теорема Гринберга используется также для поиска планарных гипогамильтоновых графов<ref>[https://ru.wikipedia.org/wiki/Tutte_graph| %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 Википедия {{---}} Гипогамильтонов граф Татта](1946)</ref> путём построения графа, в котором все грани имеют число рёбер, негамильтоновость которого доказывалась переборомсравнимых с <tex>2</tex> по модулю <tex>3</tex>.

== См. также ==* [[Гамильтоновы графы]]* [[Разрез, лемма о потоке через разрез]]* [Файл: Tutte_graph.png|300px|thumb|right| [http://en.wikipedia.org/wiki/Tutte_graph| Граф ТаттаЛемма о рукопожатиях]] * [[Дерево, эквивалентные определения]]

== Источники информации ==*[httpУ. Татт. Теория графов. М.://en"Мир", 1988. с.wikipedia304.org/wiki/Grinberg%27s_theorem Grinberg's theorem ISBN 5-03-001001- wikipedia]7*[httphttps://logic.pdmi.ras.ru/~dvk/211/graphs_dk.pdf Д.В . Карпов - теория . Теория графов]*[http://www.math.yorku.ca/Who/Faculty/Steprans/Courses/1200/Tutorial4c.pdf теорема Гринберга301]