szukanie zaawansowane
 [ Posty: 2 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 30 lip 2016, o 11:00 
Użytkownik

Posty: 5640
Lokalizacja: Kraków
Ile drzew spinających ma graf K_{2 \ n} a ile K_{3 \ n} ?
Góra
Mężczyzna Offline
PostNapisane: 2 sie 2016, o 00:36 
Użytkownik

Posty: 1088
Lokalizacja: Lublin/Warszawa
Każdy wierzchołek z prawej strony, liczącej n wierzchołków musi być połączony z którymś z lewej. Gdyby każdy wierzchołek spośród tych z prawej strony był połączony z jednym z lewej to mielibyśmy dwa drzewa, dlatego dokładnie jeden z prawej musi być połączony z oboma z drugiej strony (można go wybrać na n sposobów). Reszta musi być połączona z dowolnym spośród dwóch z lewej.
Dlatego K_{2 , n} ma n  \cdot 2^{n - 1} drzew rozpinających.
K_{3, n} analogicznie.
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 2 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Cykle w grafie  phnxck  0
 Odległość między liśćmi drzewa  rubik1990  1
 drzewa które są..  robsel  2
 Ścieżka w grafie  bartek1801  1
 Drzewa - stopnie  ucaps  2
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl