Математика. Графы. К мостам Кёнигсберга. Решение задачи по Леонарду Эйлеру.

Известно, что великий швейцарский математик Эйлер создал целое направление науки, решая задачу о семи кенигсбергских мостах.

Существует легенда, что жители Кенигсберга любили прогуливаться по улицам трех "слившихся" в единое целое средневековых городов: Альштадта, Лебенихта и Кнайпхофа - но терпеть не могли зря топтать свои башмаки. А города эти были соединены между собой семью мостами. И вот будто бы экономные горожане однажды задумались: а можно ли пройти по всем мостам так, чтобы на каждом из них побывать лишь один раз и вернуться к месту, откуда начал прогулку?

Эйлера задача заинтересовала. "Никто еще до сих пор не смог это проделать, но никто и не доказал, что это невозможно... Для решения недостаточны ни геометрия, ни алгебра, ни комбинаторское искусство", - так писал он своему коллеге, итальянскому математику и инженеру...

В конце концов, выстроив сложнейший алгоритм, Эйлер получил отрицательный ответ. Пройти по всем мостам лишь по одному разу и, описав круг, вернуться в исходную точку, оказалось невозможным.

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

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

Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

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

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

Любопытно, что другое решение задачи предложил кайзер Вильгельм. На приёме ему поднесли карту Кёнигсберга и предложили решить загадку семи мостов. Вильгельм не растерялся, а тут же приказал построить восьмой мост. После чего задача стала легкорешаемой.

Третье решение придумали речники. За небольшую плату они предлагают перевезти всех, кому не хватает моста для решения задачки.

Решение задачи по Леонарду Эйлеру На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам: Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин. Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине. Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком. Граф кёнигсбергских мостов имел четыре (синим) нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды Созданная Эйлером теория графов нашла очень широкое применение в транспортных и коммуникационных системах (например, для изучения самих систем, составления оптимальных маршрутов доставки грузов или маршрутизации данных в Интернете).