Теорема Гринберга — различия между версиями
Hazzus (обсуждение | вклад) м (→Теорема Гринберга) |
м (rollbackEdits.php mass rollback) |
||
(не показано 40 промежуточных версий 2 участников) | |||
Строка 7: | Строка 7: | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | ''' | + | '''Бонд''' (англ. ''bond'') графа {{---}} это минимальный (по включению) непустой [[Разрез,_лемма_о_потоке_через_разрез | разрез графа]] <tex>G</tex>. |
}} | }} | ||
{{Определение | {{Определение | ||
|definition= | |definition= | ||
− | ''' | + | '''Минимальный (по включению)''' (англ. ''minimal by inclusion'') разрез графа <tex>G</tex> {{---}} разрез, из которого нельзя выделить разрезы с меньшим количеством ребер. |
− | |||
− | |||
− | |||
− | |||
− | |||
}} | }} | ||
Строка 26: | Строка 21: | ||
Для удобства примем <tex>E = E(V_1, V_2)</tex>. | Для удобства примем <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>\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>\Leftarrow</tex>. Если оба графа <tex>G(V_1)</tex> и <tex>G(V_2)</tex> — связны, то добавление любого ребра из <tex>E</tex> даст нам связный подграф графа <tex>G</tex>. Значит, в этом случае разрез <tex>E</tex> минимален по включению. В силу связности <tex>G</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= | |definition= | ||
− | Подграфы <tex>V_1</tex> и <tex>V_2</tex> из предыдущей леммы называются '''торцевыми графами'''. | + | Подграфы <tex>V_1</tex> и <tex>V_2</tex> из предыдущей леммы называются '''торцевыми графами''' (англ. ''end graph''). |
}} | }} | ||
− | Также стоит отметить, что если граф <tex> G </tex> несвязен, то его '''бонд''' определим как бонд какой-либо его компоненты, а всякий | + | Также стоит отметить, что если граф <tex> G </tex> несвязен, то его '''бонд''' определим как бонд какой-либо его компоненты, а всякий [[Мост,_эквивалентные_определения | мост]] графа образует однореберный бонд. Торцевые графы моста являются торцевыми графами соответствующего бонда. |
{{Определение | {{Определение | ||
Строка 53: | Строка 50: | ||
Так как торцевые графы являются деревьями, то количество их вершин на единицу больше количества ребер: | Так как торцевые графы являются деревьями, то количество их вершин на единицу больше количества ребер: | ||
<center> <tex> \sum\limits_{n=1}^{\infty} f_n^{X} = |V(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> \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> | |
− | + | Полученная формула в правой части не зависит от подграфа, поэтому вычитая вариант для <tex> Y </tex> из <tex>\textbf{(4)}</tex>, приходим к <tex>\textbf{(1)}</tex>. | |
}} | }} | ||
== Использование теоремы == | == Использование теоремы == | ||
− | * Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические(все вершины имеют степень 3) [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 | + | |
− | + | * Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические (все вершины имеют степень <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>. | |
− | + | ||
− | * Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа <tex> G </tex>, кроме одной, имеют степени, сравнимые с 2 по модулю 3. Тогда левая часть формулы | + | {|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 /> | ||
== Источники информации == | == Источники информации == |
Текущая версия на 19:35, 4 сентября 2022
Базовые определения
Определение: |
Подграф (англ. subgraph) исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. По отношению к подграфу исходный граф называется суперграфом. |
Определение: |
Бонд (англ. bond) графа — это минимальный (по включению) непустой разрез графа . |
Определение: |
Минимальный (по включению) (англ. minimal by inclusion) разрез графа | — разрез, из которого нельзя выделить разрезы с меньшим количеством ребер.
Лемма: |
Разрез связного графа является бондом, если и только если оба графа и связны. |
Доказательство: |
Для удобства примем .. Пусть — бонд. Докажем, что для любого ребра граф связен. Действительно, пусть этот граф несвязен и имеет, скажем, компоненты связности и . Тогда , а из связности графа следует, что . Противоречие с минимальностью . Теперь докажем, что подграфы связны. Рассмотрим отдельно подграф , если он не связный, то имеет как минимум компоненты связности, назовем их .можно также представить как , то есть , и граф состоит из компонент — , что противоречит условию связности. Так же доказывается связность . . Если оба графа и — связны, то добавление любого ребра из даст нам связный подграф графа , содержащий все его вершины. Значит, в этом случае разрез минимален по включению. В силу связности этот разрез непуст, то есть, является бондом. |
Определение: |
Подграфы | и из предыдущей леммы называются торцевыми графами (англ. end graph).
Также стоит отметить, что если граф мост графа образует однореберный бонд. Торцевые графы моста являются торцевыми графами соответствующего бонда.
несвязен, то его бонд определим как бонд какой-либо его компоненты, а всякий
Определение: |
Гамильтоновым бондом (англ. hamiltonian bond) называется бонд графа | , торцевыми графами которого являются деревья.
Теорема Гринберга
Теорема (Гринберг): |
Пусть связный граф имеет гамильтонов бонд с торцевыми графами и . Пусть и — число вершин в графов и соответственно, имеющих в степень . Тогда:
|
Доказательство: |
Так как торцевые графы являются деревьями, то количество их вершин на единицу больше количества ребер: Посчитаем лемме о рукопожатиях ребер, с обоих сторон прикрепленных к , будет . Количество ребер, прикрепленных и к , и к , по определению бонда — количество ребер в бонде , то есть . Отсюда: , то есть количество всех исходящих ребер из . ПоВычитаем дважды из формулы формулу и получаем: |
Использование теоремы
- Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические (все вершины имеют степень [1] с высокой циклической реберной связностью. Циклическая рёберная связность графа — это наименьшее число рёбер, которое можно удалить так, чтобы оставшийся граф содержал более чем одну циклическую компоненту. Например он нашел граф с вершинами, гранями и циклической рёберной связностью пять, показанный на рисунке . ) полиэдральные графы
- Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа , кроме одной, имеют степени, сравнимые с по модулю . Тогда левая часть формулы не делится на и, следовательно, гамильтонова бонда в графе не существует. Рисунок иллюстрирует этот простой пример.
- Чтобы планарный граф существовал и содержал гамильтонов цикл, необходимо выполнение теоремы Гринберга.[2]
- Теорема Гринберга используется также для поиска планарных гипогамильтоновых графов[3] путём построения графа, в котором все грани имеют число рёбер, сравнимых с по модулю .
См. также
Примечания
- ↑ Википедия — Полиэдральный граф
- ↑ 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.
- ↑ Википедия — Гипогамильтонов граф
Источники информации
- У. Татт. Теория графов. М.: "Мир", 1988. с. 304. ISBN 5-03-001001-7
- Д.В. Карпов. Теория графов. c. 301