Справочный материал «Теория графов. Введение»
©кабинет 21, 2006-2015
Теория графов и Леонард Эйлер
Издавна среди жителей Кёнигсберга (Калининград) была распространена загадка: как пройти по всем мостам (через реку Преголь), не проходя ни по одному из них дважды. Многие люди пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но доказать или опровергнуть возможность существования такого маршрута никто не мог.
В 1736 году задача заинтересовала выдающегося математика Леонарда Эйлера и вскоре он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них.
На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам:
Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Созданная Эйлером теория графов нашла широкое применение (в транспортных системах – составление оптимальных маршрутов доставки грузов, экономике и т.д.).
«Решение» Кайзера
На карте старого Кёнигсберга был ещё один мост, появившийся чуть позже. Своим появлением этот мост обязан самой задаче Эйлера-Канта. Произошло это при следующих обстоятельствах.
Император Вильгельм был известен своей прямотой, простотой мышления и солдатской «недалёкостью». Однажды, находясь на светском рауте, он чуть не стал жертвой шутки, которую с ним решили сыграть учёные умы, присутствующие на приёме. Они показали Кайзеру карту Кёнигсберга, и попросили попробовать решить эту знаменитую задачу, которая по определению была нерешаемой. Ко всеобщему удивлению, Кайзер попросил перо и лист бумаги, сказав, что решит задачу за полторы минуты. Ошеломлённые люди не могли поверить своим ушам, но бумагу и чернила быстро нашли. Кайзер положил листок на стол, взял перо и написал следующее: «Приказываю построить восьмой мост на острове Ломзе». Так в Кёнигсберге и появился новый мост, который назвали «мостом Кайзера». А задачу с восемью мостами теперь мог решить даже ребёнок.
