Картинки из квадратов \ Прямоугольники, собранные из квадратов \ Блочные системы и сети \

5.3.2. Сеть, ассоциированная
с блочной системой

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

Вертикальные отрезки на блочной системе ассоциируются с гранями отвечающей ей сети. У рассматриваемой нами блочной системы имеется 8 вертикальных отрезков (они закрашены красным цветом на рисунке ниже; отметим, что в "вертикальном случае" нас интересуют только "внутренние" вертикальные отрезки), поэтому соответствующая сеть будет иметь 8 граней. Мы обозначили их K1, K2, ... , K8 (использование буквы "K" оправдывается тем, что при электрической интерпретации грани сети принято называть "контурами").
К началу данной страницы
Картинки из квадратов \ Прямоугольники, собранные из квадратов \ Блочные системы и сети \