Упражнение

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

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

2) сеть s-разложима имеет разделяющую вершину;

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

5.15. p-сети

Суперпозиция сетей называется p-сетью. Каждой p-сети можно поставить во взаимнооднозначное соответствие укладку дерева, неконцевым вершинам которого сопоставлены символы p и s. Сопоставление производится по правилу:

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

 

 

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

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

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

■

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

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