Теория графов и ее применение в науке

Картинка

История возникновения теории графов

Родоначальником теории графов считается Леонард Эйлер. Родился в 1707 году в Швейцарии. Оставил важнейшие труды по самым различным отраслям математики, механики, физики, астрономии и по ряду прикладных наук. Познания Эйлера были энциклопедичны; кроме математики, он глубоко изучал ботанику, медицину, химию, теорию музыки, множество европейских и древних языков. 13 марта 1736 года Эйлер в письме итальянскому математику и инженеру Джованни Джакобо Маринони приводит правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. В данном случае ответ был: «нельзя». В письме Карлу Готлибу Элеру от 3 апреля 1736 года Эйлер обосновывает найденное им правило, а позднее на эту тему Эйлер публикует статью в научном журнале Петербургской академии наук «Commentarii Academiae Scientiarum Imperialis Petropolitanae». Сам Термин "граф" впервые ввел Сильвестр, Джеймс Джозеф в 1878 году в своей статье в Nature.

Картинка

Решение Задачи «о семи мостах Кенигсберга»

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

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

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

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

Картинка

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

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