Strona 1 z 1
Z ilu drzew sklada sie ten las? (Grafy)
: 16 cze 2016, 16:53
autor: Matematyk_Hais
Witam,
Mam takie zadanie: Z ilu drzew sklada sie las majacy 2015 wierzcholkow i 2000 krawedzi?
Kurcze nie wiem za bardzo jak to zrobic, kombinuje takie cos:
Drzewo to graf spojny bez cykli. Las to graf, ktorego skladowe spojne sa drzewami.
Graf spojny bez cykli: |V| = |E| - 1
W moim przypadku: |V| = 2015, |E| = 2000
Nie wiem jak to rozwiazac ;/
: 16 cze 2016, 17:09
autor: arksoftware
To nieprawda, że w drzewie \(|V| = |E| - 1\). Prawdą jest za to, że \(|V| = |E| + 1\). V - vertex - wierzchołek, E- edge - krawędź.
Wracając do zadania:
Oznaczmy przez n liczbę drzew, a przez \(|V_i|, |E_i|\) odpowiednio liczbę wierzchołków i krawędzi w i-tym drzewie.
\(2015 = \sum_{i=1}^{n}|V_i| = \sum_{i=1}^{n} (|E_i| + 1) = \sum_{i=1}^{n} |E_i| + n = 2000 + n\)
\(2015 = 2000 + n\)
\(n = 15\)
: 16 cze 2016, 17:34
autor: Matematyk_Hais
@arksoftware
Jestes pewny ze graf spojny bez cykli: |V| = |E| + 1?????
To jest niemozliwe
: 17 cze 2016, 09:27
autor: arksoftware
Dlaczego niemożliwe?
Wzór można łatwo udowodnić przez indukcję. Wyobraź sobie najprostsze drzewo: 1 wierzchołek i 0 krawędzi. Wzór zachodzi.
Kolejny przykład: 2 wierzhołki i 1 krawędź, która je łączy.
Teraz wyobraź sobie dowolne drzewo. Dodajemy do niego jeden wierzhołek. Aby to nadal było drzewo, trzeba ten wierzchołek połączyć jedną krawędzią z dowolnym innym wierzchołkiem.
Mówimy oczywiście o drzewie nieskierowanym, a przez V oznaczamy zbiór wierzchołków, a przez E zbiór krawędzi.
: 17 cze 2016, 20:38
autor: Matematyk_Hais
@arksoftware
Dobra dzięki wielkie za pomoc, rozumiem wszystko, wtedy cos mi sie pomieszało z wzorami.