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>. '''(1.6.1)'''</center>Это число называют также '''числом Бетти''' (англ. ''Betti number'') размерности 1.
}}
{{Теорема
|about=1.35
|statement=
Цикломатическое число графа <tex> G </tex> неотрицательно. Оно равно нулю тогда и только тогда, когда <tex> G </tex> {{---}} лес.
|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>.
}}
{{Теорема
|about=1.372
|statement=
Если <tex> T </tex> {{---}} дерево, то <tex> |V(T)| = |E(T)| + 1 </tex>
|proof=
Имеем <tex> p_0(T) = 1 </tex>. По теореме '''1.35''': <tex> p_1(T) = 0 </tex>. Остается применить соотношение '''1'''}} {{Определение|definition='''Подграф''' (англ. ''subgraph'') исходного графа {{---}} граф, содержащий некое подмножество вершин данного графа и некое подмножество инцидентных им рёбер. По отношению к подграфу исходный граф называется суперграфом.6}} {{Определение|definition='''Порождённый подграф''' (англ.1''induced subgraph'') — подграф, порождённый множеством рёбер исходного графа. Содержит не обязательно все вершины графа, но эти вершины соединены такими же ребрами, как в графе.
}}
{{Определение
|definition=
'''Гамильтоновым бондом''' (англ. ''hamiltonian bond'') называется бонд графа <tex> G </tex>, торцевыми графами которого являются деревья, т.е. бонд, состоящий из <tex> p_1(G) + 1 </tex> ребер.
}}
