Теорема Гринберга — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Использование теоремы)
м (rollbackEdits.php mass rollback)
 
(не показано 55 промежуточных версий 3 участников)
Строка 1: Строка 1:
== Базовые определения и теоремы ==
+
== Базовые определения ==
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Цикломатическое число''' (англ. ''cyclomatic number'') графа <tex> G </tex> обозначается через <tex> p_1(G) </tex> и определяется с помощью следующего ''соотношения'':
+
'''Подграф''' (англ. ''subgraph'') исходного графа {{---}} граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. По отношению к подграфу исходный граф называется суперграфом.
<center> <tex> p_1(G) = |E(G)| - |V(G)| + p_0(G) ~~~ \textbf{(1)} </tex> </center>
 
Это число называют также '''числом Бетти''' (англ. ''Betti number'') размерности 1.
 
 
}}
 
}}
  
{{Теорема
+
{{Определение
|about=1
+
|definition=
|statement=
+
'''Бонд''' (англ. ''bond'') графа {{---}} это минимальный (по включению) непустой [[Разрез,_лемма_о_потоке_через_разрез | разрез графа]] <tex>G</tex>.  
Цикломатическое число графа <tex> G </tex> неотрицательно. Оно равно нулю тогда и только тогда, когда <tex> G </tex> {{---}} лес.
+
}}
|proof=
+
 
Предположим сначала, что в <tex> G </tex> нет ребер. Тогда <tex> p_1(G) = 0 </tex>. Очевидно, что "безреберный" граф является лесом.
+
{{Определение
Далее предположим, что граф <tex> G </tex> есть лес и в нем содержится хотя бы одно ребро. Удаляем из <tex> G </tex> ребра до тех пор, пока не получим безреберного графа <tex> H </tex>. При удалении каждого ребра цикломатическое число не меняется. Следовательно, <tex> p_1(G) = p_1(H) = 0 </tex>.
+
|definition=
Наконец, рассмотрим случай, когда граф <tex> G </tex> не является лесом. Тогда в <tex> G </tex> содержится ребро <tex> A </tex>, не являющееся перешейком. Удаляя его из <tex> G </tex>, мы уменьшим цикломатическое число на 1. Если результирующий граф не будет лесом, то процесс удаления ребра повторяем. После нескольких таких шагов (обозначим их число через <tex> n </tex>) мы получим лес <tex> F </tex>. Очевидно, что <tex> n </tex> {{---}} положительное число, и мы имеем <tex> p_1(G) = n + p_1(F) = n > 0 </tex>.
+
'''Минимальный (по включению)''' (англ. ''minimal by inclusion'') разрез графа <tex>G</tex> {{---}} разрез, из которого нельзя выделить разрезы с меньшим количеством ребер.  
 
}}
 
}}
  
{{Теорема
+
{{Лемма
|about=2
 
 
|statement=
 
|statement=
Если <tex> T </tex> {{---}} дерево, то <tex> |V(T)| = |E(T)| + 1 </tex>
+
Разрез <tex>E(V_1, V_2)</tex> связного графа <tex>G</tex> является '''бондом''', если и только если оба графа <tex>G(V_1)</tex> и <tex>G(V_2)</tex> связны.
 
|proof=
 
|proof=
Имеем <tex> p_0(T) = 1 </tex>. По теореме '''1''': <tex> p_1(T) = 0 </tex>. Остается применить соотношение '''1'''
+
Для удобства примем <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>.
|definition=
 
'''Подграф''' (англ. ''subgraph'') исходного графа {{---}} граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. По отношению к подграфу исходный граф называется суперграфом.
 
}}
 
  
{{Определение
+
<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=
 
'''Порождённый подграф''' (англ. ''induced subgraph'') — подграф, порождённый множеством рёбер исходного графа. Содержит не обязательно все вершины графа, но эти вершины соединены такими же ребрами, как в графе.
 
 
}}
 
}}
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
Если граф <tex> G </tex> и порожденные подграфы <tex> G[X] </tex> и <tex> G[Y] </tex> связны, то множество <tex> J(X, Y) </tex> называется '''бондом''' графа <tex> G </tex>. Подграфы <tex> G[X] </tex> и <tex> G[Y] </tex> называются '''торцевыми графами''' этого бонда. Из приведенного определения следует, что бонд <tex> J(X, Y) </tex> должен быть непустым множеством. Если граф <tex> G </tex> несвязен, то его '''бонд''' определим как бонд какой-либо его компоненты. Заметим, что всякий перешеек графа образует однореберный бонд. Торцевые графы перешейка являются торцевыми графами соответствующего бонда.
+
Подграфы <tex>V_1</tex> и <tex>V_2</tex> из предыдущей леммы называются '''торцевыми графами''' (англ. ''end graph'').
 
}}
 
}}
 +
Также стоит отметить, что если граф <tex> G </tex> несвязен, то его '''бонд''' определим как бонд какой-либо его компоненты, а всякий [[Мост,_эквивалентные_определения | мост]] графа образует однореберный бонд. Торцевые графы моста являются торцевыми графами соответствующего бонда.
  
 
{{Определение
 
{{Определение
 
|definition=
 
|definition=
'''Гамильтоновым бондом''' (англ. ''hamiltonian bond'') называется бонд графа <tex> G </tex>, торцевыми графами которого являются деревья, т.е. бонд, состоящий из <tex> p_1(G) + 1 </tex> ребер.
+
'''Гамильтоновым бондом''' (англ. ''hamiltonian bond'') называется бонд графа <tex> G </tex>, торцевыми графами которого являются деревья.
 
}}
 
}}
  
 
== Теорема Гринберга ==
 
== Теорема Гринберга ==
 
{{Теорема
 
{{Теорема
|about=Гринберг
+
|author=Гринберг
 
|statement=
 
|statement=
 
Пусть связный граф <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>. Тогда:
 
Пусть связный граф <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>. </center>
 
<center> <tex> \sum\limits_{n=1}^{\infty} (n - 2) (f_n^{X} - f_n^{Y}) = 0 ~~~ \bf{(1)} </tex>. </center>
 
|proof=
 
|proof=
Используя теорему '''2''', находим, что:
+
Так как торцевые графы являются деревьями, то количество их вершин на единицу больше количества ребер:
<center> <tex> \sum\limits_{n=1}^{\infty} f_n^{X} = |E(X)| + 1 ~~~ \textbf{(2)} </tex>. </center>
+
<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>Y</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>
 
<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} (n - 2) f_n^{X} = |E(H)| - 2 ~~~ \textbf{(4)} </tex>. </center>
+
<center> <tex>\sum\limits_{n=1}^{\infty} (n - 2) f_n^{X} = |E(H)| - 2 ~~~ \textbf{(4)} </tex>. </center>
Аналогичную формулу получаем для графа <tex> Y </tex>. Вычитая ее из '''(4)''', приходим к '''(1)'''.
+
Полученная формула в правой части не зависит от подграфа, поэтому вычитая вариант для <tex> Y </tex> из <tex>\textbf{(4)}</tex>, приходим к <tex>\textbf{(1)}</tex>.
 
}}
 
}}
  
 
== Использование теоремы ==
 
== Использование теоремы ==
Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа <tex> G </tex>, кроме одной, имеют степени, сравнимые с 2 по модулю 3. Тогда левая часть формулы '''(1)''' не делится на 3 и, следовательно, гамильтонова бонда в графе <tex> G </tex> не существует. Рисунок '''1''' иллюстрирует этот простой пример.
+
 
[[Файл: Гамильтонов_бонд.png|300px|thumb|center|Рис. 1]]
+
* Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические (все вершины имеют степень <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> не существует. Рисунок <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 />
  
 
== Источники информации ==
 
== Источники информации ==
 
* У. Татт. Теория графов. М.: "Мир", 1988. с. 304. ISBN 5-03-001001-7
 
* У. Татт. Теория графов. М.: "Мир", 1988. с. 304. ISBN 5-03-001001-7
 +
* [https://logic.pdmi.ras.ru/~dvk/graphs_dk.pdf Д.В. Карпов. Теория графов. c. 301]
  
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Алгоритмы и структуры данных]]
 
[[Категория:Обходы графов]]
 
[[Категория:Обходы графов]]
 
[[Категория:Гамильтоновы графы]]
 
[[Категория:Гамильтоновы графы]]

Текущая версия на 19:35, 4 сентября 2022

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

Определение:
Подграф (англ. subgraph) исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. По отношению к подграфу исходный граф называется суперграфом.


Определение:
Бонд (англ. bond) графа — это минимальный (по включению) непустой разрез графа [math]G[/math].


Определение:
Минимальный (по включению) (англ. minimal by inclusion) разрез графа [math]G[/math] — разрез, из которого нельзя выделить разрезы с меньшим количеством ребер.


Лемма:
Разрез [math]E(V_1, V_2)[/math] связного графа [math]G[/math] является бондом, если и только если оба графа [math]G(V_1)[/math] и [math]G(V_2)[/math] связны.
Доказательство:
[math]\triangleright[/math]

Для удобства примем [math]E = E(V_1, V_2)[/math].

[math]\Rightarrow[/math]. Пусть [math]E[/math] — бонд. Докажем, что для любого ребра [math]e \in E[/math] граф [math]G - E + e[/math] связен. Действительно, пусть этот граф несвязен и имеет, скажем, компоненты связности [math]U_1[/math] и [math]U_2[/math]. Тогда [math]E \supsetneq E(U_1, U_2)[/math], а из связности графа [math]G[/math] следует, что [math]E(U_1, U_2) \neq \varnothing[/math]. Противоречие с минимальностью [math]E[/math].

Теперь докажем, что подграфы [math]G(V_1) \text{ и } G(V_2)[/math] связны. Рассмотрим отдельно подграф [math]G(V_1)[/math], если он не связный, то имеет как минимум [math]2[/math] компоненты связности, назовем их [math]O_1 \text{ и } O_2[/math].

[math]e \in E [/math] можно также представить как [math]e = (u, v) \text{ при этом } u \in G(V_1), v \in G(V_2)[/math], то есть [math]u \in O_1 \mid u \in O_2[/math], и граф [math] G - E + e [/math] состоит из [math]2[/math] компонент — [math](O_1 \cup G(V_2), O_2) \mid (O_2 \cup G(V_2), O_1)[/math], что противоречит условию связности. Так же доказывается связность [math]G(V_2)[/math].

[math]\Leftarrow[/math]. Если оба графа [math]G(V_1)[/math] и [math]G(V_2)[/math] — связны, то добавление любого ребра из [math]E[/math] даст нам связный подграф графа [math]G[/math], содержащий все его вершины. Значит, в этом случае разрез [math]E[/math] минимален по включению. В силу связности [math]G[/math] этот разрез непуст, то есть, является бондом.
[math]\triangleleft[/math]


Определение:
Подграфы [math]V_1[/math] и [math]V_2[/math] из предыдущей леммы называются торцевыми графами (англ. end graph).

Также стоит отметить, что если граф [math] G [/math] несвязен, то его бонд определим как бонд какой-либо его компоненты, а всякий мост графа образует однореберный бонд. Торцевые графы моста являются торцевыми графами соответствующего бонда.


Определение:
Гамильтоновым бондом (англ. hamiltonian bond) называется бонд графа [math] G [/math], торцевыми графами которого являются деревья.


Теорема Гринберга

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

Так как торцевые графы являются деревьями, то количество их вершин на единицу больше количества ребер:

[math] \sum\limits_{n=1}^{\infty} f_n^{X} = |V(X)| = |E(X)| + 1 ~~~ \textbf{(2)} [/math].

Посчитаем [math] \sum\limits_{n=1}^{\infty} n f_n^{X} [/math], то есть количество всех исходящих ребер из [math]X[/math]. По лемме о рукопожатиях ребер, с обоих сторон прикрепленных к [math]X[/math], будет [math]2|E(X)|[/math]. Количество ребер, прикрепленных и к [math]X[/math], и к [math]Y[/math], по определению бонда — количество ребер в бонде [math]H[/math], то есть [math]|E(H)|[/math]. Отсюда:

[math] \sum\limits_{n=1}^{\infty} n f_n^{X} = |E(H)| + 2|E(X)| ~~~ \textbf{(3)} [/math].

Вычитаем дважды из формулы [math]\textbf{(3)}[/math] формулу [math]\textbf{(2)}[/math] и получаем:

[math]\sum\limits_{n=1}^{\infty} (n - 2) f_n^{X} = |E(H)| - 2 ~~~ \textbf{(4)} [/math].
Полученная формула в правой части не зависит от подграфа, поэтому вычитая вариант для [math] Y [/math] из [math]\textbf{(4)}[/math], приходим к [math]\textbf{(1)}[/math].
[math]\triangleleft[/math]

Использование теоремы

  • Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические (все вершины имеют степень [math]3[/math]) полиэдральные графы[1] с высокой циклической реберной связностью. Циклическая рёберная связность графа — это наименьшее число рёбер, которое можно удалить так, чтобы оставшийся граф содержал более чем одну циклическую компоненту. Например он нашел граф с [math]46[/math] вершинами, [math]25[/math] гранями и циклической рёберной связностью пять, показанный на рисунке [math]1[/math].
Рис. 1
Рис. 2
  • Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа [math] G [/math], кроме одной, имеют степени, сравнимые с [math]2[/math] по модулю [math]3[/math]. Тогда левая часть формулы [math]\textbf{(1)}[/math] не делится на [math]3[/math] и, следовательно, гамильтонова бонда в графе [math] G [/math] не существует. Рисунок [math]2[/math] иллюстрирует этот простой пример.
  • Чтобы планарный граф существовал и содержал гамильтонов цикл, необходимо выполнение теоремы Гринберга.[2]
  • Теорема Гринберга используется также для поиска планарных гипогамильтоновых графов[3] путём построения графа, в котором все грани имеют число рёбер, сравнимых с [math]2[/math] по модулю [math]3[/math].

См. также

Примечания

  1. Википедия — Полиэдральный граф
  2. 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, arXiv:0908.2563.
  3. Википедия — Гипогамильтонов граф

Источники информации