\input ../sgr.tex
-\prednaska{6}{Rychlej¹í algoritmy na~minimální kostry}{}
+\prednaska{6}{Rychlej¹í algoritmy na minimální kostry}{}
V~této kapitole popí¹eme nìkolik pokroèilej¹ích algoritmù pro problém minimální
kostry. Vesmìs to budou rùzná vylep¹ení klasických algoritmù z~minulé kapitoly.
Pokud je $\cal C$ minorovì uzavøená tøída grafù, existuje koneèná mno¾ina grafù $Z$ taková,
¾e pro ka¾dý graf $G$ platí:
$$G \not\in {\cal C} \iff \exists H \in Z: H \preceq G.$$
-
Jinými slovy, ka¾dou minorovì uzavøenou tøídu lze charakterizovat {\I koneèným} poètem zakázaných minorù.
To není samo sebou, dokazuje se to dosti obtí¾nì (a~je to jedna z~nejslavnìj¹ích kombinatorických
vìt za~posledních mnoho let), ale plyne z~toho spousta zajímavých dùsledkù.