A b c d

A

B

C

D

Говорят, что две вершины соединены путем, если из первой вершины можно пройти по ребрам во вторую вершину. Путей между вершинами может быть несколько, поэтому они обозначаются перечислением вершин, которые встречаются на данном пути. Например, вершины A и C графа:

соединены путями ABC, AC, ADC, AEDC, ABDC, AEDBC.

Граф называется связным, если любые две его вершины соединены некоторым путем. Если в графе можно найти замкнутый путь, то граф называется циклическим, а сам замкнутый путь – циклом.

Связный граф, в котором нет циклов, называется деревом:

Одной из основных отличительных черт дерева является то, что в нем любые две вершины соединены единственным путем.

Дерево называется ориентированным, если на каждом его ребре указано направление. Следовательно, о каждой его вершине можно сказать, какие ребра в него входят, а какие из нее выходят. Точно так же о каждом ребре можно сказать, из какой вершины оно выходит и в какую входит:

Из вершины A выходят три ребра – AB, AC и AЕ, в вершину D входит одно ребро – ED. Этот же граф можно описать следующей матрицей смежности:

Дата добавления: 2014-01-06