Matematické Fórum

Acykický graf se skládá z k stromů, pro i-tý strom , kde je počet jeho hran a počet jeho vrcholů. Sečtením přes všechna i máme m=n-k. To nám dává odpověď na obě otázky.

↑ hanzx88:
jj ;-)

1) Acyklický graf je graf neobsahující kružnici.
2) Každý graf se skládá z komponent.
3) Každá komponenta grafu je souvislá.
4) Každá komponenta acyklického grafu je navíc acyklická.
5) Acyklický souvislý graf se nazývá strom.
6) Všechny komponenty acyklického grafu jsou stromy.
7) Počet komponent v daném acyklickém grafu označme k.
8) Strom je rovinný graf.
9) Hrany stromu neohraničují žádnou plochu.
10) Pro rovinné grafy platí Eulerův vzorec F-E+V=1 (F počet ploch, E hran, V vrcholů)
11) Pro stromy tedy platí 0-E+V=1.
12) Pro strom platí, že počet jeho vrcholů je o 1 větší, než počet hran.
13) Pro i-tou komponentu daného acyklického grafu , kde je počet jejích hran a počet jejích vrcholů.
14) Předchozí vztah lze formálně sečíst přes všechna i od 1 do k .
15) Vyčíslením sum .
16) Proto k=n-m (odpověď na druhou otázku)
17) Tudíž k>1 právě když n-m>1
18) Graf je nesouvislý právě když k>1
19) Graf je nesouvislý, právě když n-m>1 (odpověď na první otázku)

Pokud i nyní máte nejasnosti, napište prosím u kterých vět.