Форум программистов [Powered by Invision Power Board]

Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > Центр помощи > [ДескрМат] матрицы смежностей

Автор: KatrinIceLand 20.2.2008, 19:47

Объясните мне пожалуйста (до меня никак не доходит smile

) когда считаем число возможных путей (paths) используя матрицу смежности надо умножать или возводить в степень или как это число высчитывается (почему 0 = 8).

Например, (пример из книги):

дана матрица: (a,b,c,d)
                         0110
                         1001
                         1001
                         0110
Значит число возможных путей длинной 4 от a до d равно:

        8008
А4    0880
        0880
        8008

Значит 8 путей возможных. Как это считается? И какую роль играют данный вершины (a,d) будет ли разница если данные точки будут другими или вообще не будут указаны?
Представляю насколько это элементарно, но мне нужно объяснение   smile

Автор: devyshko 20.2.2008, 20:29

Ну даж не знаю как тут получили 8 путей. Как по мне, то их тут два smile

. Нарисовала по матрице граф и посчитала.

Автор: KatrinIceLand 20.2.2008, 20:46

Цитата(devyshko @ 20.2.2008, 20:29

)

Как по мне, то их тут два. Нарисовала по матрице граф и посчитала

Нет, в книге все правильно, даже если по графу считать, все равно 8 получается: e.g. {a,b,a,b,d}, {a,b,a,c,d}, {a,b,d,c,d}, {a,c,a,b,d} ну и так далее, в общем 8.

Но как по матрице считать, ведь граф на экзамене будет совсем не так прост. Надо понять как по матрице считать smile

Автор: devyshko 20.2.2008, 21:56

Нас учили так! В начальную точку возвращаться нельзя и из конечной тоже. А тут все эти правила нарушены smile

любопытно

Автор: KatrinIceLand 21.2.2008, 14:52

Цитата(devyshko @ 20.2.2008, 21:56

)

Нас учили так! В начальную точку возвращаться нельзя и из конечной тоже

Если вершины не повторяются в "пути", то это простой "путь", а если повторяются, то сложный. Ну во всяком случае по английски это звучит так:
Simple path and not simple path if repits its vertices.

Странно, я думала это очень просто, но никто не может объяснить smile

Автор: KatrinIceLand 25.2.2008, 14:12

А вот конкретное задание:

дана матрица:

   R  S  T  U
R 0  0  3  2
S 0  0  1  0
T 3  1  0  4
U 2  0  4  0

Посчитать сколько макс возможных путей длинной 3 между S and U используя матрицу.

Помогите, не понимаю как решать   smile