Sysop: + NEW

2025-05-30T10:05:55Z

+ NEW

Nová stránka

'''Minor''' [[graf (teorie grafů)|grafu]] je rozšířením pojmu [[podgraf]]u.

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

== Indukovaný minor ==
'''Indukovaný minor''' je takový minor, který lze získat kontrakcemi z [[podgraf#indukovaný podgraf|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í [[Graf (teorie grafů)#Odebrání vrcholu|odebrání vrcholu]], [[Graf (teorie grafů)#Odebrání hrany|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í (matematika)|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í.
# 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 (matematik)|Neil Robertson]] a [[Paul Seymour (matematik)|Paul Seymour]] dokázali, že tato relace definuje na třídě všech grafů [[Dobře uspořádaná množina|dobré uspořádání]].

== Třídy grafů uzavřené na minory ==
[[Soubor:Partial 3-tree forbidden minors.png|thumb|240px|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á šířka|stromové šířky]] nejvýše ''k''
** ''k''=1 — lesy — zakázaný minor K3
** ''k''=2 — [[sériově paralelní graf]]y — zakázaný minor K4
** ''k''=3 — zakázané minory C5[[součin grafů|◻]]K2, K5, W8, K2,2,2
* grafy nakreslitelné bez křížení hran na nějakou [[plocha|plochu]]
** [[rovinný graf|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 ==

{{Commonscat}}{{Článek z Wikipedie}}
[[Kategorie:Grafové pojmy]]

Minor (teorie grafů) - Historie editací

Sysop: + NEW