Drzewa spinające w grafie

Permutacje. Kombinacje. Wariacje. Rozmieszczanie kul w urnach. Silnie i symbole Newtona. Przeliczanie zbiorów. Funkcje tworzące. Teoria grafów.
kuba_g
Użytkownik
Użytkownik
Posty: 7
Rejestracja: 19 lis 2009, o 01:24
Płeć: Mężczyzna
Lokalizacja: sląsk

Drzewa spinające w grafie

Post autor: kuba_g » 29 cze 2011, o 17:40

Mam problem z zadaniem,

Z grafu pełnego \(\displaystyle{ K_{12}}\) usuwamy jedną krawędź, dowolną. Ile graf ma drzew spinających?

Nawet nie wiem od której strony ugryźć :/

Gość Specjalny
Gość Specjalny
Posty: 9834
Rejestracja: 18 gru 2007, o 03:54
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 90 razy
Pomógł: 2629 razy

Drzewa spinające w grafie

Post autor: » 2 lip 2011, o 11:06

Drzew spinających w \(\displaystyle{ K_n}\) jest \(\displaystyle{ n^{n-2}}\). Wszystkich krawędzi jest \(\displaystyle{ {n \choose 2}=\frac{n(n-1}{2}}\), a każda należy do tej samej ilości drzew spinających. Skoro więc każde drzewo ma \(\displaystyle{ n-1}\) krawędzi, to łączna ilość krawędzi we wszystkich drzewach to \(\displaystyle{ (n-1)n^{n-2}}\). Tak więc każda krawędź należy do:
\(\displaystyle{ \frac{(n-1)n^{n-2}}{\frac{n(n-1)}{2}}=2n^{n-3}}\)
drzew.
Jeśli więc usuniemy z grafu pełnego jedną krawędź, to odpadają nam wszystkie drzewa, które ją zawierały, musimy więc ich ilość odjąć od liczby wszystkich drzew. Tak więc odpowiedź to:
\(\displaystyle{ n^{n-2}-2n^{n-3}=(n-2)n^{n-3}}\)

Q.

ODPOWIEDZ