Kostra grafu: Rozdiel medzi revíziami
Smazaný obsah Přidaný obsah
Bez shrnutí editace |
|||
Riadok 5:
== Definície ==
* Veta: Nech G=(V,H) je súvislý graf a T je jeho podgraf s |V|-1 hranami
* Dôkaz: Nevieme, či T je súvislý, preto predpokladajme, že T je vytvorený komponentmi
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.<br />▼
▲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ť:<br />
G je strom<br />
Řádek 21 ⟶ 24:
* 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.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.<br />
| |||