8. Понятия: маршрут, путь, цепь, простая цепь, цикл, контур, достижимость, радиус, эксцентриситет, диаметр, матрица расстояний. Теорема о числе различных цепей (путей) длины n в графах и орграфах: следствия.

Понятия.

Маршрут в графе — это чередующаяся последовательность вершин и рёбер v_0, e_1, v_1, e_2, v_2, … , e_k, v_k, в которой любые два соседних элемента инцидентны.

Цепь в графе — маршрут, все рёбра которого различны.

Если все вершины (а тем самым и рёбра) различны, то такая цепь называется простой (элементарной).

Цикл — замкнутая цепь.

Контур — замкнутый путь в орграфе.

Простой цикл — цикл, не проходящий дважды через одну вершину.

Эксцентриситет вершины — максимальное расстояние из всех минимальных расстояний от других вершин до данной вершины.

Радиус графа — минимальный из эксцентриситетов вершин связного графа; вершина, на которой достигается этот минимум, называется центральной вершиной.

Диаметр графа — это максимум расстояния между вершинами для всех пар вершин. Расстояние между вершинами — наименьшее число рёбер пути, соединяющего две вершины.

Матрица D(G) расстояний между вершинами графа - матрица, элементами dij которой будут расстояния между вершинами vi и vj. Матрица симметрична относительно главной диагонали.

Теорема.

Теорема. Пусть G = ( X, E ) – орграф, A ( G ) – матрица смежности его вершин. Тогда элемент cij матрицы C = An( G ) равен числу различных путей длиной n, выходящих из вершины xi и заходящих в вершину xj.

Следствие. В орграфе G путь длиной n существует тогда и только тогда, когда An( G ) ≠ 0.

Следствие. Если An( G ) = 0 для некоторого n > 0, то в орграфе G нет циклов.