2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 подсчет путей в графе
Сообщение03.11.2008, 15:16 
Вот такой простенький граф c направленными ребрами

Изображение

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

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

 
 
 
 
Сообщение04.11.2008, 00:35 
Аватара пользователя
Лобовое решение: составить взвешенную 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$$

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

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

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

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

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

 
 
 
 Re:
Сообщение20.09.2010, 18:55 
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$) ответ в задаче, которую решал получился правильный при использовании этой формулы. Хотя строго получить вывод такого выше приведенного выражения у меня не получилось. :-)

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

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group