Графы и сети. Харитонова Е.В. - 5 стр.

UptoLike

ВУЗ: 

УлГТУ | Ульяновск

Составители: 

Рубрика: 

4
ВВЕДЕНИЕ
Первой работой теории графов как математической дисциплины считают
статью Эйлера (1736 г.), в которой рассматривалась задача о Кёнингсбергских
мостах. Эйлер показал, что нельзя обойти сеть городских мостов и вернуться в
исходную точку, пройдя по каждому мосту ровно один раз. Следующий им-
пульс теория графов получила спустя почти 100 лет с развитием исследований
по
электрическим сетям, кристаллографии, органической химии и другим нау-
кам.
С графами, сами того не замечая, мы сталкиваемся постоянно. Например,
графом является схема линий метрополитена. Точками на ней представлены
станции, а линиями – пути движения поездов. Исследуя свою родословную и
возводя ее к далекому предку, мы строим так называемое генеалогическое дре-
во.
И это древо – граф.
Графы служат удобным средством описания связей между объектами.
Например, рассматривая граф, изображающий сеть дорог между населенными
пунктами, можно определить маршрут проезда от пункта А до пункта Б. Если
таких маршрутов окажется несколько, хотелось бы выбрать в определенном
смысле оптимальный, например самый короткий или самый безопасный. Для
решения
задачи выбора требуется проводить определенные вычисления над
графами. При решении подобных задач удобно использовать алгебраическую
технику, да и само понятие графа необходимо формализовать.
Методы теории графов широко применяются в дискретной математике.
Без них невозможно обойтись при анализе и синтезе различных дискретных
преобразователей.
В настоящее время теория графов охватывает большой материал
и актив-
но развивается.
До появления сетевых методов планирование работ, проектов осуществ-
лялось в небольшом объеме. Наиболее известным средством такого планирова-
ния был ленточный график Ганта, недостаток которого состоит в том, что он не
позволяет установить зависимости между различными операциями.
Современное сетевое планирование начинается с разбиения программы
работ на операции.
Определяются оценки продолжительности операций, и
строится сетевая модель (график). Построение сетевой модели позволяет про-
анализировать все операции и внести улучшения в структуру модели до начала
ее реализации. Строится календарный график, определяющий начало и оконча-
ние каждой операции, а также взаимосвязи с другими операциями графика. Ка-
лендарный график выявляет критические операции, которым
надо уделять осо-
бое внимание, чтобы закончить все работы в директивный срок. Что касается
некритических операций, то календарный план позволяет определить резервы
времени, которые можно выгодно использовать при задержке выполнения ра-
бот или эффективном применении как трудовых, так и финансовых ресурсов.

Страницы