Strom (teória grafov): Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
obrazky |
|||
Riadok 41:
== Algoritmus hľadania stredu, priemeru a polomeru v grafe ==
Na označenie stromov ako špeciálnych grafov budeme používať označenie T = (V,H). Písmeno T z anglickej terminológie zo slova tree. V strome môžeme hľadať priemer, polomer a stred jednoduchšie ako u iných grafov.
**Ak máme daný strom, tak z neho vynecháme vrcholy stupňa 1 aj s hranami, ktoré s nimi sú spojené
Řádek 46 ⟶ 47:
**Nakoniec dostaneme jedinú hranu. V tomto prípade stred pozostáva z dvoch vrcholov, alebo dostaneme jediný vrchol, ktorý je stredom
**V prípade, že stredom je jeden vrchol, polomer je rovný počtu iterácii (koľkokrát sme vykonali proces odoberania vrcholov stupňa jedna
**Ak stred pozostáva z dvoch vrcholov, polomer je o jednotku väčší, ako počet iterácií<br />
Poznámka: Dole na obrázku je znázornený hore uvedený algoritmus na dvoch stromoch
[[Obrázok:Priklad.JPG|thumb|right]]
= Priklad 1 =
Řádek 56 ⟶ 59:
== Druhy počítačových topológií ==
'''kruhová topológia'''
[[Obrázok:kruhova_tops.JPG|thumb|right]]
*Táto počítačová topológia nepatri medzi stromy, lebo na základe vety o stromoch (strom je súvislí graf, ktorý neobsahuje kružnice) nevyhovuje mojím požiadavkám.
'''hviezdicová topológia'''
[[Obrázok:hviezdicova_top.JPG|thumb|right]]
*Táto topológia patrí medzi stromy, lebo neobsahuje žiadne kružnice.
*V tejto topológií vieme určiť aj stred a polomer stromu.
Řádek 64 ⟶ 69:
'''zbernicová topológia'''
[[Obrázok:zbernicova_top.JPG|thumb|right]]
*Pri tomto druhu topológie som narazil na jeden problém.
*Ak túto topológiu budem chápať takto ako je aj znázornená na obrázku tak tento druh nepatrí medzi stromy, pretože ak by sme si túto topológiu prepísali inač, tak by nám v tejto topológií vznikli kružnice, pretože v konečnom dôsledku každý vrchol je prepojený s každým (obrázok 1)
*Ale ak by sme do uzlov dali vrcholy, tak by nám vyšiel pekný a jednoduchý druh stromu (obrázok2), čo by aj zodpovedalo podmienkam pre môj projekt.
[[Obrázok:zbernicova_strom.JPG|thumb|right]]
[[Obrázok:zbernica_strom.JPG|thumb|right]]
== Využitie v praxi ==
[[Obrázok:dom.JPG|thumb|right]]
*Na vyššie uvedenom obrázku sme si ukázali, ako môžeme zapojiť počítače do siete. Vyberali sme si z jednotlivých druhov topológií. Nakoľko hviezdicová topológia nám vyšla, že je strom a jednoducho sa dajú pripájať nové počítače a iné zariadenia do siete, tak sme v našom konkrétnom príklade použili práve ju
*Nakoľko táto hviezdicová topológia nie je rozvinutá, ľahko sa dalo určiť, kde je stred
| |||