Суперпозиция сетей

Результатом подстановки вместо ребра сети Г ₁ другой сети называется сеть, полученная удалением из сети Г ₁ ребра и отождествлением полюсов а ₂, сети с вершинами сети Г ₁. Предположим, что сети Г ₁ и не пересекаются. Сеть Г ₁ в этом случае называем внешней, а сети, которые подставляем в неё вместо рёбер, называем внутренними. Сеть Г (а, полученная из сетей, изоморфных сетям Г ₁ , …, , путём применения конечного числа подстановок, называется суперпозицией этих сетей. Легко видеть, что суперпозиция – ассоциативная операция.

Сеть a b называется тривиальной. Сильносвязная сеть называется разложимой, если её можно представить в виде суперпозиции нетривиальных непересекающихся сетей. В противном случае сеть называется неразложимой. На рис. 5.20 и 5.21 представлены примеры неразложимых сетей (полюса помечены кружочками).

:

	a

Рис. 5.20 Рис. 5.21 Рис. 5.22 Рис. 5.23 Рис. 5.24

Можно показать, что любая нетривиальная неразложимая сильносвязная сеть, имеющая не более шести рёбер, изоморфна одной из этих трёх сетей, т.е. не существует неразложимых сильносвязных сетей с тремя, четырьмя и шестью рёбрами. В то же время для каждого существуют неразложимые сильносвязные сети h с рёбрами. Это видно на рис. 5.23 и 5.24. Множество нетривиальных неразложимых сетей, отличных от , обозначим через H и сеть, принадлежащую H, будем называть H -сетью.

Пусть – сеть, представляющая собой параллельное соединение h рёбер, – последовательное соединение h рёбер, . Если сеть Г (а, – суперпозиция сетей с внешней сетью , то она называется p-разложимой. Если сеть – суперпозиция сетей с внешней сетью , то она называется s-разложимой. Если сеть – суперпозиция сетей с внешней H- сетью, то она называется H-разложимой. Подсеть называется сквозной, если её полюса – это полюса основной сети.