Вывод формул для количества циклов фиксированной длины в графах ладьи

В отличие от многих других подходов к подсчету циклов, явные формулы [1], [4], [5], [6] позволяют свести определение числа циклов длины k к вычислению количества произвольных маршрутов длины не более k с фиксированными начальными и конечными вершинами. Подсчет маршрутов без ограничения на их структуру в виде различия вершин обычно оказывается более простой задачей по сравнению с определением самого количества циклов. В частности, при достаточно регулярной структуре графов некоторого параметризованного семейства удается аналитически выразить зависимость количества маршрутов от значения параметра. Воспользовавшись далее явными формулами, можно вывести выражение и для числа циклов. Возможность таких символьных вычислений отмечалась ранее в [3], однако подробно в литературе не освещалась.

Целью настоящей работы является демонстрация основных способов аналитического преобразования сумм, входящих в явные формулы. Все необходимые построения иллюстрируются на примере семейства графов ладьи, соответствующих доскам размера N × N .

ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ

Графом ладьи для доски размера N × N будем называть граф, вершины которого соответствуют клеткам доски, а ребра – парам клеток, таким что ладью можно переставить с одной клетки на другую за один ход. Определенный таким образом граф содержит N ² вершин, N ²( N – 1) ребер и является регулярным. Степень каждой вершины графа ладьи равна 2( N – 1).

Маршрутом длины k называется упорядоченный набор ( v ₁; v ₂;…; v_{k +1}) вершин графа, в котором каждые две соседние вершины v_i и v_{i +1} смежны. Маршрут длины не менее 3, для которого все вершины v ₁, v ₂, …, v_k различны, а v_{k +1} = v ₁, называется

циклом. При подсчете циклы, отличающиеся только выбором начальной вершины или направления обхода вершин, будут рассматриваться как один.

Количество циклов длины k обозначим символом c_k , а буквы n и A будем использовать для обозначения порядка (числа вершин) и матрицы смежности графа ладьи. Элементы матриц A и A^k записываются как a j и a j ) . Величина а^² равна степени вершины i и будет обозначаться символом d_i .

ЯВНЫЕ ФОРМУЛЫ ДЛЯ ПОДСЧЕТА ЦИКЛОВ

Явные формулы представляют собой комбинации сумм, члены которых являются произведениями элементов матрицы смежности и ее степеней. Например, количество циклов длин 3, 4, …, 7 в произвольном графе можно определить по следующим формулам [1], [2], [5], [6]:

c 4 = 1 1^ ) - 2 d i + d i ) , c 5 = 1 0 ? - 5^ ( d . — 1 ) ) ,

• ⁸    i = 1                                  ¹⁰ i = 1

n   nn

C 3 = 1 1 a (3 \ c 6 = 1 a^ * -1 z ( a (³⁾ ) 2 + 2 «4* ) ( d - 1 ) ) +

• ⁶    г = 1                ¹² г = 1         ⁴ г = 1

n                   nn

• + 1 t^ d. ⁽ d 2 — 3 d . + 1 ) - a ®) + 1 H^’ ) 2 a_y + a j ) , ⁽¹⁾

³ i = 1                                      ⁴ i = 1 j = 1

c 7 = r_A l a i⁷’ - 1 1(a i?¹ ( d . - 1 ) + a (3) ( a <⁴’ - 2 d . + 11 d . - 8 )) +

• ¹⁴ i = 1         ² i = 1

1 ^{n n} (2)       (2) ²        (3)                  (2)       (2) (3)

• ⁺ 31L \ ^a4 ^a .j ' a l ) ^{+ 3 a} j ⁺ d i d J ^{- 4 a} j ^{)+ a} .j a ll ) .

² i = 1 J = 1

Символьное преобразование выражений (1) для заданного параметризованного семейства графов возможно при наличии формул, описывающих зависимость величин a j ) от параметра семейства. В следующем разделе представлены такие формулы в случае графов ладьи.

ПОДСЧЕТ МАРШРУТОВ В ГРАФАХ ЛАДЬИ

Количество маршрутов длины k, соединяющих фиксированные вершины (клетки) i и j, в графе ладьи определяется одним из трех вариантов взаимного расположения i и j: клетки совпадают; клетки различны, но расположены в одном ряду доски; клетки расположены в разных рядах.

