Сильно связная сеть

Cтраница 1

В дальнейшем будем рассматривать только силь. [1]

Сильно связная сеть Г ( а, Ь), не являющаяся разложимой, называется неразложимой. [2]

Сильно связная сеть Г ( а, Ь) распада-ется на два параллельных куска, если множество всех ее цепей можно разбить на два непустых класса так, что любые две цепи из разных классов не имеют общих внутренних вершин. [3]

Пусть в сильно связной сети Г имеется ровно одна минимальная вершина и не менее трех ребер. Доказать, что сеть Г является либо р -, либо s - разложимой. [4]

Пусть в сильно связной сети Г, имеющей не менее трех ребер, все минимальные вершины эквивалентны между собой. Доказать, что сеть Г либо р -, либо s - разложима. [5]

В противном случае сильно связная сеть называется неразложимой. Пусть Г ( а, 6) - разложимая сеть, G ( c, d ] - ее нетривиальная подсеть, a 1 ( а, b ] - сеть, полученная из Г ( а, 6) заменой подсети С. [6]

Пусть все вершины сильно связной сети Г минимальны. [7]

Очевидно, что всякая сильно связная сеть является одновременно и связной. [8]

Остается последняя возможность - удаление звезды приводит к сильно связной сети. [9]

Если Г ( а, Ь) - Н - сетъ и ( а, с) - ребро, принадлежащее полюсной звезде, то после удаления этого ребра получим сильно связную сеть. [10]

Заметим, что ловушка и тупик не исключают друг друга. В сильно связной сети множество Р всех ее мест обладает свойством Р Р, т.е. является одновременно ловушкой и тупиком. [11]

Пусть две сети S и Т не имеют общих элементов. И РТ соответственно с аа и ( Зя и удалим ребро а. Очевидно, что при этом снова получится сильно связная сеть, в которой Т будет уже подсетью. Рассмотренная операция называется операцией суперпозиции, или подстановкой сети Т вместо ребра а сети S. Обратная операция, заключающаяся в переходе от Sa ( T) к S, называется свертыванием подсети Т в ребро а. [12]

Свободная сеть на рис. 4.8 а содержит только один тупик р р рз - Р -, т.е. все множество мест сети. Тупик содержит размеченную ловушку, совпадающую с самим туликом, поэтому эта сеть - живая. Сеть на рис. 4.8 а покрывается разными совокупностями плотных подсетей, например, автоматными подсетями, показанными на рис. 4.8 6 и в. Однако только подсеть на рис. 4.8 5 является сильно связной сетью. Поэтому сеть на рис. 4.8 э не является безопасной. [13]

Страницы: 1