A gráfelméletben a jól rendezett gráf olyan gráf, amelynek csúcsai úgy rendezhetők, hogy a mohó színező algoritmus ezzel a rendezéssel optimálisan színezi az adott gráf bármely generált részgráfját . A megfelelő sorrendet tökéletesnek nevezzük . A teljesen rendezhető gráfok a tökéletes gráfok alosztályát alkotják , és ebbe az alosztályba tartoznak az akkordgráfok , az összehasonlíthatósági gráfok és a távolság öröklött gráfok . Azonban annak ellenőrzése, hogy egy gráf teljesen rendezhető-e, NP-teljes probléma.
A mohó színező algoritmus, ha egy G gráf csúcsainak adott sorrendjére alkalmazzuk, a gráf csúcsait szekvenciálisan (a sorrendnek megfelelően) veszi figyelembe, és minden csúcshoz hozzárendeli az első elérhető színt. A különböző csúcsok sorrendje eltérő számú színt eredményezhet. Mindig van egy rendezés, ami az optimális színezéshez vezet - ez igaz például a csúcsok optimális színezésének színei szerint történő rendezésekor, de előfordulhat, hogy egy ilyen sorrendet nehéz megtalálni. A jól rendezett gráfok definíció szerint olyan gráfok, amelyeknél a mohó színezési algoritmus számára optimális a rendezés, nemcsak magának a gráfnak, hanem az összes generált részgráfnak is .
Formálisabban egy G gráfot teljesen rendezhetőnek mondunk , ha létezik G csúcsainak π rendezettsége úgy , hogy G bármely generált részgráfját optimálisan színezi a mohó színező algoritmus, a részgráf csúcsai által generált π rendező részsorozat segítségével. . Egy π rendezés pontosan akkor rendelkezik ezzel a tulajdonsággal, ha nincs négy olyan a , b , c és d csúcs, amelyekre az abcd egy generált részgráf, amelyben a b elé kerül (a rendezésben), c pedig d után jön [1] [2 ] .
A jól rendezett gráfok felismerése NP-teljes probléma [3] [2] . Könnyen ellenőrizhető azonban, hogy egy adott rendezés tökéletesen kielégít-e (azaz megfelel-e egy teljesen rendezhető grafikon követelményeinek). Ezért NP-nehéz probléma egy gráf tökéletes rendezését megtalálni, még akkor is, ha előre tudjuk, hogy a gráf teljesen rendezett.
Minden teljesen rendezhető grafikon tökéletes . [1] [2]
Az akkordgrafikonok teljesen rendelhetők. Az akkordgráfok tökéletes sorrendjét a gráf tökéletes kivételi sorrendjének megfordításával találhatjuk meg. Így a mohó színezési algoritmus tökéletes rendezésre való alkalmazása hatékony színezési algoritmust biztosít akkordgráfokhoz. Az összehasonlíthatósági gráfok is teljesen rendezhetők, ahol a tökéletes sorrendet a gráf tranzitív orientációjának topológiai sorrendje határozza meg [1] [2] .
A jól rendezett gráfok egy másik osztálya a G gráfokból áll, így a G -beli öt csúcsból álló bármely részhalmazban az öt csúcs közül legalább az egyik zárt szomszédsággal rendelkezik , amely a másik zárt szomszédságainak részhalmaza (vagy egyenlő azzal). csúcsok az első ötben. Ezzel egyenértékűen olyan gráfokról van szó, amelyekben a halmazok bevonásával meghatározott zárt környezetek részleges sorrendje legfeljebb 4 szélességű . Az 5 csúcsot tartalmazó ciklusgráf részleges szomszédsági sorrendje öttel egyenlő, tehát négy a maximális szélesség amely tökéletes sorrendet biztosít. Akárcsak az akkordgráfok esetében (de általában nem teljesen rendezhető gráfoknál), a négyes szélességű gráfokat polinomiális időben ismeri fel [4] [5] .
Az akkordgráfok tökéletes eliminációs sorrendje és a tökéletes sorrend közötti koncepció a féltökéletes eliminációs sorrend fogalma . A tökéletes eliminációs koncepcióban nincs olyan 3 csúcsból generált útvonal , amelyben a középső csúcsot először eliminálják, és a féltökéletes eliminációs sorrendben nincsenek 4 csúcsból generált utak, amelyekben az egyik középső csúcs eltávolításra kerül. a többiek a négyből. Egy ilyen sorrend megfordítása tehát kielégíti a tökéletes rendezés követelményeit, így a féltökéletes eliminációs sorrendű gráfok teljesen rendezhetők [6] [7] . Az akkordgráfok tökéletes kizárási sorrendjének megtalálására használt lexikográfiai szélesség-első keresési algoritmus használható a távolság öröklött gráfok féltökéletes kizárási sorrendjének megtalálására , amelyek így szintén teljesen rendezhetők [8] .
Azok a gráfok, amelyekre a csúcsok bármilyen sorrendje tökéletes, a kográfok , amelyek egyben akkordális és távolság öröklött gráfok [9] . Mivel a kográfok nem tartalmaznak négy csúcsból generált útvonalakat, nem sérthetik meg azt a követelményt, hogy az utak tökéletes sorrendben legyenek rendezve.
A teljesen rendezhető gráfok néhány más osztálya is ismert [10] [6] [11] [2] [12] .