Mamy zbior wierzcholkow o nr {1,2,3,...,10}
Ile drzew na tym zbiorze wierzcholkow mozna utworzyc jesli jest dokladnie jeden wierzcholek stopnia 6 i wierzcholek o numerze 7 jest stopnia 3?
Myslalem zeby kombinowac cos z kodem Prufera. Ze wierzcholek stopnia 6 wystepuje w tym kodzie 5 razy, wierzcholek stopnia 3 wystepuje 2 razy. Laczna dlugosc kodu to 10-2=8.Czyli 5+2=7 czyli jest jeszcze jeden wierzcholek stopnia 2, a reszta wierzcholkow ma stopnie 1. Ze najpierw trzeba wybrac wierzcholek o stopniu 6. Wierzcholek nr 7 jest juz ustalony. Trzeba wybrac jeden wierzcholek o stopniu 2 i reszte o stopniu 1. Tylko nie wiem jak to zapisac.
Ilosc drzew na zbiorze wierzcholkow
-
- Użytkownik
- Posty: 1384
- Rejestracja: 26 lis 2006, o 21:34
- Płeć: Mężczyzna
- Lokalizacja: Poznań
- Podziękował: 33 razy
- Pomógł: 268 razy
Ilosc drzew na zbiorze wierzcholkow
Najpierw wybierasz wierzchołek o stopniu 6 na 9 sposobów co jest oczywiste..
Kolejnym krokiem jest rozdzielenie na dwa przypadki:
1. Wierzchołek nr 7 łączy się z wierzchołkiem o stopniu 6;
2. Wierzchołek nr 7 nie łączy się z owym wierzchołkiem.
Oba przypadki są rozłączne więc zsumujemy tylko liczby utworzonych grafów.
ad 1. Wybieramy 6 wierzchołków połączonych z wierzchołkiem o stopniu 6 (jednym jest wierzchołek nr 7) na \(\displaystyle{ {8 \choose 5}}\) sposobów. W ten sposób mamy odpalone 7 wierzchołków. Pozostały nam 3.. Z nich musimy wybrać 2 łączące się z wierzchołkiem nr 7 oczywiście na \(\displaystyle{ {3 \choose 2}}\) sposobów oraz wybieramy wierzchołek z którym połączy się ostatni wierzchołek na 7 sposobów (wierzchołki nr 7 oraz stopnia 6 nie mogą zostać wybrane).
ad 2. Wybieramy 6 wierzchołków połączonych z wierzchołkiem o stopniu 6 (żadnym z nich nie jest wierzchołek nr 7) na \(\displaystyle{ {8 \choose 6}}\) sposobów. Kolejnym krokiem jest wybór wierzchołka do którego przyłączymy wierzchołek nr 7 na 6 sposobów. Pozostałe dwa wierzchołki przyłączamy do wierzchołka nr 7.
Podsumowując: Liczba utworzonych grafów to:
\(\displaystyle{ 9 \cdot {8 \choose 5} \cdot {3 \choose 2} \cdot 7 + 9 \cdot {8 \choose 6} \cdot 6}\)
Można sobie policzyć.. Liczba nie wyjdzie taka ogromna.. Niemniej w tej formie chyba wystarczy.
Kolejnym krokiem jest rozdzielenie na dwa przypadki:
1. Wierzchołek nr 7 łączy się z wierzchołkiem o stopniu 6;
2. Wierzchołek nr 7 nie łączy się z owym wierzchołkiem.
Oba przypadki są rozłączne więc zsumujemy tylko liczby utworzonych grafów.
ad 1. Wybieramy 6 wierzchołków połączonych z wierzchołkiem o stopniu 6 (jednym jest wierzchołek nr 7) na \(\displaystyle{ {8 \choose 5}}\) sposobów. W ten sposób mamy odpalone 7 wierzchołków. Pozostały nam 3.. Z nich musimy wybrać 2 łączące się z wierzchołkiem nr 7 oczywiście na \(\displaystyle{ {3 \choose 2}}\) sposobów oraz wybieramy wierzchołek z którym połączy się ostatni wierzchołek na 7 sposobów (wierzchołki nr 7 oraz stopnia 6 nie mogą zostać wybrane).
ad 2. Wybieramy 6 wierzchołków połączonych z wierzchołkiem o stopniu 6 (żadnym z nich nie jest wierzchołek nr 7) na \(\displaystyle{ {8 \choose 6}}\) sposobów. Kolejnym krokiem jest wybór wierzchołka do którego przyłączymy wierzchołek nr 7 na 6 sposobów. Pozostałe dwa wierzchołki przyłączamy do wierzchołka nr 7.
Podsumowując: Liczba utworzonych grafów to:
\(\displaystyle{ 9 \cdot {8 \choose 5} \cdot {3 \choose 2} \cdot 7 + 9 \cdot {8 \choose 6} \cdot 6}\)
Można sobie policzyć.. Liczba nie wyjdzie taka ogromna.. Niemniej w tej formie chyba wystarczy.