39
правок
Изменения
м
== Базовые определения и теоремы ==
{{Определение
|definition=
'''Цикломатическое число''' (англ. ''cyclomatic number'') графа <tex> G </tex> обозначается через <tex> p_1(G) </tex> и определяется с помощью следующего ''соотношения'':
<center> <tex> p_1(G) = |E(G)| - |V(G)| + p_0(G) ~~~ \textbf{(1)} </tex> </center>
Это число называют также '''числом Бетти''' (англ. ''Betti number'') размерности 1.
}}
{{Теорема
|about=1
|statement=
Цикломатическое число графа <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>.
Наконец, рассмотрим случай, когда граф <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>.
}}
{{Теорема
|about=2
|statement=
Если <tex> T </tex> {{---}} дерево, то <tex> |V(T)| = |E(T)| + 1 </tex>
|proof=
Имеем <tex> p_0(T) = 1 </tex>. По теореме '''1''': <tex> p_1(T) = 0 </tex>. Остается применить соотношение '''1'''
}}
Пусть множество вершин графа <tex> G </tex> разбито на взаимно дополнительные подмножества <tex> X </tex> и <tex> Y </tex>. Через <tex> J(X, Y) </tex> обозначим множество всех ребер графа <tex> G </tex>, у каждого из которых один конец лежит в <tex> X </tex>, а другой {{---}} в <tex> Y </tex>. <br>
→Базовые определения и теоремы
{{Определение
|definition=
}}
Пусть множество вершин графа <tex> G </tex> разбито на взаимно дополнительные подмножества <tex> X </tex> и <tex> Y </tex>. Через <tex> J(X, Y) </tex> обозначим множество всех ребер графа <tex> G </tex>, у каждого из которых один конец лежит в <tex> X </tex>, а другой {{---}} в <tex> Y </tex>.
{{Определение
|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> несвязен, то его '''бонд''' определим как бонд какой-либо его компоненты. Заметим, что всякий перешеек графа образует однореберный бонд. Торцевые графы перешейка являются торцевыми графами соответствующего бонда.
}}
