Множества. Комбинаторика. Отношения (стр. 25 )

Доказательство. Составим цепь из части первой от полюса а до маршрута -и части второй цепи отдо в. <

Пусть в сети Г(а,в) выделено подмножество рёбер, которое определяет подграф. Вершина подграфа называется граничной, если она полюс сети, либо конец ребра, не принадлежащего подграфу. Подграф с единственной граничной вершиной называется отростком.

ТЕОРЕМА. Связная сеть сильно связана не содержит отростков.

Доказательство. Пусть связная сеть сильно связана и содержит отросток. Маршрут, соединяющий полюса и проходящий через ребро отрезка, должен, по крайней мере, дважды пройти через граничную вершину отростка. Такой маршрут не является цепью (по определению цепь не проходит через вершины дважды).

Пусть связная сеть Г(а,в) не содержит отростков и предположим, что она не сильно связна. Тогда в ней есть рёбра, через которые не проходит ни одной цепи. Пусть – максимальное связное подмножество рёбер, обладающих этим свойством. В силу связности сети имеет граничные вершины. По условию в нашей сети нет отростков, поэтому существует, по крайней мере, две граничные вершины и подграфа . Через вершины и проходят цепи. В силу связности по лемме существует цепь, проходящая через вершины и и через рёбра . <

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

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

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

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

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

Упражнения

Докажите, что:

1) сеть S – разложима имеет разделяющую вершину;

2) H-сеть не имеет разделяющей вершины, т. е. вершины, через которую проходит каждая цепь;

3) сеть р–разложима имеет собственную сквозную подсеть.

3.2.3 p-сети

Суперпозиция сетей называется p-сетью. Каждой p-сети можно поставить во взаимнооднозначное соответствие укладку дерева, неконцевым вершинам которого сопоставлены символы p и s. Сопоставление производится по следующему правилу. Сети ставим в соответствие пучок из h рёбер, корень которого помечен символом где или p. Пусть имеет в качестве внешней сети. Такая сеть кодируется пучком из h рёбер, корень которого помечен символом и каждое ребро соответствует внутренней подсети (каждая из которых уже не является суперпозицией с внешней сетью ).

Лемма. Сеть с h рёбрами кодируется деревом с числом рёбер

Доказательство. Индукция по h. Для h=2 очевидно. Предположим что для сетей с числом рёбер меньше h утверждение верно.

Пусть сеть Г(а, в) имеет h рёбер и кодируется деревом m исходящими из корня рёбрами, из которых t не концевые, Деревья соответствую нетривиальным внутренним сетям. Пусть число рёбер в Дi , hi – число рёбер в соответствующей внутренней сети Г(а, в). Тогда

<

ТЕОРЕМА. Число всех различных попарно неизоморфных сетей с h рёбрами

Доказательство. Число таких сетей равно числу кодовых деревьев. В каждой укладке дерева символы p и s расставляются двумя способами (при чередовании их по ярусам). Отсюда

<. <