Liczba różnych drzew DFS

[matinf]

Dany jest graf. Ten graf to drabina. Powiemy, że drabina jest rzędu \(\displaystyle{ n}\) - zobaczcie na ilustrację.

AU

aU2hY.png (2.71 KiB) Przejrzano 82 razy

Uruchamiamy DFS na węźle \(\displaystyle{ 1}\). Ile istnieje różnych drzew DFS ?
\(\displaystyle{ 2}\) przypadki:

dla węzła \(\displaystyle{ 1}\): \(\displaystyle{ 1\to 2\to 4}\)

Zaczynając z węzła \(\displaystyle{ 4}\), otrzymujemy przejście DFSem na drabinie rzędu \(\displaystyle{ n−1}\) \(\displaystyle{ 2$: 1\to 3}\)

Powstaje rekursja :
\(\displaystyle{ T_{1} = 1}\)
\(\displaystyle{ T_n = T_{n-1} + T_{n-1} = 2^{n-1}}\)


Czy jest ok ?

[MatXXX]

Potwierdzam. Inne rozwiązanie to chociażby powiedzenie, że możemy "zejść" jeden poziom niżej na drabinie na dokładnie \(\displaystyle{ 2}\) sposoby: na dół oraz w bok i na dół. Po dotarciu do pewnego wierzchołka, jeżeli w drzewie DFS istniałaby gałąź idąca po elementach wyżej na drabinie, to byłaby ona dokładnie jedna (co wynika z tego, jak zbudowana jest drabina) A poziomów trzeba pokonać \(\displaystyle{ n-1}\), więc odpowiedź \(\displaystyle{ 2^{n-1}}\) potwierdzona.

[matinf]

Dzięki wielkie