Extrémní teorie grafů

Extrémní teorie grafů je odvětví teorie grafů . Teorie extrémních grafů studuje extrémní (maximální nebo minimální) vlastnosti grafů , které splňují určité podmínky. Extremality může odkazovat na různé invarianty grafu , jako je pořadí, velikost nebo obvod. V abstraktnějším smyslu teorie studuje, jak globální vlastnosti grafu ovlivňují lokální podstruktury grafu [1] .

Příklady

Například jednoduchá otázka v teorii extremálních grafů zní: "Které n -vrcholové acyklické grafy mají maximální počet hran?" Extrémními grafy pro tuto otázku budou n -vertexové stromy s n  − 1 hranami [2] . Obecnější typická otázka zní: Vzhledem k vlastnosti grafu P , invariantu u [3] a množině grafů H chceme najít minimální hodnotu m takovou, aby každý graf v H , který má u větší než m , měl vlastnost P. . Ve výše uvedeném příkladu byla H množina grafů s n vrcholy, P byla vlastnost cyklu a u byl počet hran v grafu. Každý graf s n vrcholy a více než n  − 1 hranami tedy musí obsahovat cyklus.

Některé funkční výsledky v extremální teorii grafů jsou otázky výše uvedeného druhu. Například na otázku, kolik hran grafu s n vrcholy musí být v grafu, aby nutně obsahoval kliku o velikosti k jako podgraf, odpovídá Turanova věta . Pokud se místo klik v podobné otázce někdo zeptá na kompletní multipartitní grafy, odpověď dává Erdős-Stoneova věta .

Historie

Teorie extrémních grafů v nejpřísnějším slova smyslu je odvětví teorie grafů, které je v Maďarsku oblíbené a rozvíjené.

—  Bollobas, 2004

Extrémní teorie grafů vznikla v roce 1941, kdy Turan dokázal svou větu definující grafy řádu n , které neobsahují úplný graf K k řádu k a jsou extremální s ohledem na velikost (tj. s co nejmenším počtem hran) [4] . Dalším stěžejním rokem byl rok 1975, kdy Szémeredi dokázal svůj teorém , důležitý nástroj pro řešení extremálních problémů [4] .

Hustota grafu

Typickým výsledkem extremální teorie grafů je Turanova věta . Věta odpovídá na následující otázku. Jaký je maximální možný počet hran v neorientovaném grafu G s n vrcholy, který neobsahuje K 3 (tři vrcholy A , B , C s hranami AB , AC , BC , tj. trojúhelník) jako podgraf? Kompletní bipartitní graf , ve kterém se části liší nejvýše o 1, je jediným extrémním grafem s touto vlastností. Počet obsahuje

žebra. Podobné otázky byly vzneseny pro různé jiné podgrafy H místo K 3 . Například Zarankiewiczova úloha se ptá na největší (podle počtu hran) graf, který neobsahuje pevný úplný bipartitní graf jako podgraf, a teorém o sudých obrysech se ptá na největší graf, který neobsahuje sudé cykly pevná délka. Turan také našel (unikátní) největší graf neobsahující K k , který je po něm pojmenován, totiž Turanův graf . Tento graf je úplným spojením „k-1“ nezávislých množin a má maximum

žebra. Největší graf s n vrcholy, který neobsahuje C 4 má

žebra.

Podmínky minimálního stupně

Uvedené věty dávají podmínky pro vzhled malých objektů uvnitř (možná) velkého grafu. Jako opačné extrémy lze hledat podmínku, která si vynucuje existenci struktury, která pokrývá všechny vrcholy. Ale ten graf

hrany mohou mít izolované vrcholy, i když v grafu jsou přítomny téměř všechny možné hrany, což znamená, že i velmi husté grafy nemusí mít strukturu zájmu, která pokrývá všechny vrcholy. Jednoduchá podmínka založená na počtu hran nedává informaci o tom, jak jsou hrany rozmístěny v grafu, takže taková podmínka často dává nezajímavé výsledky pro velmi velké struktury. Místo toho zavádíme pojem minimálního stupně. Minimální stupeň grafu G je definován jako

Zadání velkého minimálního stupně odstraňuje námitku, že mohou existovat „patologické“ vrcholy. Pokud je minimální stupeň grafu G například 1, pak nemohou existovat izolované vrcholy (i když G obsahuje velmi málo hran).

Klasickým výsledkem je Diracův teorém , který říká, že každý graf G s n vrcholy a minimálním stupněm alespoň n/2 obsahuje Hamiltonův cyklus .

Viz také

Poznámky

  1. ↑ Diestel, 2010 .
  2. ↑ Bollobás, 2004 , s. 9.
  3. ↑ Obecně řečeno, vlastnost grafu a invariantu jsou jedno a totéž.
  4. ↑ 1 2 Bollobás, 1998 , s. 104.

Literatura