Kostra (červene) grafu (čierne)

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

• 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 T₁, T₂, …, T_p s počtom vrcholov n₁, n₂, …., n_p. Každý komponent T_i je súvislý graf bez kružníc, a preto má práve n_i hrán. Celkove máme

${\displaystyle |V|-1=\sum _{i=1}^{p}(n_{i}-1)=\sum _{i=1}^{p}n_{i}-p\leq |V|-p}$

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 ${\displaystyle \sum _{i=1}^{p}n_{i}=|V|}$ 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í: ${\displaystyle c_{ij}=\left\{{\begin{array}{cc}1&h_{j}\in c_{i}\\0&h_{j}\not \in c_{i}\end{array}}\right.}$

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í ${\displaystyle A.C^{T}=R}$, kde R=(r_ij)a prvky r_ij matice R sú nezáporné celočíselné násobky čísla 2.

Dôkaz: Označme súčin matíc ${\displaystyle A.C^{T}=R}$, kde R=(r_ij). Potom je ${\displaystyle r_{ii}=\sum _{k=1}^{|H|}a_{ik}\cdot c_{kj}^{T}=\sum _{k=1}^{|H|}a_{ik}\cdot c_{jk}}$ Nech G=(V,H), |V|=n, je súvislý graf. Nech B je matica susednosti a D je diagonálna matica s prvkami ${\displaystyle d_{ii}=\delta (v_{i})}$ grafu G. Označme D_i-B_i 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 ${\displaystyle (1\leq i\leq n)}$
Potom pre počet p(T) všetkých rôznych kostier grafu G platí p(T)=det(D_i-B_i), pre ľubovoľné ${\displaystyle i,i\in \{1,2,\ldots ,n\}}$

Príklady

• Kružnica na n vrcholoch (graf ${\displaystyle C_{n}}$) má práve n rôznych kostier.
• Ľubovolný strom má jedinú kostru – sám seba.
• Úplný graf na n vrcholoch má práve ${\displaystyle n^{n-2}}$ 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.

Zdroj:
Text je dostupný za podmienok Creative Commons Attribution/Share-Alike License 3.0 Unported; prípadne za ďalších podmienok. Podrobnejšie informácie nájdete na stránke Podmienky použitia.