|
5.3.2. Сеть, ассоциированная с блочной системой
|
|
Выделение в
блочной системе горизонтальных отрезков
(которые будут соответствовать
вершинам), является первым этапом в процессе
построения
сети, отвечающей блочной системе.
|
Все последующие рассмотрения будем иллюстрировать на примере блочной системы, изображенной слева.
Как мы увидим, ей отвечает сеть, состоящая из 7 вершин, 14 ребер и 8 граней.
Определения горизонтальных и вертикальных отрезков можно найти также в книге
Яглома.
|
Прежде всего мы выделяем два горизонтальных отрезка, лежащие на
верхней и
нижней сторонах блочной системы
(они будут соответствовать
истоку и
стоку сети).
Выделяемые отрезки мы закрашиваем зеленым цветом и помечаем символами, которыми затем
будут помечены вершины сети (в данном случае это символы
s
и
t).
Теперь переходим к выделению внутренних горизонтальных отрезков блочной системы.
Смысл этих отрезков очевиден из представленного ниже рисунка (они помечены числами 1, 2, ... , 5).
Итак, всего у рассматриваемой блочной системы имеется 7 горизонтальных отрезков; следовательно,
у отвечающей ей сети будет иметься 7 вершин.
Ребер у сети будет столько, сколько квадратов у блочной системы
(т. е. в данном случае 14).
Две вершины будут соединены ребром тогда и только тогда, когда отвечающий ребру квадрат блочной системы
соединяет два горизонтальных отрезка, отвечающих этим вершинам.
В итоге получаем сеть, изображенную ниже:
Еще раз подчеркнем, что при рисовании сетей нам безразличны длина и форма их ребер;
значение имеет только лишь
общая архитектура связи ребер с вершинами (определяемая архитектурой
связи квадратов с горизонтальными отрезками в соответствующей блочной системе).
Таким образом, при рисовании сетей у нас имеется значительная свобода, ограниченная только
рядом сформулированных ранее требований.
Вертикальные отрезки на блочной системе ассоциируются с
гранями отвечающей ей сети.
У рассматриваемой нами блочной системы имеется 8 вертикальных отрезков (они закрашены красным цветом
на рисунке ниже; отметим, что в "вертикальном случае" нас интересуют только "внутренние" вертикальные отрезки),
поэтому соответствующая сеть будет иметь 8 граней. Мы обозначили их
K1,
K2, ... ,
K8
(использование буквы "
K" оправдывается тем, что при электрической интерпретации грани сети принято называть
"контурами").