Элементы теории графов

Question

Элементы теории графов

Ярослав Кудряшов Ученик (103), открыт 1 день назад

На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город З?

объясните пожалуйста как это делать я не врубаюсь

Answer 1

строишь матрицу для этого направленного графа...
перемножаешь её несколько раз...
смотришь сколько получилось в элементе отвечающем за соединение конкретных двух точек...
ответ будет 13

W в первой и второй степенях можно откинуть... потому как нет путей такой длины между заданными точками...
а вот для длин 3, 4 и 5 такие пути имеются... вот в сумме 13 и получится...