Элементы теории графов и их технические приложения - 21 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

21
существенно различными, если они не изоморфны. На рис. 27 показаны все
возможные различные деревья с шестью вершинами.
Рис. 27
С увеличением числа вершин количество различных деревьев резко
возрастает (например, при n=20 их насчитывается около миллиона). Среди рзлич-
ных деревьев выделяются два частных случая: последовательное дерево,
представляющее собой простую цепь, и звездное дерево, в котором одна из вершин
(центр) смежна со всеми остальными вершинами.
Рассматриваются также деревья с ориентированными ребрами
(дугами).
Ориентированное дерево называется прадеревом с корнем v
0
, если существует путь
между вершиной v
0
и любой другой его вершиной (рис. 28).
Рис. 28
Рис. 29. Исходный граф (а) и два возможных дерева (б и в).
Для графа G с n вершинами и m ребрами следующие утверждения
эквивалентны:
1)
G – дерево;
2)
G – связный граф и m=n-1;
3)
G – ациклический граф и m=n-1;
4)
Любые две несовпадающие вершины графа G соединяет единственная
простая цепь;
5) G – ациклический граф, обладающий тем свойством, что если какую-либо
пару его несмежных вершин соединить ребром, то полученный граф будет
содержать ровно один цикл.
Из этих утверждений следует, что в любом дереве порядка n≥2 имеется не
менее двух концевых вершин.

Страницы