НАЧАЛЬНЫЕ ПОНЯТИЯ О СЕТЯХ И ОРГРАФАХ

 

Ориентированный граф (орграф) - совокупность двух конечных множеств таких что:

§ то есть множество не пустое;

§ , то есть множество A состоит из упорядоченных пар элементов множества .

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

Вершины орграфа i и j называются смежными, если Дуга в этом случае называется инцидентной вершинам i и j. Число дуг, инцидентных данной вершине k, называется степенью вершины и обозначается Степень вершины в орграфе можно представить в виде deg(k) = od(k)+ id(k).

Здесь od(k) – полустепень исхода, т.е. число дуг, начинающихся в k (исходящих из k); id(k) – полустепень захода, то есть число дуг, заканчивающихся (заходящих) в k. В дальнейшем из рассмотрения исключаются орграфы с повторяющимися (кратными) дугами и петлями – дугами, которые соединяют вершину саму с собой.

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

Следуя [1], определим путь, соединяющий в орграфе вершины и как последовательность чередующихся вершин и дуг:

(1)

В последовательности (1) вершины и дуги не повторяются и

Замкнутый путь, в котором называется контуром. Если допустить, что в последовательности вида (1)

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

Следуя терминологии, принятой в [2], определим транспортную сеть N как связный орграф без контуров и петель, удовлетворяющий следующим условиям.

§ Существует только одна вершина с нулевой полустепенью захода. Эта вершина называется источником и обозначается через s.

§ Существует только одна вершина с нулевой полустепенью исхода. Эта вершина называется стоком и обозначается через t.

§ Каждой дуге в сети сопоставлено неотрицательное вещественное число называемое пропускной способностью дуги; если дуги в сети не существует, то полагают