39
правок
Изменения
м
Нет описания правки
'''Цикломатическое число''' графа <tex> G </tex> обозначается через <tex> p_1(G) </tex> и определяется с помощью следующего соотношения:
<center> <tex> p_1(G) = |E(G)| - |V(G)| + p_0(G) </tex>. '''(1.6.1)'''</center>
Это число называют также '''числом Бетти ''' размерности 1.
}}
|proof=
Предположим сначала, что в <tex> G </tex> нет ребер. Тогда <tex> p_1(G) = 0 </tex> (в силу соотношения '''1.6.1''' и теоремы '''1.20'''). Очевидно, что "безреберный" граф является лесом.
Далее предположим, что граф <tex> G </tex> есть лес и в нем содержится хотя бы одно ребро. Удаляем из <tex> G </tex> рбра ребра до тех пор, пока не получим безреберного графа <tex> H </tex>. При удалении каждого ребра цикломатическое число не меняется (см. теоремы '''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'''). Если результирующий граф не будет лесом, то процесс удаления ребра повторяем. После нескольких таких шагов (обозначим их число через <tex> n </tex>) мы получим лес <tex> F </tex>. Очевидно, что <tex> n </tex> {{---}} положительное число, и мы имеем <tex> p_1(G) = n + p_1(F) = n > 0 </tex>.
}}
Аналогичную формулу получаем для графа <tex> Y </tex>. Вычитая ее из '''(4)''', приходим к '''(1)'''.
}}
== Использование теоремы ==
Теорему Гринберга можно иногда использовать для доказательства отсутствия гамильтонова бонда в графе. Пусть, например, все вершины связного графа <tex> G </tex>, кроме одной, имеют валентности, сравнимые с 2 по модулю 3. Тогда левая часть формулы '''(1)''' не делится на 3 и, следовательно, гамильтонова бонда в графе <tex> G </tex> не существует. Рисунок '''1''' иллюстрирует этот простой пример.
[[Файл: Гамильтонов_бонд.png|300px|thumb|center|Рис. 1]]
== См. также ==
