V teorii grafů je dobře uspořádaným grafem graf, jehož vrcholy lze uspořádat tak, že chamtivý barvicí algoritmus s tímto uspořádáním optimálně obarví jakýkoli vygenerovaný podgraf daného grafu. Odpovídající řazení se nazývá dokonalé . Zcela uspořádané grafy tvoří podtřídu dokonalých grafů a tato podtřída zahrnuje akordické grafy , grafy srovnatelnosti a grafy zděděné vzdáleností . Nicméně kontrola, zda je graf zcela uspořádaný, je NP-úplný problém.
Algoritmus chamtivé barvy, když je aplikován na dané uspořádání vrcholů grafu G , zvažuje vrcholy grafu postupně (podle pořadí) a přiřazuje každému vrcholu první dostupnou barvu. Různé uspořádání vrcholů může vést k různému počtu požadovaných barev. Vždy existuje řazení, které vede k optimálnímu zbarvení - to platí například při řazení vrcholů podle barev optimálního zbarvení, ale takové řazení může být obtížné najít. Dobře uspořádané grafy jsou ze své podstaty grafy, pro které existuje uspořádání, které je optimální pro algoritmus chamtivého zbarvení, a to nejen pro samotný graf, ale také pro všechny jeho generované podgrafy .
Formálněji se o grafu G říká, že je zcela uspořádaný , pokud existuje uspořádání π vrcholů G tak , že jakýkoli vygenerovaný podgraf G je optimálně obarven algoritmem chamtivého vybarvování pomocí podsekvence řazení π generované vrcholy podgrafu. . Uspořádání π má tuto vlastnost právě tehdy, když neexistují žádné čtyři vrcholy a , b , c a d , pro které abcd je vygenerovaný podgraf, ve kterém a je před b (v uspořádání) a c za d [1] [2 ] .
Rozpoznání dobře uspořádaných grafů je NP-úplný problém [3] [2] . Je však snadné zkontrolovat, zda konkrétní uspořádání dokonale vyhovuje (tj. splňuje požadavky na zcela uspořádaný graf). Proto je NP-těžký problém najít dokonalé uspořádání grafu, i když je předem známo, že graf je kompletně uspořádaný.
Jakýkoli zcela uspořádaný graf je dokonalý . [1] [2]
Chordální grafy jsou zcela uspořádané. Dokonalé pořadí akordických grafů lze nalézt obrácením pořadí dokonalé výjimky pro graf. Použití algoritmu chamtivého zbarvení na dokonalé uspořádání tedy poskytuje účinný algoritmus barvení pro akordické grafy. Zcela uspořádané jsou také grafy srovnatelnosti , kde dokonalé uspořádání je určeno topologickým uspořádáním tranzitivní orientace grafu [1] [2] .
Další třída dobře uspořádaných grafů se skládá z grafů G tak, že v jakékoli podmnožině pěti vrcholů v G má alespoň jeden z pěti vrcholů uzavřené okolí , které je podmnožinou (nebo rovno) uzavřeným sousedstvím druhého. vrcholy v prvních pěti. Ekvivalentně se jedná o grafy, ve kterých má částečné pořadí uzavřených sousedství definované zahrnutím množin šířku maximálně 4. Cyklický graf s 5 vrcholy má řád částečného sousedství o šířce rovné pěti, takže čtyři je maximální šířka která poskytuje dokonalé uspořádání. Stejně jako v případě akordických grafů (ale obecně ne pro úplně uspořádané grafy obecně) jsou grafy šířky čtyři rozpoznávány v polynomiálním čase [4] [5] .
Koncept mezi dokonalým eliminačním řádem pro akordické grafy a dokonalým uspořádáním je pojem polodokonalého eliminačního řádu . V konceptu dokonalé eliminace neexistuje žádná cesta generovaná 3 vrcholy, ve které je prostřední vrchol eliminován jako první, a v pořadí semi-dokonalé eliminace neexistují žádné cesty generované 4 vrcholy, ve kterých by byl jeden ze středních vrcholů odstraněn dříve. ostatní ze čtyř. Obrácení takového uspořádání tak splňuje požadavky na dokonalé uspořádání, takže grafy se semiperfektním eliminačním řádem jsou zcela uspořádané [6] [7] . Zejména lexikografický algoritmus prohledávání šířky, který se používá k nalezení dokonalého pořadí vyloučení pro akordické grafy, lze použít k nalezení semiperfektního pořadí vyloučení grafů zděděných vzdáleností , které jsou tak také zcela uspořádané [8] .
Grafy, pro které je jakékoli uspořádání vrcholů dokonalé, jsou cographs , což jsou jak akordické grafy, tak grafy zděděné vzdáleností [9] . Protože kografy neobsahují vygenerované cesty čtyř vrcholů, nemohou porušit požadavek, aby cesty byly uspořádány v dokonalém pořadí.
Jsou známy některé další třídy zcela uspořádaných grafů [10] [6] [11] [2] [12] .