Minor (teorie grafů)

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

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

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

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

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“ 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ří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ů

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