Дан граф с вершинами 1, 2, 3, 4, 5, 6 и ребрами с концами 1 и 2, 2 и 3, 3 и 4, 4 и 1, 5 и 4, 5 и 6, 3 и 6, 2 и 6, 6 и 3. Существует ли на графе эйлерова цепь?
Если такой цепи не существует, то в ответе укажите 0; если такая цепь есть, что в ответе укажите сумму номеров вершин, являющихся ее концами.
Рассмотрим граф с вершинами 1, 2, 3, 4, 5, 6 и ребрами: • (1,2) • (2,3) • (3,4) • (4,1) • (5,4) • (5,6) • (3,6) • (2,6) • (6,3)
Заметим, что ребра (3,6) и (6,3) представляют собой два ребра между вершинами 3 и 6 (то есть это кратные ребра).
Шаг 1. Определим степень каждой вершины, считая каждое ребро (включая кратные) отдельно.
– Вершина 1: инцидентны ребра (1,2) и (4,1) → степень = 2.
– В...