Minor (teorie grafů)

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

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

Minor[editovat | editovat zdroj]

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

Indukovaný minor[editovat | editovat zdroj]

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

Topologický minor[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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“[editovat | editovat zdroj]

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[editovat | editovat zdroj]

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ů. 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 C5K2, 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ů