§ 46. Перечисление факторов графа
Фактором графа 
называется частичный граф 
такой, что полустепени исхода и захода каждой его вершины равны 1. Таким образом, фактор графа составляется из непересекающихся контуров таких, что в совокупности они содержат все вершины графа и каждая встречается один раз. Например, на рис. 213 и 214 изображены факторы графа на рис. 212. Гамильтонов контур представляет собой фактор.
Фактор является элементом класса эквивалентности, определенного в § 16 В том же параграфе мы указали, как пересчитать эти классы Здесь же мы займемся перечислением их элементов, сопоставляя перестановкам возможные факторы заданного графа
Метод латинской композиции позволяет перечислить факторы графа, отыскивая элементарные контуры
Рассмотрим свойство последовательность является либо элементарным путем, либо элементарным контуром В обозначениях, введенных ранее,
Для единообразия будущих обозначений положим 
Рис. 212
Рис. 213
Рис. 214
На главной диагонали матрицы 
представлены все элементарные контуры длины 
обозначает 
без главной диагонали Составим матрицу
на главной диагонали которой будут представлены элементарные контуры длины 3. Аналогично из 
получаем 
и составляем
и т. д. Таким образом, исключаемые главные диагонали дадут нам все элементарные контуры
Найдем таким способом факторы графа на рис. 212 (см, стр 259—261).
(кликните для просмотра скана)
(кликните для просмотра скана)
(кликните для просмотра скана)
Приходим к следующим элементарным контурам:
Рис. 215
Рис. 216.
Классы подстановок на множестве 6 элементов:
Учитывая (46.9), получаем
Два первых фактора представлены на рис. 213 и 214, а два последних на рис. 215 и 216.
