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