Теория графов. Возникший в XVIII веке интерес к изучению графов прошел эволюцию от небольшого “развлекательного” раздела математики

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

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

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

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

Теория графов имеет тесные связи с такими разделами математики как теория автоматов, теория кодирования, топология, исследование операций и другими.

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

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

Дата добавления: 2014-11-15; просмотров: 230; Нарушение авторских прав

Мы поможем в написании ваших работ!