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źć :/
Drzewa spinające w grafie
-
- Użytkownik
- Posty: 9833
- Rejestracja: 18 gru 2007, o 03:54
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 90 razy
- Pomógł: 2632 razy
Drzewa spinające w grafie
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.
\(\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.