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

1

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

3 Маршрутом называют последовательность вершин и ребер, в которой любые два соседних элемента инцидентны (т.е. соединены). Например: V0-V1-V2-V4-V6-V3-V2-V4-V5-V1-V2-V3 В случае простого графа (графа без петель и кратных ребер) маршрут однозначно определяется последовательностью вершин или последовательностью ребер

4 Если вершины v 0 = v k, то маршрут называют замкнутым. Если вершины v 0 v k, то маршрут называют незамкнутым. Длиной маршрута называют число ребер в нем с учетом повторений. Например: длина маршрута V0-V1-V2-V4-V6-V3-V2-V4-V5-V1-V2-V3 равна11

5 Если маршрут в простом графе задан последовательностью вершин v 0, v 1,...,v k, то вершины v o,v k называют концами маршрута. Например: концами маршрута V0-V1-V5-V4-V2-V3 являются вершины V0,V3

6 Цепь - это маршрут, в котором нет повторения ребер. Например: V 0 -V 2 -V 4 -V 3 -V 6 -V 7 Цепь, в которой все вершины различны, кроме, может быть, ее концов, называется простой.

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

8 Простой цикл – это замкнутая простая цепь. Например: V 0 -V 1 -V 2 -V 6 -V 3 -V 0

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

10 Леонард Эйлер ( ) Эйлеров путь (эйлерова цепь) это путь, проходящий по всем ребрам графа и притом только по одному разу. Эйлеров цикл это эйлеров путь, являющийся циклом.

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

12 Расстояние между вершинами – это длина кратчайшей цепи, соединяющей эти вершины (сама такая цепь называется геодезической) Например: расстояние между вершинами V 1 и V 5 это длина геодезической цепи V 1 -V 2 -V 4 -V 5 Диаметр – это самая длинная геодезическая цепь.

13 Мост – это такое ребро е = ( u, v ) графа, удаление которого приводит к тому, что вершины u и v перестают быть связными. Например: на рисунке это ребра (2,4), (7,10), (11,12)

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

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

16 Блок – связный граф, не имеющий точек сочленения. После удаления вершины V, граф распался на 3 блока

17 Спасибо за внимание!

18 Выполнили: Студенты группы 953 Вдовин Роман Матвеева Ольга Молодчикова Алена Источники: Учебник «Дискретная математика. Курс лекций» Палий И.А. irina-m.at.ua Материал из Википедии: статья «Эйлеров цикл»