Kostra grafu
V teórii grafov je kostra grafu takým podgrafom grafu G na množine všetkých jeho vrcholov (súčasťou kostry grafu G musia byť všetky vrcholy grafu G), pre ktorý platí, že medzi každými dvoma vrcholmi existuje práve jedna cesta. Ináč povedané, kostra je graf, ktorý získame z pôvodného grafu G postupným rušením takých hrán, ktorých odstránením sa nenaruší súvislosť grafu. Hneď ako už neexistuje žiadna hrana, ktorú by sme mohli odstrániť, získaný graf je kostrou pôvodného grafu G. „Kostra“ je teda akýmsi hranovým minimom potrebným na to, aby graf „držal po kope“.
Definície
upraviť- Veta: Nech G=(V,H) je súvislý graf a T je jeho podgraf s |V|-1 hranami neobsahujúci kružnice. Potom T je kostra grafu G.
- 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
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 Preto graf T je súvislý podgraf grafu G a neobsahuje kružnice, je strom, teda je kostrou grafu G.
- Strom možno definovať:
G je strom
Každé dva vrcholy z G sú spojené práve jednou cestou (jednoznačnosť cesty).
G je súvislý a po odobraní ľubovoľnej hrany sa stane nesúvislým (minimálna súvislosť).
G neobsahuje kružnicu, ale po pridaní ľubovoľnej hrany vznikne v G kružnica (maximálny graf bez kružníc) .
G je súvislý a |V|=|E|+1, kde V je množina vrcholov a E množina hrán grafu G.
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ť:
(a) T je súvislý graf,
(b) T neobsahuje kružnice,
(c) T má |V| = n vrcholov,
(d) T má n-1 hrán.
- Maticové vyjadrenie kostier
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í:
Výpočet kostier grafu pomocou maticového vyjadrenia kostier
upraviť- Veta: Nech A je matica incidencie a C matica kružníc grafu g=(V,H). Potom platí , kde R=(rij)a prvky rij matice R sú nezáporné celočíselné násobky čísla 2.
Dôkaz: Označme súčin matíc , kde R=(rij). Potom je Nech G=(V,H), |V|=n, je súvislý graf. Nech B je matica susednosti a D je diagonálna matica s prvkami grafu G. Označme Di-Bi maticu rádu n-1, ktorú sme vytvorili z matice D-B vynechaním jej i-tého riadku a i-tého stĺpca
Potom pre počet p(T) všetkých rôznych kostier grafu G platí p(T)=det(Di-Bi), pre ľubovoľné
Príklady
upraviť- Kružnica na n vrcholoch (graf ) má práve n rôznych kostier.
- Ľubovolný strom má jedinú kostru – sám seba.
- Úplný graf na n vrcholoch má práve rôznych kostier (tzv. Cayleyho vzorec).
- Skúmanie hlavného topologického prepojenia siete internet na Slovensku.Graf upravíme tak aby obsahoval hlavné uzly a hlavné prepojenia(10 Gb/s) v rámci Slovenska a aby bol súvislý.
Čím viac kostier obsahuje graf(topológia), tým väčšia je prepojenosť medzi bodmi(uzlami) a tým lepšie je zabezpečená voči výpadkom spojenia v sieti.
Determinant (Di-Bi)=249
Po vypočítaní determinantu sem dostali číslo ktoré značí koľko priamych ciest(prepojení) existuje medzi ľubovoľnými dvoma bodmi(uzlami) . Ak vypočítame kostru úplného grafu, tak dostaneme číslo 2 357 947 691 a to je oveľa väčšie číslo.
Počet priamych prepojení medzi dvoma uzlami predstavuje cestu dátového toku, ktoré prúdi medzi týmito dvoma uzlami. Keď medzi dvoma uzlami je viac prepojení tak rýchlosť prepojenia uzlov sa zvyšuje proporcionálne s narastajúcimi prepojeniami.
Záver:
Ak všimneme rozdiel medzi počtom kostier grafu ktorého sme skúmali a jeho úplným grafom, tak zistíme že daná internetová sieť, ktorá predstavuje náš graf sa môže ešte zdokonaľovať a aj by sa mal. Bezpečnosť proti výpadkov podľa danej topológie je nízka, lebo môžu nastať prípady kedy sa znefunkčnia dve prepojenia a nastáva výpadok internetu, ale zato pravdepodobnosť, aby sa znefunkčnili dve prepojenia v danom okamihu je veľmi malá. Pri rozširovaní prepojení medzi uzlami sa zvyšuje aj rýchlosť internetu a odolnosť voči výpadkom.
Algoritmy pre hľadanie kostry
upraviťĽubovolná kostra
upraviťNasledujúci základný algoritmus je schopný nájsť nejakú (bližšie neurčenú) kostru:
- Nech je graf s n vrcholmi a m hranami; zoraďme hrany G ľubovolne do postupnosti ; položme .
- Ak už bola nájdená množina , spočítame množinu takto:
- ∪ { }, ake neobsahuje graf (V, ∪ ) kružnicu,
- inak.
- Algoritmus sa zastaví, ak buď už obsahuje n − 1 hran alebo i = m, teda sa prebrali všetky hrany z G. Graf potom predstavuje kostru grafu G.
Referencie
upraviť- Jiří Matoušek, Jaroslav Nešetřil: Kapitoly z diskrétní matematiky, nakladatelství Karolinum, Praha 2002, ISBN 80-246-0084-6
- Jakub Černý: Základní grafové algoritmy Archivované 2007-10-18 na Wayback Machine (texty v pdf)
- Diskrétna matematika – Doc. RNDr. Michal Bučko, CSc. – RNDr. Marián Klešč
Pozri aj
upraviťExterné odkazy
upraviť- Kruskalův algoritmus- animace a příklady, Bc. práce z MFF UK
- Tento článok je čiastočný alebo úplný preklad článku Kostra grafu na českej Wikipédii (číslo revízie nebolo určené).
- http://ics.upjs.sk/~galcik/files/progLS2008/grafy.ppt