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

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

Возникновение теории графов как математической дисциплины принято связывать с именем Леонарда Эйлера, который в 1735 г. доказал условие существования в связном графе цикла, содержащего все его ребра без повторений. С тех пор такой цикл называется эйлеровым, если в нем существует эйлеров цикл.

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

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

Графы используются для построения моделей и решения многих практических задач. В зависимости от задачи ребрам графа могут ставиться в соответствие некоторые числа, характеризующие например, длину дороги, либо стоимость или время проезда, либо другую характеристику моделируемого ребром объекта. Такие графы называют сетями.

Классическая задача почтальона, который должен разнести почту по всем улицам своего участка за минимальное время (или пройдя минимальное расстояние) связана с эйлеровыми графами.

Еще одна классическая задача на графах – задача коммивояжера, который должен доставить товар в несколько городов и вернуться в исходный, минимизировав стоимость проезда (или расстояние). В терминах графа эта задача сводится к нахождению в графе простого цикла, содержащего все его вершины.

В настоящее время теория графов получила широкое развитие, поскольку она позволяет моделировать и решать много практических задач из различных областей деятельности, в том числе инженерной. Широко применимы:

- транспортная задача, в которой необходимо минимизировать затраты на перевозку продуктов из пунктов производства в пункты потребления, удовлетворив при этом спрос предложением;

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

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

Существует и много других задач.

Контрольные вопросы:

1. Какая задача послужила источником Эйлерову для создания теории графов?

2. Какие есть задачи на графах?

3. Какая классическая задача связана с эйлеровыми графами?

---

Дата добавления: 2015-08-28