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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (Теорема Гринберга)
м (Использование теоремы)
Строка 62: Строка 62:
  
 
== Использование теоремы ==
 
== Использование теоремы ==
Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа <tex> G </tex>, кроме одной, имеют валентности, сравнимые с 2 по модулю 3. Тогда левая часть формулы '''(1)''' не делится на 3 и, следовательно, гамильтонова бонда в графе <tex> G </tex> не существует. Рисунок '''1''' иллюстрирует этот простой пример.
+
Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа <tex> G </tex>, кроме одной, имеют степени, сравнимые с 2 по модулю 3. Тогда левая часть формулы '''(1)''' не делится на 3 и, следовательно, гамильтонова бонда в графе <tex> G </tex> не существует. Рисунок '''1''' иллюстрирует этот простой пример.
 
[[Файл: Гамильтонов_бонд.png|300px|thumb|center|Рис. 1]]
 
[[Файл: Гамильтонов_бонд.png|300px|thumb|center|Рис. 1]]
  

Версия 22:04, 28 января 2016

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

Определение:
Цикломатическое число (англ. cyclomatic number) графа [math] G [/math] обозначается через [math] p_1(G) [/math] и определяется с помощью следующего соотношения:
[math] p_1(G) = |E(G)| - |V(G)| + p_0(G) ~~~ \textbf{(1)} [/math]
Это число называют также числом Бетти (англ. Betti number) размерности 1.


Теорема (1):
Цикломатическое число графа [math] G [/math] неотрицательно. Оно равно нулю тогда и только тогда, когда [math] G [/math] — лес.
Доказательство:
[math]\triangleright[/math]

Предположим сначала, что в [math] G [/math] нет ребер. Тогда [math] p_1(G) = 0 [/math]. Очевидно, что "безреберный" граф является лесом. Далее предположим, что граф [math] G [/math] есть лес и в нем содержится хотя бы одно ребро. Удаляем из [math] G [/math] ребра до тех пор, пока не получим безреберного графа [math] H [/math]. При удалении каждого ребра цикломатическое число не меняется. Следовательно, [math] p_1(G) = p_1(H) = 0 [/math].

Наконец, рассмотрим случай, когда граф [math] G [/math] не является лесом. Тогда в [math] G [/math] содержится ребро [math] A [/math], не являющееся перешейком. Удаляя его из [math] G [/math], мы уменьшим цикломатическое число на 1. Если результирующий граф не будет лесом, то процесс удаления ребра повторяем. После нескольких таких шагов (обозначим их число через [math] n [/math]) мы получим лес [math] F [/math]. Очевидно, что [math] n [/math] — положительное число, и мы имеем [math] p_1(G) = n + p_1(F) = n \gt 0 [/math].
[math]\triangleleft[/math]
Теорема (2):
Если [math] T [/math] — дерево, то [math] |V(T)| = |E(T)| + 1 [/math]
Доказательство:
[math]\triangleright[/math]
Имеем [math] p_0(T) = 1 [/math]. По теореме 1: [math] p_1(T) = 0 [/math]. Остается применить соотношение 1
[math]\triangleleft[/math]


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


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


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


Определение:
Гамильтоновым бондом (англ. hamiltonian bond) называется бонд графа [math] G [/math], торцевыми графами которого являются деревья, т.е. бонд, состоящий из [math] p_1(G) + 1 [/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]

Используя теорему 2, находим, что:

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

Ясно также, что:

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

Поэтому:

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

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

Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа [math] G [/math], кроме одной, имеют степени, сравнимые с 2 по модулю 3. Тогда левая часть формулы (1) не делится на 3 и, следовательно, гамильтонова бонда в графе [math] G [/math] не существует. Рисунок 1 иллюстрирует этот простой пример.

Рис. 1

См. также

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

  • У. Татт. Теория графов. М.: "Мир", 1988. с. 304. ISBN 5-03-001001-7