liczba dróg

waliant · Post autor: **waliant** » 26 sty 2015, o 21:01

ile jest wszystkich dróg długości \(\displaystyle{ 10}\) z \(\displaystyle{ v_1}\) do \(\displaystyle{ v_1}\) w grafie:

\(\displaystyle{ v_1-------v_2------v_3------v_4------v_5}\).

Moim zdaniem \(\displaystyle{ 41}\), czy to dobry wynik?

norwimaj · Post autor: **norwimaj** » 26 sty 2015, o 21:27

Dobry wynik.

waliant · Post autor: **waliant** » 26 sty 2015, o 21:32

a mogę jeszcze wiedzieć jakim sposobem to liczyłeś? Ja korzystałem z macierzy sąsiedztwa

norwimaj · Post autor: **norwimaj** » 26 sty 2015, o 21:45

Ja zrobiłem sobie tabelkę. W \(\displaystyle{ n}\)-tym wierszu i w \(\displaystyle{ i}\)-tej kolumnie wpisywałem liczbę dróg długości \(\displaystyle{ n}\) z wierzchołka \(\displaystyle{ v_1}\) do \(\displaystyle{ v_i.}\) Przy większej długości dróg też bym użył macierzy i potęgowania w czasie logarytmicznym.