Kostra grafu: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
d robot Pridal: cs:Kostra grafu |
obrázok |
||
Riadok 1:
{{Na rozšírenie}}
[[Obrázok:Spanning tree.svg|thumb|Kostra (červene) grafu (čierne)]]
'''Kostra grafu''' G je taký jeho [[faktor grafu|faktor]], ktorý neobsahuje [[kružnica (graf)|kružnice]].
'''KOSTRA GRAFU'''
Kostra grafu je taká podmnožina T hrán grafu G, že platí: Medzi každými 2 vrcholmi grafu existuje cesta využívajúca len hrany kostry T. Odobratím ľubovoľnej hrany kostry už vlastnosť nebude platiť.
„''Kostra''“ sú hrany, ktoré graf „držia po kope“.
== Definície ==
* 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.bmp]]<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.bmp]] 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 />
Každé dva vrcholy z G sú spojené práve jednou cestou (jednoznačnosť cesty).<br />
G je súvislý a po odobraní ľubovoľnej hrany sa stane nesúvislým (minimálna súvislosť).<br />
G neobsahuje kružnicu, ale po pridaní ľubovoľnej hrany vznikne v G kružnica (maximálny graf bez kružníc) .<br />
G je súvislý a |V|=|E|+1, kde V je množina vrcholov a E množina hrán grafu G.<br />
Ak zamyslíme nad tvrdením vety a definíciou stromu, tak zistíme, že ľubovoľné tri z nasledujúcich štyroch vlastností implikujú už štvrtú vlastnosť: <br />
(a) T je súvislý graf,<br />
(b) T neobsahuje kružnice,<br />
(c) T má |V| = n vrcholov,<br />
(d) T má n-1 hrán.<br />
* Maticové vyjadrenie kostier<br />
Nech G=(V,H) je graf, H={h1,h2, …, hn}. Nech C1,C2, ...,Cm sú všetky kružnice grafu G. Matica kružníc grafu G je matica C=(cij) typu (m,n), ak pre jej prvky platí: [[Súbor:vzorec3.bmp]]
== Príklady ==
* [[Kružnica (graf)|Kružnica]] na ''n'' vrcholoch (graf <math>C_n</math>) má práve ''n'' rôznych kostier.
Řádek 51 ⟶ 70:
[[vi:Cây bao trùm]]
[[zh:最小生成树]]
<gallery>
Obrázok:Príklad.jpg|Popis
Obrázok:Príklad.jpg|Popis2
</gallery>
| |||