Строительные технологии

Система сетевого планирования и управления основана на теории графов, являющейся разделом современной математики. Теория графов самостоятельно сформировалась в 40-50-х годах XX столетия, хотя отдельные задачи о графах и решались значительно ранее, а некоторые даже насчитывают более чем двухсотлетнюю историю.

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

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

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