Номер 1, страница 91, часть 1 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

1 Что такое эйлеров путь и какие графы называют эйлеровыми?

Что такое эйлеров путь

Эйлеров путь (или эйлерова цепь) — это путь в графе, который проходит через каждое ребро ровно один раз. При этом вершины могут посещаться многократно. Если начальная и конечная вершины пути совпадают, его называют эйлеровым циклом.

Это понятие было введено Леонардом Эйлером в 1736 году при решении знаменитой задачи о семи кёнигсбергских мостах, которая считается одной из первых задач теории графов.

Критерий существования эйлерова пути в связном графе напрямую связан со степенями его вершин.

• Для неориентированного графа: связный граф имеет эйлеров путь тогда и только тогда, когда в нём имеется не более двух вершин нечётной степени (степень вершины — это количество инцидентных ей рёбер).
  • Если в графе нет вершин нечётной степени (т.е. все вершины имеют чётную степень), то любой эйлеров путь также является эйлеровым циклом. Такой путь можно начать из любой вершины и закончить в ней же.
  • Если в графе ровно две вершины нечётной степени, то эйлеров путь существует, но он должен начинаться в одной из этих вершин и заканчиваться в другой.
  Если в графе больше двух вершин нечетной степени, эйлеров путь невозможен.
• Для ориентированного графа (орграфа): сильно связный орграф имеет эйлеров путь тогда и только тогда, когда для каждой его вершины $v$ выполняется условие:
  • полустепень захода $deg^-(v)$ (число входящих рёбер) и полустепень исхода $deg^+(v)$ (число выходящих рёбер) почти равны;
  • существует не более одной вершины, для которой $deg^+(v) - deg^-(v) = 1$ (она будет начальной);
  • существует не более одной вершины, для которой $deg^-(v) - deg^+(v) = 1$ (она будет конечной).
  У всех остальных вершин должно выполняться равенство $deg^+(v) = deg^-(v)$.

Ответ: Эйлеров путь — это путь в графе, который проходит по каждому ребру ровно один раз. Он существует в связном неориентированном графе, если число вершин нечетной степени в нем равно нулю или двум. Он существует в сильно связном ориентированном графе, если у всех вершин, кроме, возможно, двух, полустепень захода равна полустепени исхода, а для оставшихся двух (стартовой и конечной) эта разница равна 1.

Какие графы называют эйлеровыми

Эйлеровым графом называют граф, в котором существует эйлеров цикл.

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

Критерий, определяющий, является ли граф эйлеровым (т.е. существует ли в нем эйлеров цикл), следующий:

• Для неориентированного графа: связный граф является эйлеровым тогда и только тогда, когда степени всех его вершин чётны.
• Для ориентированного графа (орграфа): сильно связный орграф является эйлеровым тогда и только тогда, когда для каждой его вершины $v$ полустепень захода равна полустепени исхода: $deg^-(v) = deg^+(v)$.

Граф, который содержит эйлеров путь, но не содержит эйлерова цикла, иногда называют полуэйлеровым графом.

Ответ: Эйлеровыми называют графы, которые содержат эйлеров цикл (замкнутый путь, проходящий по каждому ребру ровно один раз). Для связного неориентированного графа это означает, что все его вершины должны иметь чётную степень. Для сильно связного ориентированного графа — что у каждой вершины полустепень захода должна быть равна полустепени исхода.