Главная > Математика > Введение в прикладную комбинаторику
<< Предыдущий параграф
Следующий параграф >>
<< Предыдущий параграф Следующий параграф >>
Макеты страниц

§ 46. Перечисление факторов графа

Фактором графа называется частичный граф такой, что полустепени исхода и захода каждой его вершины равны 1. Таким образом, фактор графа составляется из непересекающихся контуров таких, что в совокупности они содержат все вершины графа и каждая встречается один раз. Например, на рис. 213 и 214 изображены факторы графа на рис. 212. Гамильтонов контур представляет собой фактор.

Фактор является элементом класса эквивалентности, определенного в § 16 В том же параграфе мы указали, как пересчитать эти классы Здесь же мы займемся перечислением их элементов, сопоставляя перестановкам возможные факторы заданного графа

Метод латинской композиции позволяет перечислить факторы графа, отыскивая элементарные контуры

Рассмотрим свойство последовательность является либо элементарным путем, либо элементарным контуром В обозначениях, введенных ранее,

Для единообразия будущих обозначений положим

Рис. 212

Рис. 213

Рис. 214

На главной диагонали матрицы представлены все элементарные контуры длины обозначает без главной диагонали Составим матрицу

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

и т. д. Таким образом, исключаемые главные диагонали дадут нам все элементарные контуры

Найдем таким способом факторы графа на рис. 212 (см, стр 259—261).

(кликните для просмотра скана)

(кликните для просмотра скана)

(кликните для просмотра скана)

Приходим к следующим элементарным контурам:

Рис. 215

Рис. 216.

Классы подстановок на множестве 6 элементов:

Учитывая (46.9), получаем

Два первых фактора представлены на рис. 213 и 214, а два последних на рис. 215 и 216.

УПРАЖНЕНИЯ

(см. скан)

<< Предыдущий параграф Следующий параграф >>
Оглавление