2015-06-28
468
Докажите, что
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), 
Деревья 
соответствуют нетривильным внутренним сетям. Пусть 
число рёбер в Di , hi – число рёбер в соответствующей внутренней сети .
■
ТЕОРЕМА. Число всех различных попарно неизоморфных сетей с h рёбрами 
Доказательство. Число таких сетей равно числу кодовых деревьев. В каждой укладке дерева символы p и s расставляются двумя способами (при чередовании их по ярусам). Отсюда 
< 
.■
