Граф и его элементы

курсовая работа

1.5 Маршруты и пути

Одно из наиболее простых свойств, которым может обладать граф это свойство быть связным. В данном разделе рассматриваются основные структурные свойства связных и несвязных графов.

Маршрут в графе - чередующаяся последовательность вершин и ребер.

Эта последовательность начинается и кончается вершиной, и каждое ребро последовательности инцидентно двум вершинам, одна из которых непосредственно предшествует ему, а другая непосредственно следует за ним (рисунок 8).

Рисунок 8 Граф для иллюстрации маршрутов

Указанный маршрут соединяет вершины Do и Dn, и его можно обозначить Do,D1,D2,...,Dn (наличие ребер подразумевается). Эта последовательность иногда называется (Do-Dn) - маршрутом. Маршрут замкнут, если D = Dn, и открыт в противном случае.

Цепь - маршрут с различными ребрами.

Простая цепь-маршрут с различными вершинами (а значит, и ребрами).

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

В помеченном графе J на рисунке 8 D1 D2 D3 D4 - маршрут, который не является цепью, а D1 D2 D4 D3 D2 - цепь, где D1 D2 D4 D3 - простая цепь и D2 D4 D3 D2 - простой цикл.

Обозначим через Jn граф состоящий из одного простого цикла с n вершинами, и через Pn простую цепь с n вершинами. Jn часто называют треугольником.

Делись добром ;)