Цепи и циклы в графах

1.

2.

Задача: Найдите 3 разных цикла

3.

4.

5. Цепи и циклы. Обход графа (эйлеров путь). Понятие об ориентированном графе

6.

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

7. Эйлеров путь Длина этого пути = 5

Эйлеров граф- это граф,
в котором существует
эйлеров путь, то есть,
путь, проходящий ровно
один раз по каждому
ребру.
Эйлеров путь
Длиной этого пути
Длина этого пути
называется количество
=5
ребер, входящих в него.
Ориентированный граф,
то есть у каждого ребра
графа есть
направление.

8.

9.

10.

Домашнее задание:
Выучить все определения и решить задачи.
Задача 1. Представим себе схему дорог, соединяющих различные населенные пункты.
Определите, какими путями можно попасть из A в E? Какие из этих путей являются простыми?
Задача 2. От вершины А до вершины F графа можно пройти четырьмя путями; один из них — длины 1,
второй — длины 2 и два пути длиной 6. (Назовите эти пути.)
Задача 3. Назовите в графе циклы, содержащие a) 4 ребра; б) 6 ребер; в) 5 ребер; г) 10 ребер. Какие из этих
циклов являются простыми?