Verzia z 13:53, 5. máj 2009 upraviť JagRoBot (diskusia \| príspevky) Boti 6 959 editací d Robot odstránil zbytočné zalomenie riadku ← Predchádzajúca úprava		Verzia z 18:29, 14. júl 2009 upraviť vrátiť Kilom691 (diskusia \| príspevky) 2 editace →‎Výpočet kostier grafu pomocou maticového vyjadrenia kostier: math is better than image Ďalšia úprava →
Riadok 26: == 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]]~~ <math>(1 \leq i \leq n)</math> <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]] == Príklady == * [[Kružnica (graf)\|Kružnica]] na ''n'' vrcholoch (graf <math>C_n</math>) má práve ''n'' rôznych kostier.

Kostra grafu: Rozdiel medzi revíziami