Страница 56 номер 74, ГДЗ по алгебре за 10 класс к учебнику Бунимовича. Математика вероятность и статистика
Какое максимальное число кёнигсбергских мостов можно пройти по одному разу и вернуться в исходную точку? А если не требовать возвращения в исходную точку?
Части города — вершины, мосты — рёбра мультиграфа: \(a\) — северный берег, \(b\) — остров, \(c\) — южный берег, \(d\) — восточный район. Остров \(b\) связан с \(a\) двумя мостами и с \(c\) тоже двумя, есть по одному мосту \(bd\), \(ad\) и \(cd\) — всего 7 рёбер. Степени вершин: \(a\) — 3, \(b\) — 5, \(c\) — 3, \(d\) — 3. Проверка суммы: \(3 + 5 + 3 + 3 = 14 = 2 \cdot 7\). Все четыре вершины нечётные.
Прогулка с возвращением. Пройденные мосты образуют эйлеров цикл, поэтому у всех вершин пройденной части степени чётные. Выбрасывание одного моста меняет чётность ровно двух вершин и уменьшает число нечётных вершин не больше чем на 2, а их четыре: выбросить придётся хотя бы два моста, и пройти удастся не больше \(7 - 2 = 5\) мостов.
Пять мостов пройти можно: уберём один из двух мостов между \(b\) и \(a\) и мост \(cd\). Останутся \(ab\), оба моста \(bc\), \(bd\) и \(ad\); степени вершин стали чётными: \(a\) — 2, \(b\) — 4, \(c\) — 2, \(d\) — 2, и все четыре части города по-прежнему связаны. Маршрут: с берега \(a\) на остров \(b\), оттуда первым мостом на берег \(c\), вторым мостом обратно на остров \(b\), затем в район \(d\) и из него на берег \(a\). Пройдено 5 мостов, каждый ровно один раз, прогулка кончилась там же, где началась.
Прогулка без возвращения. Пройденные мосты образуют незамкнутую цепь, у которой нечётных вершин не больше двух. Сейчас их четыре, а один выброшенный мост уменьшает их число не больше чем на 2: пройти удастся не больше \(7 - 1 = 6\) мостов.
Шесть мостов пройти можно: уберём один из двух мостов между \(b\) и \(c\). Останется 6 мостов, степени вершин станут такими: \(a\) — 3, \(b\) — 4, \(c\) — 2, \(d\) — 3; нечётных ровно две, \(a\) и \(d\), они и будут началом и концом. Маршрут: с берега \(a\) первым мостом на остров \(b\), оттуда на берег \(c\), из него в район \(d\), обратно на остров \(b\), вторым мостом на берег \(a\) и, наконец, из \(a\) в район \(d\). Пройдено 6 мостов, каждый ровно один раз.
Ответ: наибольшее число мостов, которые можно пройти по одному разу и вернуться в исходную точку, равно 5; если возвращаться в исходную точку не требуется, наибольшее число мостов равно 6, а все семь мостов не удаётся пройти ни с возвращением, ни без него.
Какое максимальное число кёнигсбергских мостов можно пройти по одному разу и вернуться в исходную точку? А если не требовать возвращения в исходную точку?
Сопоставим каждой из четырёх частей города вершину, а каждому мосту — ребро. Получается мультиграф: \(a\) — северный берег, \(b\) — остров, \(c\) — южный берег, \(d\) — восточный район. Остров \(b\) связан с северным берегом \(a\) двумя мостами и с южным берегом \(c\) тоже двумя; кроме того, есть по одному мосту \(bd\), \(ad\) и \(cd\) — всего 7 рёбер. Степени вершин: \(a\) — 3, \(b\) — 5, \(c\) — 3, \(d\) — 3. Проверка суммы: \(3 + 5 + 3 + 3 = 14 = 2 \cdot 7\). Все четыре вершины нечётные.
Прогулка с возвращением. Пройденные мосты образуют часть мультиграфа, и в этой части маршрут проходит по каждому ребру ровно один раз и замыкается, то есть является эйлеровым циклом. Значит, у всех вершин этой части степени чётные, и задача сводится к тому, чтобы выбросить как можно меньше мостов, оставив связную часть со всеми чётными степенями.
Выбрасывание одного моста меняет чётность ровно двух вершин, поэтому оно уменьшает число нечётных вершин не более чем на 2. Нечётных вершин четыре, поэтому одного выброшенного моста мало — выбросить придётся хотя бы два. Значит, пройти удастся не больше \(7 - 2 = 5\) мостов.
Пять мостов пройти можно. Уберём один из двух мостов между островом \(b\) и северным берегом \(a\), а также мост \(cd\) между южным берегом и восточным районом. Останутся мосты \(ab\), \(bc\), второй \(bc\), \(bd\) и \(ad\) — пять штук; степени вершин стали чётными: \(a\) — 2, \(b\) — 4, \(c\) — 2, \(d\) — 2, и все четыре части города по-прежнему связаны между собой. Вот сам маршрут: с северного берега \(a\) по мосту на остров \(b\), с острова по первому мосту на южный берег \(c\), обратно по второму мосту на остров \(b\), с острова в восточный район \(d\) и из него по мосту на северный берег \(a\). Пройдено 5 мостов, каждый ровно один раз, прогулка кончилась там же, где началась.
Прогулка без возвращения. Теперь пройденные мосты образуют незамкнутую цепь. У неё чётную степень имеют все вершины, кроме начала и конца, поэтому нечётных вершин в пройденной части не больше двух. Сейчас их четыре, а один выброшенный мост уменьшает их число не более чем на 2, значит, без одного выброшенного моста не обойтись и пройти удастся не больше \(7 - 1 = 6\) мостов.
Шесть мостов пройти можно. Уберём один из двух мостов между островом \(b\) и южным берегом \(c\). Останется 6 мостов, а степени вершин станут такими: \(a\) — 3, \(b\) — 4, \(c\) — 2, \(d\) — 3; нечётных ровно две, \(a\) и \(d\), они и будут началом и концом. Вот маршрут: с северного берега \(a\) по первому мосту на остров \(b\), с острова на южный берег \(c\), оттуда в восточный район \(d\), из него обратно на остров \(b\), с острова по второму мосту на северный берег \(a\) и, наконец, из \(a\) в восточный район \(d\). Пройдено 6 мостов, каждый ровно один раз.
Ответ: наибольшее число мостов, которые можно пройти по одному разу и вернуться в исходную точку, равно 5; если возвращаться в исходную точку не требуется, наибольшее число мостов равно 6, а все семь мостов не удаётся пройти ни с возвращением, ни без него.
