Составители:
Рубрика:
97
Формула (5.1) для определения числа ребер графа применима как
для графов с кратными ребрами, так и для графов с петлями. Следует
только правильно подсчитывать степени вершин. Для этого нужно
вокруг вершины провести маленькую окружность так, чтобы в нее не
попала полностью петля. После чего подсчитать количество ребер,
проходящих в этой окружности к вершине. Так, для вершины B гра
фа с (см. рис. 5.2) получаем r(B) = 5, а для вершины D того же графа
r(D) = 6. Число ребер этого графа
253624
P11,
2
11111
22
что соот
ветствует значению, полученному прямым пересчетом.
5.7. Теорема о количестве вершин нечетной степени
Приведенные рассуждения позволяют сформулировать очевидную
теорему о степенях вершин в графе: В любом графе количество вер+
шин нечетной степени четно.
Во всех примерах графов это действительно так. Если бы был най
ден граф, у которого количество вершин нечетной степени было бы не
четным, то из формулы (5.1) следовало бы, что число ребер этого гра
фа было бы нецелым!
5.8. Графы типа «дерево» – основные соотношения
В задачах сортировки используется особый вид графов – графы типа
«дерево» (см. рис. 5.2, f) . Особенностью этих графов является то, что
в них нет внутренних циклов.
Подсчитаем число ребер и вершин графа f: P = 11, B = 12. Легко по
казать, что в любом графе типа «дерево» число вершин на единицу боль
ше числа ребер. Действительно, возьмем самый простой граф типа «де
рево». Он будет содержать 2 вершины и одно ребро. Будем теперь про
извольно наращивать этот граф, добавляя ребра и вершины. Число до
бавленных ребер будет равно числу добавленных вершин. Следователь
но, в графе типа «дерево»
B – P = 1. (5.2)
5.9. Цикломатическое число графа
Рассмотрим произвольный граф, например граф с на рис. 5.2. В этом
графе P = 11, B = 6. Для того чтобы превратить этот граф в граф типа
«дерево», необходимо вычеркнуть 6 ребер. В этом случае будет спра
ведливо соотношение (5.2).
Страницы
- « первая
- ‹ предыдущая
- …
- 95
- 96
- 97
- 98
- 99
- …
- следующая ›
- последняя »
