Question

96. Эйлеровой цепью графа называется маршрут, включающий A) не все ребра графа B) все ребра графа и через каждое ребро проходящий по одному разу C) все ребра графа и через каждое ребро проходящий по два раза D) все вершины графа и через каждую проходит по два раза E) все вершины графа и через каждую проходит по одному разу

Answer 1

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

Answer 2

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

Теперь рассмотрим предложенные варианты:

A) Эйлерова цепь, проходящая через не все рёбра графа, не соответствует определению Эйлеровой цепи.

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

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

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

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

Таким образом, правильные варианты ответа: B, D, E.