Minor (teorie grafů)

Minor grafu je rozšířením pojmu podgrafu.

Minor

Minor H grafu G je takový graf, který může vzniknout z nějakého podgrafu G kontrakcemi některých hran.

Indukovaný minor

Indukovaný minor je takový minor, který lze získat kontrakcemi z indukovaného podgrafu.

Topologický minor

Topologický minor je takový, který lze získat z podgrafu pouze topologickými kontrakcemi. To jsou takové, kde alespoň jeden z vrcholů kontrahované hrany má stupeň nejvýše 2.

Minorové operace

Minorovými operacemi se míní odebrání vrcholu, odebrání hrany a kontrakce hrany. To jsou právě ty operace, které jsou zapotřebí k přeměnění grafu na jakýkoli jeho minor. +more Indukovaný minor se dá získat bez použití operace odebrání hrany.

Alternativní definice

Graf H je minorem grafu G tehdy, když existuje zobrazení f: V(H) → P(V(G)) takové, že: # Pro každé v je f(v) neprázdné a souvislé. # Pro různé u, v jsou f(u), f(v) disjunktní. +more # Mezi u, v smí být hrana pouze pokud je hrana mezi nějakým vrcholem f(u) a nějakým vrcholem f(v). V případě indukovaného minoru mezi takovými u a v hrana být musí.

Ekvivalence s původní definicí se nahlédne snadno: Po zahození vrcholů mimo f(V(H)) se každá souvislá f(u) dá zkontrahovat do jediného vrcholu. Tak vznikne indukovaný minor, ze kterého se případným odstraněním některých hran získá minor H. +more Pro opačný směr stačí f(v) nazvat ty vrcholy, které se zkontrahovaly do vrcholu v a ověřit vlastnosti f(v).

Relace „býti minorem“

Relace „býti minorem“ je reflexivní (každý graf je sám sobě triviálním minorem), tranzitivní (každý minor minoru H grafu G je i minorem grafu G) a až na isomorfismus antisymetrická (každá minorová operace sníží počet vrcholů nebo hran). Jedná se tedy o částečné uspořádání. +more Neil Robertson a Paul Seymour dokázali, že tato relace definuje na třídě všech grafů dobré uspořádání.

Třídy grafů uzavřené na minory

Zakázané minory pro grafy stromové šířky nejvýše 3

Třída grafů F je uzavřená na minory, pokud každý minor nějakého grafu z F je také v F. Důsledkem toho, že minorová relace určuje dobré uspořádání, je to, že se každá taková třída dá charakterizovat konečným počtem zakázaných minorů. +more Takovéto třídy jsou například: * grafy stromové šířky nejvýše k ** k=1 - lesy - zakázaný minor K3 ** k=2 - sériově paralelní grafy - zakázaný minor K4 ** k=3 - zakázané minory C5◻K2, K5, W8, K2,2,2 * grafy nakreslitelné bez křížení hran na nějakou plochu ** rovinné grafy - zakázané minory K5 a K3,3 (minorová Kuratowského věta) * všechny grafy - mají prázdnou množinu zakázaných minorů.

Externí odkazy

Kategorie:Grafové pojmy