Студопедия

КАТЕГОРИИ:

АстрономияБиологияГеографияДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРиторикаСоциологияСпортСтроительствоТехнологияФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника


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




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

В случае простого графа маршрут однозначно определяется последовательностью вершин или последовательностью ребер. Если маршрут в простом графе задан последовательностью вершин v0, v1,, … , vk, то вершины v0, vk называют концами маршрута. Если v0 = vk, то маршрут называют замкнутым, в противном случае – незамкнутым.

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

Определение. Простой цикл с р вершинами обозначается Ср . Например, граф – это одновременно граф С3.

Определение. Ориентированная простая цепь называется путем, ориентированный простой цикл называют контуром.

Рассмотрим граф на рис. 11. Маршруты в этом графе будем задавать последовательностью вершин.

Пример маршрута: 1 – 2 – 3 – 5 – 7 – 4 – 3 – 5 – 6 – 2 – 3 – 4.

Пример замкнутого маршрута: 3 – 4 – 5 – 7 – 3 – 4 – 1 – 3.

Пример цепи, соединяющий вершины 6 и 8: 6 – 5 – 3 – 4 – 5 – 7 – 3 – 2 – 6 – 8.

Пример цикла: 5 – 3 – 2 – 6 – 5 – 7 – 4 – 5.

Примеры простых цепей, соединяющих вершины 1 и 6: 1 – 3 – 4 – 5 – 6; 1 – 2 – 6; 1 – 4 – 7 – 8 – 6.

Примеры простых циклов: 3 – 5 – 7 – 4 – 3; 1 – 2 – 6 – 8 – 7 – 4 – 1;

1 – 2 – 6 – 5 – 7 – 3 – 1.

 

Рис. 11

Рассмотрим ориентированный граф на рис. 12. Ориентированные маршруты в этом графе будем задавать последовательностью вершин, проходимых в направлении ориентации дуг.

Рис. 12

Пример ориентированного маршрута: 1 ® 2 ® 3 ® 5 ® 2 ® 6 ® 8 ® 5.

Пример замкнутого ориентированного маршрута: 1 ® 4 ® 5 ® 2 ® 6 ® 8 ® 5 ® 2 ® 3 ® 1.

Пример ориентированной цепи: 4 ® 5 ® 7 ® 8 ®5 ® 2.

Пример замкнутой ориентированной цепи:6 ® 8 ® 5 ® 2 ® 3 ® 1 ® 5 ® 6.

Пример пути, соединяющего вершины 3 и 9: 3 ® 1 ® 4 ® 5® 6 ® 9.

Пример контура:5 ® 7 ® 4 ® 5.



Поделиться:

Дата добавления: 2014-12-03; просмотров: 825; Мы поможем в написании вашей работы!; Нарушение авторских прав





lektsii.com - Лекции.Ком - 2014-2024 год. (0.005 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты