Ile drzew spinających ma graf

De Moon · Post autor: **De Moon** » 3 cze 2010, o 16:25

Połączmy wybrane wierzchołki grafów pełnych Km oraz Kn krawędzią. Ile drzew spinających ma otrzymany w ten sposób graf?

szatkus · Post autor: **szatkus** » 3 cze 2010, o 17:35

Graf pełny ma \(\displaystyle{ n^{n-2}}\) drzew rozpinających, jeśli połączymy te dwa drzewa więcej niż jedną krawędzią to dostaniemy cykl i nie będzie to już drzewem. Musimy więc wybrać tylko jedną krawędź, więc ten graf będzie miał \(\displaystyle{ n^{n-2}m^{m-2}k}\) drzew rozpinających, gdzie k to liczba dorysowanych krawędzi.

De Moon · Post autor: **De Moon** » 3 cze 2010, o 18:17

gdzie k to liczba dorysowanych krawędzi.

Można to jakoś inaczej wytłumaczyć czym jest k? Nie zrozumiałem tego fragmentu.

szatkus · Post autor: **szatkus** » 3 cze 2010, o 18:54

Połączmy wybrane wierzchołki grafów pełnych Km oraz Kn krawędzią.

Tak to zdanie jest ułożone, że nie zrozumiałem czy chodzi o utworzenie jednej krawędzi między tymi grafami czy kilku dlatego zabezpieczyłem się dopuszczając k krawędzi.