Задача о мостах, Леонард Эйлер и теория графов
Издавна среди жителей Кёнигсберга была распространена такаязагадка: как пройти по всем мостам, не проходя ни по одному из них дважды?Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически,во время прогулок. Но никому это не удавалось, однако не удавалось и доказать,что это даже теоретически невозможно.
В 1736 году задача о семи мостах заинтересовала выдающегосяматематика, члена Петербургской академии наук Леонарда Эйлера, о чём он написалв письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. Вэтом письме Эйлер пишет о том, что он смог найти правило, пользуясь которымлегко определить, можно ли пройти по всем мостам, не проходя дважды ни поодному из них (в случае семи мостов Кёнигсберга это невозможно).
На упрощённой схеме части города (графе) мостамсоответствуют линии (рёбра графа), а частям города — точки соединения линий(вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётноечисло рёбер) графа должно быть чётно. Не может существовать граф, который имелбы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрываякарандаша от бумаги, начертить граф, при этом можно начинать с любой вершиныграфа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможноначертить одним росчерком.
Граф кёнигсбергских мостов имел четыре нечётные вершины(т.е. все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Упрощённаясхема мостов Кёнигсберга. Значение букв и цифр — см. комментарий к старинной карте Кёнигсберга
Граф кёнигсбергских мостов
Созданная Эйлером теория графов нашла очень широкое применение: например, её используют при изучении транспортных и коммуникационных систем, в частности, для маршрутизации данных в Интернете.
Изучи теоретический материал: Основы теории графов. Способы представления графов. Обход графа
Графы - 1 Построение направленного графа по заданному описанию отношений. Графы - 2 Построение направленного графа по заданному описанию отношений. Графы - 3 Построение направленного графа по заданному описанию отношений Графы - 4 Построение направленного графа по заданному описанию отношений Графы - 5 Построение направленного графа по заданному описанию отношений Пути в графах-1 Закрепление умения находить и описывать пути в графах