Ilosc drzew na zbiorze wierzcholkow

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Leiton
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 14 maja 2013, o 00:51
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 2 razy

Ilosc drzew na zbiorze wierzcholkow

Post autor: Leiton »

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.
mostostalek
Użytkownik
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

Post autor: mostostalek »

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.
Leiton
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 14 maja 2013, o 00:51
Płeć: Mężczyzna
Lokalizacja: Poznań
Podziękował: 2 razy

Ilosc drzew na zbiorze wierzcholkow

Post autor: Leiton »

Dziękuję bardzo!!
ODPOWIEDZ