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

Posty: 5597
Lokalizacja: Kraków
Ile drzew spinających ma graf K_{2 \ n} a ile K_{3 \ n} ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 2 sie 2016, o 00:36 
Użytkownik

Posty: 1086
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 
 Droga prosta w grafie  rubik1990  0
 Znajdowanie wszystkich rozcięć w grafie spójnym.  pablov  1
 Podgraf dwudzielny w grafie  ucaps  1
 Spójność w grafie  Summum Malum  8
 Cykl hamiltona w grafie o 6 wierzchołkach  gardner  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl