Материал: связные графы

ТЕОРИЯ ГРАФОВ

Связные графы

практическое занятие

Маршруты, цепи, циклы

Маршрутом или путем в неориентированном (ориентированном)

графе G=(V ,Е) называется чередующаяся последовательность вершин и ребер (дуг) ,

в которой любые два соседних элемента инцидентны.

Замечание 1. Для определения маршрута в

ориентированном графе (или в неориентированном

простом графе) достаточно указать только

последовательность дуг (ребер).

Маршруты, цепи, циклы

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

•Вершина, из которой начинается маршрут,

называется началом маршрута.

Вершина, в которой заканчивается маршрут,

называется концом маршрута.

• Число ребер маршрута называется длиной

маршрута.

Маршрут называется цепью, если все его ребра

различны.

•Цепь, не содержащая повторяющихся вершин,

кроме, возможно, крайних, называется

простой цепью.

Маршруты, цепи, циклы

Маршрут называется циклическим, если его начало совпадает с концом.

Циклический маршрут называется циклом, если

он является цепью.

Циклический маршрут называется простым

циклом, если он − простая цепь.

Граф, не содержащий циклов, называется

ациклическим.

ЗАДАЧА 1.

Для графа, представленного на рисунке маршрут