подсчет путей в графе

[Yu_K]

Вот такой простенький граф c направленными ребрами



Требуется посчитать кол-во замкнутых путей, начинающихся и заканчивающихся в вершине 1,таких для которых каждое из ребер а1,а2,а3 содержалось бы ровно n раз, а каждое из ребер b1, b2, b3 содержалось бы ровно m раз. Всего длина пути 3*(n+m).

С какой стороны можно подойти к этой задаче?

[maxal]

Лобовое решение: составить взвешенную 3x3 матрицу смежности с символьными весами ребер $a_1, a_2, a_3, b_1, b_2, b_3$, возвести ее в степень $3(n+m)$ (используя жорданову форму) и, наконец, вычислить коэффициент при $(a_1 a_2 a_3)^n (b_1 b_2 b_3)^m$ в разложении элемента с индексами $(1,1)$ (который соответствует путям из вершины 1 в 1).

Добавлено спустя 1 час 13 минут 33 секунды:

Ответ получается такой:

$$\frac{m^2+n^2+mn}{(m+n)^2}\binom{m+n}{m}^3$$

[Yu_K]

Спасибо. Только вопрос - если у нас символьная матрица - то как быть с Жордановой формой?

[maxal]

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

[Yu_K]

Maxal, cпасибо - поздно благодарю - поскольку пропустил ваш ответ в свое время - я именно так и подходил к решению через рекурретные соотношения. А к символьной жордановой мне не удалось перейти - но попробую разобраться. Хотя я пытался ее найти решая системы вида A*J=J*D, A^2*J=J*D^2, A^3*J=J*D^3 и тд - здесь D - символьная диагональная матрица, A - исходная матрица, J - символьная матрица перехода.

И еще может можно как-то задать какие-нибудь комплексные коэффициенты матрицы и просто в Мапле или Маткаде возвести ее в степень, что бы все кроме нужных нам остались ненулевыми - а потом отнять от общего числа их кол-во и получить результат?

Быстро у Вас, конечно, ответ получился после моего первого вопроса - Добавлено спустя 1 час 13 минут 33 секунды.

[Yu_K]

maxal А если граф представлен большим числом путей - например по 5 каждых $a_i$, $b_i$ то формула преобразуется к следующей

$$\frac{m^4+n^4+m^3n+n^3m}{(m+n)^4}\binom{m+n}{m}^5$$

?

По крайней мере при суммировании по $m=0..10$ и (при $n=10-m$) ответ в задаче, которую решал получился правильный при использовании этой формулы. Хотя строго получить вывод такого выше приведенного выражения у меня не получилось.

[maxal]

Вот здесь есть формальный вывод формулы для 3-х вершин:
http://mathoverflow.net/questions/29829 ... c-identity
Возможно, он обобщается на большее число вершин.