Verzia z 00:38, 13. december 2008 upraviť Frantisekhajdokk (diskusia \| príspevky) 8 editací Bez shrnutí editace ← Predchádzajúca úprava		Verzia z 00:42, 13. december 2008 upraviť vrátiť Frantisekhajdokk (diskusia \| príspevky) 8 editací Bez shrnutí editace Ďalšia úprava →
Riadok 11: * Veta: Nech G=(V,H) je súvislý graf a T je jeho podgraf s \|V\|-1 hranami neobsahujúce kružnice. Potom T je kostra grafu G.<br /> * Dôkaz: Nevieme, či T je súvislý, preto predpokladajme, že T je vytvorený komponentmi T1, T2, …, Tp s počtom vrcholov n1, n2, …., np. Každý komponent Ti je súvislý graf bez kružníc, a preto má práve ni hrán. Celkove máme[[Súbor:vzorec.jpg]]<br /> Posledná nerovnosť vyplýva z úvahy, že T nemusí byť faktorom grafu G. Podľa predpokladu je, takže môže byť iba p=1, a teda[[Súbor:~~Vzorec2~~vvzorec2.jpg]] Preto graf T je súvislý podgraf grafu G a neobsahuje kružnice, je strom, teda je kostrou grafu G.<br /> * Strom možno definovať:<br /> G je strom<br />

Kostra grafu: Rozdiel medzi revíziami