Студопедия

КАТЕГОРИИ:

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



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




Читайте также:
  1. Биогеохимические циклы в биосфере
  2. Жизненные циклы социальных движений
  3. Жизненные циклы товарной категории, разновидности товара, товара и торговой марки
  4. Инверсия доминирования, доминирование и циклы формулы любви.
  5. Какой режим работы пассивной цепи, содержащей катушки индуктивности и конденсаторы, называют резонансом? Какие два основных вида резонанса известны?
  6. Маршруты, связные компоненты и расстояния в графе
  7. Механизмы окислительного фосфорилирования, локализация пунктов фосфорилирования в дых.цепи, сопряжение и разобщение дыхания и фосфорилирования.
  8. Операционный, производственный и финансовый циклы предприятия.
  9. При параллельном соединении проводников величина, обратная общему сопротивлению цепи, равна сумме величин, обратных сопротивлениям параллельно включенных проводников.

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

В случае простого графа маршрут однозначно определяется последовательностью вершин или последовательностью ребер. Если маршрут в простом графе задан последовательностью вершин 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; просмотров: 432; Нарушение авторских прав







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