В случае i = j значение a j ) выражается следующей общей формулой.

Утверждение 1. Для всякого натурального k > 2

• 3 )    = N _ ( 2( N - 1)( N - 2) ^k + 2 ^k ( N - 1) ^k + ( - 2) ^k ( N - 1)² ) . (2)

Доказательство. Пусть W S (1 ),где S c {1;2;_; 1 }, - множество всех замкнутых маршрутов ладьи длины 1 с фиксированной начальной клеткой, в которых ходы с номерами из множества S выполняются в горизонтальном направлении, а остальные ходы - в вертикальном направлении. Тогда, очевидно, множество W S ( 1 ) равномощно произведению W ₀ (| S |) х W ₀ ( 1 — | S |) (весь маршрут разбивается на подпоследовательности из горизонтальных и вертикальных ходов), и

O k ) = 2 W s ( k )| = 2 W o (| s d| • W o ( k -i s d| =

S c{1;2;_; k}          S c{1;2;_; k} k (k\                   (3)

• = 2 1, !• W o ( i )l • W o ( k - 1 )|, 1 = 0 V ¹ )

если по определению считать, что | W ₀ (0)| = 1.

Обозначим величину |W0 (1 )|, равную количеству замкнутых маршрутов ладьи длины 1 с фиксированной начальной клеткой в одном ряду доски, символом f (1). Для небольших значений 1 = 0, 1, 2 имеем f (0) = 1, f (1) = 0, f (2) = N - 1,        (4)

а при 1 > 2 величину f ( 1 ) можно выразить через f (1 - 1). Для очередного хода ладьи существует N - 1 вариантов, а 1 -м ходом ладья сумеет попасть в начальную клетку, если только она не оказалась именно в этой клетке через 1 - 1 ход:

f (1) = (N - 1)1 -1 - f (1 - 1).(5)

Решение рекуррентного соотношения (5) с начальными условиями (4) описывается следующей явной формулой:

f (1) = 1 ((N -1)1 + (-1)1 (N -1))

N.

Подстановка (6) в (3) и упрощение результата дает искомую формулу (2).□

Выражение (2) позволяет сразу же вычислить путем подстановки в (1) любые суммы с одним индексом. В частности, данного соотношения достаточно для выражения величин c ₃, c ₄ и c ₅ через параметр N. Формулы же для c ₆ и c 7 помимо диагональных элементов d, _a ⁽³⁾ , a ⁽⁴⁾ , • ••, i ii ii

_a ⁽⁷) включают недиагональные элементы a W и a W. Значенияуказанныхэлементовпредставлены в' следующем утверждении.

Утверждение 2. Для различных клеток i и j т m [2,6(N - 2), если i и j расположены в разных рядах; ak д aj =^        2                                        (7)

• ^{J J} ^ N - 2, N , если i и j расположены в одном ряду.

Доказательство. Случай a j ². Если клетки i и j находятся в разных рядах доски, то первым ходом ладью необходимо переместить в один ряд с клеткой j , а вторым ходом - в саму клетку j. Для первого хода имеются две возможности: по горизонтали или по вертикали. В случае же, когда i и j находятся в одном ряду, то после первого хода ладья должна остаться в этом же ряду, но не попасть в саму клетку j. Количество вариантов осуществления такого хода равно N - 2, по числу клеток ряда, за исключением i и j.

Случай ау. Когда клетки i и j расположены в разных рядах доски, ладья после первого хода попадет в один ряд с j (2 варианта) или вновь окажется в разных рядах с j (2( N - 2) вариантов). В первом случае останется N - 2 возможности попасть в j за два хода, а во втором - только 2 способа. Общее количество маршрутов составляет 2 • ( N - 2) + 2( N - 2) • 2 = 6( N - 2). Если же клетки i и j расположены в одном ряду, то в результате первого хода будет иметь место одна из трех ситуаций: ладья находится в клетке j (1 вариант); в одном ряду с j, но не в самой клетке j ( N - 2 варианта); в разных рядах с j ( N - 1 вариант). Остается переместить ладью в клетку j за два хода: 1 • 2( N - 1) + ( N - 2) • ( N - 2) + ( N -1) • 2 = N ².       □

При вычислении двойных сумм непосредственной подстановкой выражений (2) и (7) в общий член суммы не обойтись, так как взаимное расположение вершин i и j меняется по мере того, как они независимо друг от друга пробегают всевозможные значения от 1 до n . Необходимо предварительно разбить область суммирования таким образом, чтобы в рамках каждой из подобластей сохранялось постоянное взаимное расположение вершин i и j, а следовательно, и значение общего члена суммы.

ВЫЧИСЛЕНИЕ ДВОЙНЫХ СУММ ДЛЯ ГРАФОВ ЛАДЬИ

В случае двух индексов возникают три подобласти суммирования в соответствии с вариантами взаимного расположения, перечисленными в предыдущем разделе.

Утверждение 3. Пусть f (i ; j ) - многочлен, составленный из величин a j ) , а f₀, f и f₂ - значения f (i; j ) на тех наборах индексов, для которых клетки i и j расположены в разных рядах (t = 0); в одном ряду, но различны (t = 1); совпадают (t = 2). Тогда nn

22 f ( i ; j ) = N ² • ( f , + 2( N - 1) f , + ( N - 1)² f 0 ) . (8) i = 1 j = 1

Доказательство. Для каждой клетки i насчитывается 2(N - 1) клеток, расположенных в одном горизонтальном или вертикальном ряду с i. Клетки же, не попадающие в один ряд с i, заполняют часть доски, получаемую вычеркиванием рядов, которые проходят через клетку i. Количество таких клеток равно (N – 1)2.      □

Применительно к суммам (1), за исключением последних слагаемых в формулах для c ₆ и c ₇, правило (8) существенно упрощается, так как благодаря наличию множителя a_ij всегда f ₂ = f ₀ = 0.

n n ~                    ~

Следствие. XX f(i; j)ay = 2N2(N - ^f • i =1 j=

ФОРМУЛЫ ДЛЯ КОЛИЧЕСТВА ЦИКЛОВ В ГРАФАХ ЛАДЬИ

На основе явных формул для подсчета циклов, используя соотношение (7) непосредственно, а также с применением правила (8), можно аналитически выразить зависимость величин c ₃, c ₄, …, c ₇ от параметра N для графов ладьи.

Утверждение 4. Количество циклов длин 3, 4, …, 7 в графах ладьи на доске N × N выражается формулами :

c 3 = 1’ c4 = 4 N 2( N — i)( N2 — 4 N + 5), c5 = F (N2 - 2N + 7), c6 = F (N + 2)(N2 + 2N -11)

• 5                         6                           (9)

c7 = F (N4 + 24N3 -133N2 +134N + 94), где F = N2(N -1)(N - 2).

Для случаев, когда значение длины цикла больше 7, представленного выше набора правил преобразования сумм недостаточно, поскольку в соответствующих явных формулах встречаются суммы кратности 4 и более [2], [3], [4]. Кроме того, увеличиваются степени матрицы смежности, недиагональные элементы которых участвуют в формулах. Однако идея разбиения областей суммирования обобщается на суммы произвольной кратности, а значения недиагональных элементов также могут быть вычислены в общем виде, наподобие (2). В частности, можно показать, что для графов ладьи значения всех сумм, участвующих в явных формулах, являются многочленами от N. Следовательно, в силу полиномиальности самих формул для ck зависимость величины ck от N в случае графов ладьи также всегда описывается многочленом от N. Общий способ разбиения сумм произвольной кратности предполагается детально рассмотреть в отдельной работе.

ЗАКЛЮЧЕНИЕ

Представленная в данной работе техника символьных вычислений по явным формулам не ограничена семейством графов ладьи и применима к разнообразным классам других графов с достаточно регулярной структурой. Основная ценность предложенного подхода к аналитическому подсчету циклов на основе явных формул состоит в том, что сами формулы уже «содержат» существенную информацию о числе циклов и остается лишь предоставить вспомогательные данные, получение которых не столь затруднительно по сравнению с выводом выражений для количества циклов из первых принципов.

* Работа выполнена при поддержке Программы стратегического развития (ПСР) ПетрГУ в рамках реализации комплекса мероприятий по развитию научно-исследовательской деятельности на 2012–2016 гг.