Левый берег

Правый берег

Вводные понятия

Теория грАфов

ЛЕКЦИЯ № 12

Как и большинство разделов дискретной математики, теория графов возникла при решении различных головоломок. Известна точная дата ее появления – 1736 г. Это год, в котором великий математик Леонард Эйлер опубликовал статью с решением задачи о Кенигсбергских мостах. В 18 в. Кенигсберг был расположен на обоих берегах и двух островах реки Пречель. Острова были связаны между собой и с берегами семью мостами:

Существовала популярная задача: можно ли, выйдя из дома, вернуться обратно, пройдя по каждому мосту ровно один раз?

Размышляя над этой задачей, Эйлер для удобства рассуждений изобразил ее в виде простой геометрической фигуры – из точек, соединенных линиями. Каждый берег и остров он изобразил точками, а мосты – линиями, их соединяющими. Получилась фигура, которая сейчас называется графом:

Задачу о мостах Эйлер сформулировал так: можно ли, начав движение из любой вершины, и двигаясь вдоль линий, пройти по каждой линии точно по одному разу и вернуться в исходную вершину?

В современной постановке задача звучит так: существует ли в данном мультиграфе простой цикл, содержащий все ребра?

В своей работе Эйлер

1) доказал, что эта задача не имеет решения;

2) сформулировал и доказал необходимое и достаточное условие существования в произвольном графе такого (Эйлерова) цикла.

Потом о теории графов забыли, чтобы вспомнить в 19 веке, когда возникли задачи исследования электрических цепей, моделей кристаллов и структур молекул. Новый всплеск интереса к теории графов приходится на средину 20 века. Выяснилось, что к задачам о графах сводится множество производственных и научных задач – прокладка трасс, проектирование систем управления и интегральных схем, построение логических схем в экономике, химии, биологии. В терминах теории графов формулируются основные алгоритмы, связанные с перебором вариантов. Без преувеличения можно сказать, что теория графов – язык дискретной математики.