Декомпозиция цикла (теория графов)

Обозначения, используемые для выражения перестановок , см. в разделе «Декомпозиция цикла (теория групп)» .

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

Циклическое разложение K _n и K _n − I

Брайан Олспах и Хизер Гавлас установили необходимые и достаточные условия существования разложения полного графа четного порядка минус 1-фактор ( совершенное паросочетание ) на четные циклы и полного графа нечетного порядка на нечетные циклы. Их доказательство опирается на графы Кэли , в частности, циркулянтные графы , и многие из их разложений происходят от действия перестановки на фиксированный подграф.

Они доказали, что для положительных четных целых чисел $m$ и $n$ с $4\leq m\leq n$, график $K_{n}-I$ (где $I$ является 1-фактором) можно разложить на циклы длины $m$ тогда и только тогда, когда число ребер в $K_{n}-I$ кратно $m$. Кроме того, для положительных нечетных целых чисел $m$ и $n$ с $3\leq m\leq n$, график $K_{n}$ можно разложить на циклы длины $m$ тогда и только тогда, когда число ребер в $K_{n}$ кратно $m$.

Ссылки

• Бонди, Дж.А.; Мурти, USR (2008), «2.4 Разложения и покрытия», Теория графов , Springer, ISBN  978-1-84628-969-9 .