Kostra grafu: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
d Robot nahradil entity |
d Robot odstránil zbytočné zalomenie riadku |
||
Riadok 10:
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:Vvzorec2.JPG]] 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<br />
Každé dva vrcholy z G sú spojené práve jednou cestou (jednoznačnosť cesty).<br />
Riadok 21:
(c) T má |V| = n vrcholov,<br />
(d) T má n-1 hrán.<br />
* 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í: [[Súbor:Vzorec3.JPG]]
== Výpočet kostier grafu pomocou maticového vyjadrenia kostier ==
* Veta: Nech A je matica incidencie a C matica kružníc grafu g=(V,H). Potom platí <math>A.C^T=R</math>, kde R=(r<sub>ij</sub>)a prvky r<sub>ij</sub> matice R sú nezáporné celočíselné násobky čísla 2.
Dôkaz: Označme súčin matíc <math>A.C^T=R</math>, kde R=(r<sub>ij</sub>). Potom je [[Súbor:Vzorec4.JPG]] Nech G=(V,H), |V|=n, je súvislý graf. Nech B je matica susednosti a D je diagonálna matica s prvkami[[Súbor:Vzorec5.JPG]]grafu G. Označme D<sub>i</sub>-B<sub>i</sub> 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[[Súbor:Vzorec6.JPG]] <br />
Potom pre počet p(T) všetkých rôznych kostier grafu G platí p(T)=det(D<sub>i</sub>-B<sub>i</sub>), pre ľubovoľné [[Súbor:Vzorec7.JPG]]
Riadok 32:
* Ľubovolný [[strom (graf)|strom]] má jedinú kostru – sám seba.
* [[Úplný graf]] na ''n'' vrcholoch má práve <math>n^{n-2}</math> rôznych kostier (tzv. [[Cayleyho vzorec]]).
* Skúmanie hlavného topologického prepojenia siete internet na Slovensku.
Čí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.<br />
[[Súbor:Graf.JPG]]<br />
| |||