Kostra grafu: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
obrázok |
Bez shrnutí editace |
||
Riadok 25:
* Maticové vyjadrenie kostier<br />
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.bmp]]
== 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>
== Príklady ==
* [[Kružnica (graf)|Kružnica]] na ''n'' vrcholoch (graf <math>C_n</math>) má práve ''n'' rôznych kostier.
| |||