Теоретические основы СПУ

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

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

Ребра могут быть ориентированными (снабжены стрелками – дуги) и неориентированными.

Имеется несколько типов графов:

а) обыкновенный граф (без дуг, петель и кратных ребер);

б) мультиграф (имеются кратные ребра);

в) ориентированный (обыкновенный с ориентированными ребрами);

г) смешанный (схема движения по улице).

а) б) в)

г)

Графы бывают также конечные и бесконечные, пространственные и плоские.

Основатель теории графов – Л. Эйлер, рассмотревший в 1736 г. задачу о «кененгбергских мостах».

В основе сетевого графика лежит ориентированный граф. Одной из основных конструкций графа является путь.

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

Замкнутый путь называется контуром.