§ 41. Метод латинской композиции

Конечная последовательность вершин графа называется латинской последовательностью со свойством или -латинской последовательностью, если:

1) она является путем,

2) она обладает свойством

3) любой ее отрезок длины 2 также обладает этим свойством.

Пусть

— две -латинские последовательности.

Введем бинарную операцию

Если принять, что 0 обладает свойством то -латинские последовательности графа образуют группоид относительно закона композиции, для которого

Основные свойства этого группоида следующие.

1) Этот группоид ассоциативен, т. е. он моноид, или полугруппа; в самом деле, для любых его элементов

2) Существуют как правые, так и левые нейтральные элементы, которые не единственны. Имеем

т. e. - элемент, нейтральный справа. Аналогично

т. e. - элемент, нейтральный слева.

3) Этот моноид не обладает нейтральным элементом, и не существует обратных элементов.

4) Все элементы моноида регулярны как слева, так и справа:

5) Моноид, очевидно, не коммутативен.

Для упрощения введем обозначение:

то

где последовательность без первой вершины.

Обозначим через

подмножество -латинских последовательностей с вершинами, начинающихся и оканчивающихся Аналогично

Определим произведение

(одинаковые элементы учитываются по одному разу). Как и в (41.16), можно записать

где

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

Выпишем последовательно

где

Для любых целых положительных имеем

Исходя из (41.22) — (41.25), введем матрицы, которые назовем латинскими:

где на пересечении строки и столбца матрицы стоит

а на пересечении строки и столбца матрицы стоит

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