1. Wyznacz liczbę drzew mających n wierzchołków, w którym dany wierzchołek jest wierzchołkiem wiszącym.
2. Wyznacz liczbę drzew mających n wierzchołków, w którym wierzchołek n ma stopnień n-2.
Przeliczanie grafów
-
UNIX_admin
- Użytkownik
- Posty: 185
- Rejestracja: 6 maja 2006, o 14:24
- Płeć: Mężczyzna
- Lokalizacja: Warszawa
- Pomógł: 32 razy
Przeliczanie grafów
jak wiadomo wszystkich drzew na n wierzcholkach jest \(\displaystyle{ n^{n-2}}\)
Ad. 1.
\(\displaystyle{ (n-1)(n-1)^{n-3}}\) czyli \(\displaystyle{ (n-1)^{n-2}}\)
Ad. 2.
\(\displaystyle{ n(n-1)(n-2)}\) jesli dowolny wierzcholek moze miec stopien n-2
lub \(\displaystyle{ (n-1)(n-2)}\) jesli konkretny wierzcholek ma miec stopien n-2
Ad. 1.
\(\displaystyle{ (n-1)(n-1)^{n-3}}\) czyli \(\displaystyle{ (n-1)^{n-2}}\)
Ad. 2.
\(\displaystyle{ n(n-1)(n-2)}\) jesli dowolny wierzcholek moze miec stopien n-2
lub \(\displaystyle{ (n-1)(n-2)}\) jesli konkretny wierzcholek ma miec stopien n-2