4.6.1 Связность. Маршруты, цепи, простые цепи

Пусть G - неориентированный граф. Маршрутом в G называется такая конечная или бесконечная последовательность ребер, что каждые два соседние ребра имеют общую вершину:

S = (E0, E1, ... , En-1, En),

Где E0 = (A0, A1); E1 = (A1, A2);... EN-1 = (AN-1, AN); EN = (AN, AN+1).

Одно и то же ребро Е может встречаться в маршруте несколько раз (рис. 4.10).

Рис. 4.10 – Пример маршрута в графе

Если в маршруте нет ребер, предшествующих E0, то вершина A0 – Начальная вершина маршрута; если нет ребер, следующих за EN, то вершина AN+1 – Конечная вершина маршрута. Любая вершина AI, принадлежащая двум соседним ребрам, называется Внутренней или промежуточной. Так как ребра и вершины в маршруте могут повторяться, внутренняя вершина может также оказаться начальной или конечной.

Если в маршруте S = S (A0, AN), соединяющем вершины A0 и AN, конечная и начальная вершины совпадают, т. е. A0 = AN, то маршрут называют Циклическим.

Если каждое ребро в маршруте встречается не более одного раза, то маршрут называется Цепью; циклический маршрут называется в этом случае Циклом. Вершины в цепи могут повторяться и несколько раз. Любой участок цепи есть цепь.

Нециклическая цепь называется Простой цепью, если в ней никакая вершина не повторяется.

Цикл с концом в A0 называется Простым циклом, если A0 не является в нем промежуточной вершиной и никакие другие вершины не повторяются.

Участок простого цикла или простой цепи есть простая цепь.

Для ориентированного графа можно вводить как Неориентированные Маршруты, цепи и простые цепи, не принимая во внимание ориентации ребер, так и Ориентированные, в которых все ребра проходят в направлении их ориентации. Ориентированную цепь Называют Путем, а ориентированный цикл – Контуром.

< Предыдущая		Следующая >