5 группа/

Материал из Saratov FIO Wiki
Перейти к: навигация, поиск


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

Маршрут

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

!В случае простого графа (графа без петель и кратных ребер) маршрут однозначно определяется последовательностью вершин или последовательностью ребер.

Pktim marshrut.jpg


Например: V0-V1-V2-V4-V6-V3-V2-V4-V5-V1-V2-V3

Если вершины V0 = Vk, то маршрут называют замкнутым, в противном случае (т.е. V0 ≠ Vk) - незамкнутым.


Длиной маршрута называют число ребер в нем с учетом повторений.

Например: длина маршрута V0-V1-V2-V4-V6-V3-V2-V4-V5-V1-V2-V3 равна11.


Если маршрут в простом графе задан последовательностью вершин V0,V1,...,Vk, то вершины V0,Vk - концы маршрута

Например: концами маршрута V0-V1-V2-V4-V6-V3-V2-V4-V5-V1-V2-V3 являются вершины V0 ,V3.

Цепь

Цепь - это маршрут, в котором нет повторения ребер.

Pktim marshrut.jpg

Например: V0-V2-V4-V3-V6-V7

Цепь, в которой все вершины различны, кроме, может быть, ее концов, называется простой.

Например: V0-V1-V2-V3-V4-V6-V7

Путь – это ориентированная простая цепь

Pktim zep.jpg

Pktim primer1.jpg

Цикл

Простой цикл – это замкнутая простая цепь.

Pktim marshrut.jpg

Например: V0-V1-V2-V6-V3-V0

Контур – это простой ориентированный цикл.

Pktim zep.jpg

Pktim primer2.jpg

Расстояние между вершинами, диаметр, мост

Расстояние между вершинами – это длина кратчайшей цепи, соединяющей эти вершины (сама такая цепь называется геодезической) рисунок

Pktim marshrut.jpg

Например: расстояние между вершинами V1 и V5 это длина геодезической цепи V1-V2-V4-V5

Диаметр – это самая длинная геодезическая цепь.

Мост – это такое ребро е = ( u, v ) графа, удаление которого приводит к тому, что вершины u и v перестают быть связными.

Pktim most.jpg

Например: на рисунке это ребра (2,4), (7,10), (11,12)

Точка сочленения, блок

Точка сочленения – это вершина графа v, удаление которой из графа увеличивает число компонентов связности.

Pktim tochka.jpg

На рисунке это вершина V

Блок – связный граф, не имеющий точек сочленения.

Pktim blok.jpg

После удаления точки сочленения (вершины V) граф распадается на три блока