Номер 129 ГДЗ Вероятность и статистика 7 класс, Бунимович 2024, страница 97

В мультиграфе рисунка есть по два ребра ab и bc и по одному ad, bd, cd. Степени a, b, c, d равны , , , .

1. Для возвращения нужен цикл без повторения рёбер. В подграфе из пройденных рёбер степени всех вершин чётны, поскольку входы и выходы объединяются в пары.

У a, c, d степень в исходном графе равна . В подграфе цикла чётная степень каждой из них не больше . У b исходная степень , значит, чётная степень не больше .

Сумма степеней пройденного подграфа не больше . По теореме рёбер в нём не больше . Эта верхняя граница достигается: удалим мост ad и один из двух мостов bc. Оставшийся подграф имеет степени , , , и связен. Его цикл: a — b — c — d — b — a, где два прохождения между a и b идут по разным мостам. Значит, можно пройти мостов и вернуться.

2. Без возвращения по всем семи мостам пройти нельзя: нечётных вершин четыре, а для эйлерова пути нужны две. Поэтому максимум не больше .

Удалим ребро ad. Тогда степени a и d становятся чётными — и ; степени b и c остаются нечётными — и . Граф связен, поэтому имеет эйлеров путь.

Пример: b — a — b — c — b — d — c. Между a и b использованы два разных моста, между b и c — тоже два разных. Ещё использованы bd и dc. Всего мостов, повторений нет.

Таким образом, по изображённому мультиграфу максимумы равны и .

В ответах учебника — и , но маршрут a — b — c — d — b — a по пяти мостам возвращается в исходную точку, и по условию повторять нельзя только мосты, а не берега: поэтому при подсчёте получается , а не ; в ответе учебника, вероятно, опечатка.