§ 44. Перечисление элементарных контуров
Заметим, что элементарный контур 
длины 
становится элементарным путем, если удалить из него первую вершину, за примем свойство: «быть элементарным путем» Латинская матрица 
отличается от латинской матрицы 
тем, что из путей в клетках матрицы 
удалены первые вершины Подмножество
совпадает с подмножеством 
матрицы 
если Если 
может содержать латинскую последовательность Каждая такая последовательность оканчивается X, и представляет собой элементарный путь. Из наших рассмотрений вытекает, что, приписав 
к ней слева, потучим элементарный контур длины 
Таким образом, для получения элементарных контуров графа длины 
достаточно найти элементы главной диагонали матрицы
которую, например, можно представить так:
При 
где 
число вершин графа, элементы главной диагонали матрицы 
представляют собой
Рис. 208
гамильтоновы контуры графа, а все 
пусты, так как граф не содержит элементарных путей длины 
Так как через каждую вершину проходит любой гамильтонов котур, то все 
равны между собой, и достаточно найти одно из них.
Пример (рис. 208). Очевидно, что для нахождения гамильтоновых контуров этого графа достаточно выписать элементы одной клетки на главной диагонали матрицы 
Учитывая
находим 
Имеем
(см. скан)
Из (44.8) и (44.9) получаем первую строку и первый столбец матрицы 
Перемножив их, выписываем все гамильтоновы контуры:
Эти контуры изображены на рис. 209.
Рис. 219
УПРАЖНЕНИЯ
(см. скан)
