Изменения

== Базовые определения и теоремы ==

'''Цикломатическое числоПодграф''' графа <tex> G </tex> обозначается через <tex> p_1(G) </tex> и определяется с помощью следующего соотношения:<center> <tex> p_1(G) = |E(G)| - |V(G)| + p_0(G) </tex>англ. ''subgraph''(1.6) исходного графа {{---}} граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер.1)'''</center>Это число называют также '''числом Бетти''' размерности 1По отношению к подграфу исходный граф называется суперграфом.

{{ТеоремаОпределение|about=1.35|statement=Цикломатическое число графа <tex> G </tex> неотрицательно. Оно равно нулю тогда и только тогда, когда <tex> G </tex> {{---}} лес.|proofdefinition=Предположим сначала, что в <tex> G </tex> нет ребер. Тогда <tex> p_1(G) = 0 </tex> (в силу соотношения '''1.6.1Бонд''' и теоремы (англ. '''1.20'bond''). Очевиднографа {{---}} это минимальный (по включению) непустой [[Разрез, что "безреберный" граф является лесом.Далее предположим, что граф _лемма_о_потоке_через_разрез | разрез графа]] <tex> G </tex> есть лес и в нем содержится хотя бы одно ребро. Удаляем из <tex> G </tex> ребра до тех пор, пока не получим безреберного графа <tex> H </tex>. При удалении каждого ребра цикломатическое число не меняется (см. теоремы }} {{Определение|definition='''1.32''' и '''1.34Минимальный (по включению)'''). Следовательно, <tex> p_1(G) = p_1(H) = 0 </tex>.Наконец, рассмотрим случай, когда граф <tex> G </tex> не является лесом. Тогда в <tex> G </tex> содержится ребро <tex> A </tex>, не являющееся перешейкомангл. Удаляя его из <tex> G </tex>, мы уменьшим цикломатическое число на 1 (см. теорему '''1.34'minimal by inclusion''). Если результирующий граф не будет лесом, то процесс удаления ребра повторяем. После нескольких таких шагов (обозначим их число через разрез графа <tex> n </tex>) мы получим лес <tex> F </tex>. Очевидно, что <tex> n G</tex> {{---}} положительное числоразрез, и мы имеем <tex> p_1(G) = n + p_1(F) = n > 0 </tex>из которого нельзя выделить разрезы с меньшим количеством ребер.

{{Теорема|about=1.37Лемма

Если Разрез <tex> T E(V_1, V_2)</tex> {{---}} деревосвязного графа <tex>G</tex> является '''бондом''', то если и только если оба графа <tex> |VG(TV_1)| = |E</tex> и <tex>G(TV_2)| + 1 </tex>связны.

Имеем Для удобства примем <tex> p_0E = 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(TU_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 = 1 (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>, что противоречит условию связности. По теореме '''1Так же доказывается связность <tex>G(V_2)</tex>.35''':  <tex> p_1\Leftarrow</tex>. Если оба графа <tex>G(V_1)</tex> и <tex>G(TV_2) = 0 </tex>— связны, то добавление любого ребра из <tex>E</tex> даст нам связный подграф графа <tex>G</tex>, содержащий все его вершины. Остается применить соотношение '''1Значит, в этом случае разрез <tex>E</tex> минимален по включению.6В силу связности <tex>G</tex> этот разрез непуст, то есть, является бондом.1'''

Если граф <tex> G </tex> и порожденные подграфы <tex> G[X] </tex> и <tex> G[Y] </tex> связны, то множество <tex> J(X, Y) </tex> называется '''бондом''' графа <tex> G </tex>. Подграфы <tex> G[X] V_1</tex> и <tex> G[Y] V_2</tex> из предыдущей леммы называются '''торцевыми графами''' этого бонда. Из приведенного определения следует, что бонд <tex> J(X, Y) </tex> должен быть непустым множествомангл. Если граф <tex> G </tex> несвязен, то его ''end graph'бонд''' определим как бонд какой-либо его компоненты. Заметим, что всякий перешеек графа образует однореберный бонд. Торцевые графы перешейка являются торцевыми графами соответствующего бонда).

'''Гамильтоновым бондом''' (англ. ''hamiltonian bond'') называется бонд графа <tex> G </tex>, торцевыми графами которого являются деревья, т.е. бонд, состоящий из <tex> p_1(G) + 1 </tex> ребер.

|aboutauthor=Гринберг

Пусть связный граф <tex> G </tex> имеет гамильтонов бонд <tex> H </tex> с торцевыми графами <tex> X </tex> и <tex> Y </tex>. Пусть <tex> f_n^{X} </tex> и <tex> f_n^{Y} </tex> {{---}} числои число вершин в графов <tex> X </tex> и <tex> Y </tex> соответственно, имеющих в <tex> G </tex> валентность степень <tex> n ~ (n = 1, ~ 2, ~ 3, ~ \ldots) </tex>. Тогда:<center> <tex> \sum\limits_{n=1}^{\infty} (n - 2) (f_n^{X} - f_n^{Y}) = 0 ~~~ \bf{(1)} </tex>. '''(1)''' </center>

Используя теорему '''1.37''', находимТак как торцевые графы являются деревьями, чтото количество их вершин на единицу больше количества ребер:<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(2X)''' |</tex>. Количество ребер, прикрепленных и к <tex>X</tex>, и к <tex>Y</tex>, по определению бонда {{---}} количество ребер в бонде <tex>H</centertex>Ясно также, чтото есть <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)''' }</centertex> формулу <tex>\textbf{(2)}</tex>Поэтомуи получаем:<center> <tex> \sum\limits_{n=1}^{\infty} (n - 2) f_n^{X} = |E(H)| - 2 ~~~ \textbf{(4)} </tex>. '''(4)''' </center>Аналогичную формулу получаем Полученная формула в правой части не зависит от подграфа, поэтому вычитая вариант для графа <tex> Y </tex>. Вычитая ее из '''<tex>\textbf{(4)'''}</tex>, приходим к '''<tex>\textbf{(1)'''}</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" |[[Файл: Гамильтонов граф.png|300px|center|thumb|Рис. 1]] |[[Файл: Новый гамильтонов_бонд.png|500x300px|thumb|Рис. 2]] |} * Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа <tex> G </tex>, кроме одной, имеют валентностистепени, сравнимые с <tex>2 </tex> по модулю <tex>3</tex>. Тогда левая часть формулы '''<tex>\textbf{(1)''' }</tex> не делится на <tex>3 </tex> и, следовательно, гамильтонова бонда в графе <tex> G </tex> не существует. Рисунок '''1''' <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.png|300px|thumb|center|Рисwikipedia. 1]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 />