Дано:
Пусть G = (V, E) - мультиграф, который содержит эйлеров цикл. Обозначим вершины графа как v1, v2, ..., vn. Степень вершины vi обозначается как d(vi).
Найти:
Необходимо доказать, что степени всех вершин в мультиграфе G являются чётными.
Решение:
1. Эйлеров цикл - это цикл, который проходит через каждое ребро графа ровно один раз и возвращается в начальную вершину.
2. При прохождении по эйлерову циклу каждая вершина может быть посещена несколько раз, но каждое ребро будет использовано только один раз.
3. Когда мы заходим в вершину vi, мы используем одно ребро, и когда мы выходим из этой же вершины, мы используем еще одно ребро. Это означает, что для каждой вершины vi количество входящих и исходящих рёбер всегда будет равным.
4. Таким образом, если мы рассматриваем все пары входящих и исходящих рёбер для каждой вершины во время обхода цикла, то у каждой вершины используется четное количество рёбер.
5. Поэтому степень каждой вершины d(vi) равна количеству рёбер, которые входят в неё и выходят из неё. Поскольку каждая вершина имеет одинаковое количество входящих и исходящих рёбер, это означает, что d(vi) является четным числом.
6. Таким образом, для всех вершин vi в графе G выполняется условие, что d(vi) является чётным.
Ответ:
Если мультиграф содержит эйлеров цикл, то степени всех его вершин являются чётными.