Страница 56 номер 79, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Докажите, что если мультиграф содержит эйлеров цикл, то степени всех его вершин чётные (необходимое условие в теореме Эйлера).
Пусть в мультиграфе есть эйлеров цикл — замкнутый маршрут по всем рёбрам, каждое ровно один раз; его начальная вершина \(v\).
Пусть вершина \(x\) отлична от \(v\). Каждый раз, когда \(x\) встречается в записи цикла, с этим появлением связаны ровно два ребра: то, по которому в \(x\) вошли, и то, по которому вышли; разные появления дают разные рёбра, потому что каждое ребро пройдено один раз. Значит, если \(x\) встречается \(k\) раз, то её степень равна \(2k\), а это число чётное.
Пусть теперь \(x\) совпадает с \(v\). Первое появление \(v\) даёт ребро, по которому маршрут вышел, последнее — ребро, по которому вернулся, и они тоже образуют пару, а каждое из остальных появлений даёт по два ребра. Значит, и степень вершины \(v\) чётна.
Петля при вершине проходится один раз и добавляет к степени 2 — на чётность это не влияет.
Значит, степени всех вершин мультиграфа чётные.
Ответ: утверждение доказано: если мультиграф содержит эйлеров цикл, то рёбра при каждой вершине разбиваются на пары «вошли — вышли», а у начальной вершины пару образуют первое и последнее рёбра цикла, поэтому все степени чётные.
Докажите, что если мультиграф содержит эйлеров цикл, то степени всех его вершин чётные (необходимое условие в теореме Эйлера).
Пусть в мультиграфе есть эйлеров цикл, то есть замкнутый маршрут, который проходит по каждому ребру ровно один раз и заканчивается в той же вершине, где начался. Обозначим эту начальную вершину \(v\).
Возьмём произвольную вершину \(x\) и посчитаем её степень. Каждое ребро, выходящее из \(x\), встречается в цикле ровно один раз, поэтому степень \(x\) равна количеству тех проходов цикла, при которых он касается вершины \(x\), считая каждое касание за два ребра.
Пусть сначала \(x\) отлична от \(v\). Каждый раз, когда \(x\) встречается в записи цикла, она стоит между двумя соседними вершинами, то есть с этим появлением связаны ровно два ребра: то, по которому в \(x\) вошли, и то, по которому из неё вышли. Разные появления дают разные рёбра, потому что каждое ребро пройдено только один раз. Значит, все рёбра при вершине \(x\) разбиваются на пары «вошли — вышли»: если \(x\) встречается в цикле \(k\) раз, то её степень равна \(2k\), а это число чётное.
Теперь пусть \(x\) совпадает с начальной вершиной \(v\). Здесь рассуждение то же, только первое появление \(v\) даёт одно ребро — то, по которому маршрут вышел, а последнее появление даёт одно ребро — то, по которому маршрут вернулся. Эти два ребра тоже образуют пару, а каждое из остальных появлений \(v\) даёт, как и раньше, по два ребра. Значит, и степень вершины \(v\) чётна.
Если при вершине есть петля, она проходится один раз, маршрут выходит из вершины и сразу же в неё возвращается, а к степени петля добавляет 2 — на чётность это не влияет.
Значит, степени всех вершин мультиграфа чётные.
Ответ: утверждение доказано: если мультиграф содержит эйлеров цикл, то рёбра при каждой вершине разбиваются на пары «вошли — вышли», а у начальной вершины пару образуют первое и последнее рёбра цикла, поэтому все степени чётные.
