Задание 2. Дан граф с вершинами A, B, C, D, E и рёбрами: AB, AC, AD, BC, BE, CD, DE. Постройте его и выполните задание: а) Запишите степени всех вершин. б) Существует ли в этом графе эйлеров путь (путь, проходящий по всем рёбрам ровно по одному разу)? Если да, запишите один такой путь.

Строим граф по заданным рёбрам:

а) Степень вершины — число рёбер, выходящих из неё. Поэтому deg(A) = 3 (AB, AC, AD), deg(B) = 3 (AB, BC, BE), deg(C) = 3 (AC, BC, CD), deg(D) = 3 (AD, CD, DE), deg(E) = 2 (BE, DE).

б) В связном графе эйлеров путь существует, если нечётных вершин не больше двух. Здесь четыре вершины нечётной степени: A, B, C и D. Следовательно, эйлерова пути нет.

Ответ: степени вершин — A: 3, B: 3, C: 3, D: 3, E: 2; эйлерова пути не существует.