4.1. Упрощение сети

Иногда построенную по проекту сеть удается упростить. Некоторые вершины можно Склеить, удалив часть вершин и фиктивных дуг.

Определение 4.4. Две сети с однинаковым множеством нефиктивных дуг называются Эквивалетными, если они представляют одно и то же отношение подчиненности дуг.

Будем использовать обозначения:

S=(X,U) – сеть;

I(J) – начальная вершина дуги J;

K(J) – конечная вершина дуги J;

– множество нефиктивных дуг сети;

Ui – подмножество нефиктивных дуг, принадлежащих путям из источника в вершину I;

Ui – подмножество нефиктивных дуг, принадлежащих путям из вершины I в сток.

Определим пару вершин I и K, для которых в сети:

(1) не существует инцидентной им обеим нефиктивной дуги JÎ;

(2) не существует дуг P,QÎ таких, что:

· I(p)=i(q), k(p)=i, k(q)=k,

· либо K(p)=k(q), i(p)=1, i(q)=k.

Результатом Склейки вершин I и K сети S, удовлетворяющих свойствам (1) и (2), является сеть S¢, в которой вершина K удалена, а все дуги, которые были ей инцидентные в S, в S¢ инцидентны вершине I. Если в S¢ окажется неколько параллельных фиктивных дуг, то все, кроме одной, удаляются.

Очевидно, некоторый путь M(A,B)ÎS¢ тогда и только тогда, когда M(A,B)ÎS.

Приведем без доказательства необходимое и достаточное условие эквивалентности сетей до и после склейки.

Утверждение 4.1. Пусть вершины I и K удовлетворяют условиям (1) и (2). Сеть S¢, полученная из S в результате склеивания I и K и исключения K, эквивалентна S тогда и только тогда, когда:

- либо Ui =Uk,

- либо Ui =Uk.

< Предыдущая		Следующая >