Понятие эйлерова графа. Ориентированные.

Решение:

Эйлеров граф — это неориентированный граф, в котором существует эйлеров цикл (или эйлеров путь).

Эйлеров цикл — это цикл, который проходит по каждому ребру графа ровно один раз.

Эйлеров путь — это путь, который проходит по каждому ребру графа ровно один раз, но начало и конец пути могут не совпадать.

Признак существования эйлерова цикла в неориентированном графе:

1. Граф должен быть связным (если он не состоит из одной вершины).
2. Все вершины графа должны иметь чётную степень.

Признак существования эйлерова пути в неориентированном графе:

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

Ориентированный граф — это граф, в котором рёбра имеют направление.

Эйлеров цикл в ориентированном графе:

1. Граф должен быть сильно связным (из любой вершины можно достичь любую другую).
2. Для каждой вершины полустепень исхода должна быть равна полустепени захода (т.е. количество исходящих рёбер равно количеству входящих рёбер).

Эйлеров путь в ориентированном графе:

1. Граф должен быть связным (т.е. ориентированный граф, содержащийся в нём, является связным).
2. Либо для всех вершин полустепень исхода равна полустепени захода, либо есть ровно одна вершина, у которой полустепень исхода на единицу больше полустепени захода (начальная вершина пути), и ровно одна вершина, у которой полустепень захода на единицу больше полустепени исхода (конечная вершина пути).

Проверка теории

Заполнение пропусков:

Число [вставьте число] вершин графа всегда [вставьте слово].

Ответ: [вставьте число]; [вставьте слово].