ГДЗ по информатике 9 класс Босова, номер §2.3 ПМ 2

§. ПМ Задача о мостах Кёнигсберга

Река Преголя в центре старинного Кёнигсберга (ныне Калининград) разделяется на два русла. В некоторых местах эти русла соединены протоками. Благодаря одной такой протоке центр города оказался разбит на четыре части, которые со временем соединили мостами. Известна старинная математическая задача, в которой спрашивалось: можно ли пройти по всем семи мостам центра старого Кёнигсберга, не проходя ни по одному из них дважды? Перед вами схема центра Кёнигсберга (рис. 2.11). Можете попробовать решить эту задачу. Определив чётность вершин А, В, С и D графа мостов Кёнигсберга (рис. 2.12), завершите решение задачи.

Решение

Заменим четыре части города вершинами А, В, С, D, а каждый мост — ребром графа, как на рис. .. Между А и В проведены два моста, между А и С — один, между В и С — один, между В и D — два, между С и D — один. Проверяем число рёбер, выходящих из каждой вершины; пара мостов между одними и теми же частями города считается двумя рёбрами.

Из А выходят два ребра к В и одно к С: . Значит, вершина А нечётная.

Из В выходят два ребра к А, одно к С и два к D: . Значит, вершина В нечётная.

Из С выходят по одному ребру к А, В и D: . Значит, вершина С нечётная.

Из D выходят два ребра к В и одно к С: . Значит, вершина D нечётная. Число мостов совпадает с условием: , так как каждое ребро при подсчёте степеней учтено у двух концов.

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

Ответ

Нет. У графа мостов четыре нечётные вершины: А — ребра, В — , С — , D — .

Помогло?

Номер §2.3 ПМ 2