§ 48. Другие методы и задачи перечисления

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

Пусть - последовательность элементов множества Такую последовательность будем называть словом на а число ее членов - его длиной.

Если то говорят, что «место появления b в a», а также, что «b появляется в a».

На множестве слов введем внутренний закон композиции, называемый сцеплением:

Структура моноид, если закон всюду определен и ассоциативен. Пустую последовательность будем считать принадлежащей и называть «пустым словом». Она является нейтральным элементом в в противоположность латинскому закону композиции, определенному в § 41.

Пусть такие слова, что

тогда называют «левым сомножителем а», а у — «правым сомножителем а». Например, пусть слово на Слова -правые сомножители

Рис. 221

Рассмотрим граф на рис. 221. За слова примем последовательности его являющиеся путями. Пустое слово путь из 0 дуг. Если для путей ввести сцепление:

то этот закон будет определен всюду и мы приходим к латинской композиции.

Определим теперь понятие груды.

Грудой на множестве называют такую конечную последовательность

2) для выполняется одно из условий: левый сомножитель левый сомножитель Элементы груды называются ее состояниями, а последний элемент слова пиком состояния

Пример. Пусть

или

Последовательности

— труды. Элементы с и а — пики соответственно состояний не обладает пиком.

Для каждого элемента появляющегося в слове груды, определим его вход и его выход.

а) Предположим, что левый сомножитель тогда существует такой что Этот индекс называют входом

б) Предположим, что левый сомножитель тогда существует такой что Этот индекс называют выходом Элемент может обладать несколькими входами и выходами. Например, в (48.8): 1 — вход а, 2 — вход вход с, 4 — выход с, 5 — выход вход с, 7 — выход с, 8 — выход а обладают каждый одним входом и одним выходом, с обладает двумя входами и выходами). В (48.9): -вход а, 3 — вход с, 5 — выход каждый из элементов с и обладает одним входом и выходом.

Если каждый элемент появляющийся в слове груды, обладает одним и только одним входом (следовательно, одним и только одним выходом), то груду называют простой.

Слово груды, имеющее наибольшую длину, называют ее высотой.

Груда, построенная на дугах графа. Пусть —граф. Построим граф

где новая вершина,

Будем последовательно строить простую груду, элементами состояний которой являются дуги графа Возможны следующие случаи.

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

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

в) - выход дуги и и Тогда, если существует дуга со входом, не меньшим начало которой совпадает с началом и, то мы можем образовать состояние либо используя

эту дугу будет ее входом), либо выбрасывая пик состояния выход пика); если такой дуги нельзя найти, то у нас остается последняя возможность.

Таким образом, мы придем к простой груде, состояния которой — пути в началом в

Рис. 222.

Рис. 223.

Например, с графом на рис. 222 можно связать груды

(на рис. 223 изображены ее состояния),

Запись (48.12) с помощью вершин такова:

Груда, построенная на вершинах графа. Такую груду на множестве вершин графа можно построить последовательно.

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

б) Пусть и X — его пик. Тогда имеем три возможности:

1) -выход Если в наряду с У есть элемент не использовавшийся до этого момента при образовании нобого состояния из состояния с пиком X, то образуем

состояние либо используя будет его входом), либо выбрасывая будет выходом если такой вершины не существует, то остается последняя возможность.

первый вход Если то образуем у и выбрасывая X (i будет выходом X). Если то образуем беря некоторый элемент из будет входом этого элемента).

другой вход В этом случае образуем выбрасывая будет выходом .

Рис. 224.

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

Например (см. рис. 222—224), грудам (48.12) — (48.15) отвечают соответственно

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

Рис. 225.

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

Любому ветвящемуся графу можно сопоставить простые груды. Если фиксировать введенный ранее порядок, то такое сопоставление однозначно. Метод построения груды, указанный выше, в случае прадеревьев упрощается, так как пустыми ее состояниями могут быть только первое и последнее. Легко получить из ветвящегося графа прадерево, вводя корень и связывая его с корнями этого графа. Рассмотрим пополненный

ветвящийся граф на рис. 225. Упорядочим его следующим образом:

Такому порядку отвечает груда

Любой элемент из обладает одним и только одним входом; порядок появления элементов в груде называют порядком входа в груду. Аналогично определяется порядок выхода из груды.

Для графа на рис. 225 имеем

порядок входа:

порядок выхода:

С помощью так введенной груды легко решить следующие задачи.

1) Отыскать точки, предшествующие заданной.

2) Определить семейства ветвящегося графа.

3) Построить таблицу расположения вершин ветвящегося графа. Такая таблица состоит из трех столбцов. В первый помещаются вершины в порядке их входа в груду; во второй — первый элемент X из если третий — элемент следующий за X в его семействе. Приведем такую таблицу для графа на рис. 225:

4) Отыскать миноранты заданного элемента: любое состояние груды — путь графа, начинающийся в корне и оканчивающийся в пике

Понятие груды можно использовать также в некоторых случаях для получения транзитивного замыкания и элементарных путей графа.