ВУЗ:
Составители:
69
υ(G)=m-n+k ,
где m - число ребер; n - число вершин; к - число компонент связно-
сти. Для графа на рис. 2.36 цикломатическое число определится как
υ(G)=4-5+2=1.
Ясно, что это число равно наибольшему числу независимых
циклов в графе. При расчете электрических цепей этим числом поль-
зуются для определения числа независимых контуров.
Хроматическое число
γ(G). Пусть р – натуральное число. Граф
G называется р-хроматическим, если его вершины можно раскрасить
р различными цветами так, чтобы никакие две смежные вершины не
были раскрашены одинаково. Наименьшее число р, при котором
граф является р-хроматическим, называется хроматическим числом
графа и обозначается
γ(G).
Если
γ(G)=2, то граф называют бихроматическим. Пример та-
кого графа - двудольный граф. Необходимым и достаточным услови-
ем того, чтобы граф был бихроматичным, является отсутствие в нем
циклов нечетной длины (граф на рис. 2.36 - бихроматический).
Число внутренней устойчивости
ε(G). Множество S
⊆
X графа
G=<X,Г> называется внутренне устойчивым, если никакие две вер-
шины из S не смежны, т.е. для всех х
∈
S имеет место Г(х)∩S=Ǿ.
Множество внутренней устойчивости, содержащее наибольшее
число элементов, называют наибольшим внутренне устойчивым
множеством, а число его элементов называют числом внутренней ус-
тойчивости графа G. Это число играет важную роль в теории связи.
Примеры внутренне устойчивых множеств для G - на рис. 2.36
S
1
={1, 3, 5,}; S
2
={1, 3, 4}; S
3
={1, 3}; S
4
={2, 4} и др.
Наибольшие множества – это S
1
и S
2
. Следовательно, ε(G)=3.
Страницы
- « первая
- ‹ предыдущая
- …
- 71
- 72
- 73
- 74
- 75
- …
- следующая ›
- последняя »
