[grafy]składowe i kod Prufera

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
Bronia
Użytkownik
Użytkownik
Posty: 11
Rejestracja: 19 cze 2007, o 21:41
Płeć: Kobieta
Lokalizacja: Poznań
Podziękował: 2 razy

[grafy]składowe i kod Prufera

Post autor: Bronia » 18 paź 2007, o 19:07

Mam dwa zadania z teorii grafów, na które nie mogę nigdzie znaleźć odpowiedzi.
1. Jaka jest najmniejsza i największa liczba składowych grafu, który ma 25 wierzchołków i 20 krawędzi?
2. Ile jest drzew izomorficznych o kodzie Prufera [2,1,1,1,5,2]? Wiem, że w rozwiązaniu pojawiają się permutacje, ale nie wiem, skąd one się biorą.
Z góry dziękuję za pomoc!
Rekrutacja Instytut Matematyczny, Uniwersytet Wrocławski (gif)

ODPOWIEDZ