Z ilu drzew sklada sie ten las? (Grafy)

[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 ;/

[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\)

[Matematyk_Hais]

@arksoftware
Jestes pewny ze graf spojny bez cykli: |V| = |E| + 1?????
To jest niemozliwe

[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.

[Matematyk_Hais]

@arksoftware
Dobra dzięki wielkie za pomoc, rozumiem wszystko, wtedy cos mi sie pomieszało z wzorami.