Упр.74 ГДЗ Бунимович Булычев 10 класс (Алгебра)

Какое максимальное число кёнигсбергских мостов можно пройти по одному разу и вернуться в исходную точку? А если не требовать возвращения в исходную точку?

Из рисунка видно, что у всех вершин кёнигсбергского графа нечётные степени. Значит, пройти по каждому мосту не более одного раза и вернуться в исходную точку нельзя: для такого обхода все вершины должны иметь чётные степени.

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

Следовательно, максимальное число мостов при обходе с возвращением в исходную точку равно $$0$$, а без возвращения в исходную точку — $$6$$.

Ответ

$$0$$; $$6$$.