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. 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:

1. Pro každé v je f(v) neprázdné a souvislé.
2. Pro různé u, v jsou f(u), f(v) disjunktní.
3. 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. 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í. 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

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ů. Takovéto třídy jsou například:

• grafy stromové šířky nejvýše k
  • k=1 — lesy — zakázaný minor K₃
  • k=2 — sériově paralelní grafy — zakázaný minor K₄
  • k=3 — zakázané minory C₅◻K₂, K₅, W₈, K_2,2,2
• grafy nakreslitelné bez křížení hran na nějakou plochu
  • rovinné grafy — zakázané minory K₅ a K_3,3 (minorová Kuratowského věta)
• všechny grafy — mají prázdnou množinu zakázaných minorů

Externí odkazy

• Obrázky, zvuky či videa k tématu Minor na Wikimedia Commons