Теорема Гринберга — различия между версиями
Hazzus (обсуждение | вклад) (→Использование теоремы) |
Hazzus (обсуждение | вклад) м (→Использование теоремы) |
||
Строка 59: | Строка 59: | ||
== Использование теоремы == | == Использование теоремы == | ||
[[Файл: Гамильтонов граф.png|190px|left|thumb|Рис. 1]] | [[Файл: Гамильтонов граф.png|190px|left|thumb|Рис. 1]] | ||
− | * Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические (все вершины имеют степень <tex>3</tex>) [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 полиэдральные графы] с высокой циклической связностью. Например он нашел граф с 46 вершинами, 25 гранями и циклической рёберной связностью пять, показанный на рисунке <tex>1</tex>. | + | * Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические (все вершины имеют степень <tex>3</tex>) [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>46</tex> вершинами, <tex>25</tex> гранями и циклической рёберной связностью пять, показанный на рисунке <tex>1</tex>. |
[[Файл: Новый гамильтонов_бонд.png|300px|thumb|Рис. 2]] | [[Файл: Новый гамильтонов_бонд.png|300px|thumb|Рис. 2]] | ||
* Теорема Гринберга {{---}} необходимое условие для планарного графа, чтобы граф содержал гамильтонов цикл, основанное на длинах циклов граней. | * Теорема Гринберга {{---}} необходимое условие для планарного графа, чтобы граф содержал гамильтонов цикл, основанное на длинах циклов граней. |
Версия 10:29, 3 октября 2018
Содержание
Базовые определения
Определение: |
Подграф (англ. subgraph) исходного графа — граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. По отношению к подграфу исходный граф называется суперграфом. |
Определение: |
Бонд (англ. bond) графа — это минимальный (по включению) непустой разрез графа . |
Определение: |
Минимальный (по включению) (англ. minimal by inclusion) разрез графа | — разрез, из которого нельзя выделить разрезы с меньшим количеством ребер.
Лемма: |
Разрез связного графа является бондом, если и только если оба графа и связны. |
Доказательство: |
Для удобства примем .. Пусть — бонд. Докажем, что для любого ребра граф связен. Действительно, пусть этот граф несвязен и имеет, скажем, компоненты связности и . Тогда , а из связности графа следует, что . Противоречие с минимальностью . Теперь докажем, что подграфы связны. Рассмотрим отдельно подграф , если он не связный, то имеет компоненты .можно также представить как , то есть , и граф состоит из компонент , что противоречит условию связности. Так же доказывается связность . . Если оба графа и — связны, то добавление любого ребра из даст нам связный подграф графа , содержащий все его вершины. Значит, в этом случае разрез минимален по включению. В силу связности этот разрез непуст, то есть, является бондом. |
Определение: |
Подграфы | и из предыдущей леммы называются торцевыми графами.
Также стоит отметить, что если граф мост графа образует однореберный бонд. Торцевые графы моста являются торцевыми графами соответствующего бонда.
несвязен, то его бонд определим как бонд какой-либо его компоненты, а всякий
Определение: |
Гамильтоновым бондом (англ. hamiltonian bond) называется бонд графа | , торцевыми графами которого являются деревья.
Теорема Гринберга
Теорема (Гринберг): |
Пусть связный граф имеет гамильтонов бонд с торцевыми графами и . Пусть и — число вершин в графов и соответственно, имеющих в степень . Тогда:
|
Доказательство: |
Так как торцевые графы являются деревьями, то количество их вершин на единицу больше количества ребер: Посчитаем лемме о рукопожатиях ребер, с обоих сторон прикрепленных к , будет . Количество ребер, прикрепленных и к , и к , по определению бонда — количество ребер в бонде , то есть . Отсюда: , то есть количество всех исходящих ребер из . ПоВычитаем дважды из формулы формулу и получаем: |
Использование теоремы
- Сам Гринберг использовал свою теорему для того, чтобы искать негамильтоновы кубические (все вершины имеют степень полиэдральные графы с высокой циклической связностью. Например он нашел граф с вершинами, гранями и циклической рёберной связностью пять, показанный на рисунке . )
- Теорема Гринберга — необходимое условие для планарного графа, чтобы граф содержал гамильтонов цикл, основанное на длинах циклов граней.
- Теорема Гринберга используется также для поиска планарных гипогамильтоновых графов путём построения графа, в котором все грани имеют число рёбер, сравнимых с по модулю .
- Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа , кроме одной, имеют степени, сравнимые с по модулю . Тогда левая часть формулы не делится на и, следовательно, гамильтонова бонда в графе не существует. Рисунок иллюстрирует этот простой пример.
См. также
- Гамильтоновы графы
- Разрез, лемма о потоке через разрез
- Лемма о рукопожатиях
- Дерево, эквивалентные определения
Источники информации
- У. Татт. Теория графов. М.: "Мир", 1988. с. 304. ISBN 5-03-001001-7
- Д.В. Карпов. Теория графов. c. 301