Graafiteoriassa hyvin järjestetty graafi on graafi, jonka kärjet voidaan järjestää siten, että ahne väritysalgoritmi tällä järjestyksellä värittää optimaalisesti minkä tahansa generoidun graafin aligraafin. Vastaavaa järjestystä kutsutaan täydelliseksi . Täysin järjestettävät kaaviot muodostavat täydellisten kuvaajien alaluokan, ja tähän alaluokkaan kuuluvat sointukuvaajat , vertailukelpoisuuskaaviot ja etäisyyden periytyneet graafit . Kuitenkin sen tarkistaminen, onko graafi täysin järjestettävissä, on NP-täydellinen ongelma.
Ahne väritysalgoritmi, kun sitä sovelletaan tiettyyn graafin G kärkien järjestykseen, ottaa huomioon graafin kärjet peräkkäin (järjestyksen mukaan) ja antaa kullekin kärjelle ensimmäisen saatavilla olevan värin. Erilaiset kärkijärjestykset voivat johtaa erilaisiin tarvittaviin värimääriin. Aina on järjestys, joka johtaa optimaaliseen väritykseen - tämä pätee esimerkiksi tilattaessa huippuja optimaalisen värityksen värien mukaan, mutta tällaista järjestystä voi olla vaikea löytää. Hyvin järjestetyt graafit ovat määritelmän mukaan kaavioita, joille on olemassa optimaalinen järjestys ahneelle väritysalgoritmille, ei vain itse graafille vaan myös kaikille sen luomille aligraafille .
Muodollisemmin graafin G sanotaan olevan täysin järjestettävissä, jos G :n kärkien järjestys π on sellainen, että mikä tahansa G :n generoitu osagraafi väritetään optimaalisesti ahneella väritysalgoritmilla käyttämällä aligraafin kärkien generoimaa järjestysosasekvenssiä π. . Järjestyksellä π on tämä ominaisuus juuri silloin, kun ei ole neljää kärkeä a , b , c ja d , joille abcd on generoitu aligraafi, jossa a tulee ennen b :tä (järjestykseen) ja c tulee d :n jälkeen [1] [2 ] .
Hyvin järjestettyjen graafien tunnistaminen on NP-täydellinen ongelma [3] [2] . On kuitenkin helppo tarkistaa, täyttääkö tietty tilaus täydellisesti (eli täyttääkö täysin tilattavan graafin vaatimukset). Siksi on NP-kova ongelma löytää graafin täydellinen järjestys, vaikka tiedettäisiin etukäteen, että graafi on täysin järjestetty.
Mikä tahansa täysin järjestettävä kaavio on täydellinen . [1] [2]
Sointukaaviot ovat täysin tilattavissa. Sointukaavioiden täydellinen järjestys voidaan löytää kääntämällä kaavion täydellinen poikkeusjärjestys. Siten ahneen väritysalgoritmin soveltaminen täydelliseen järjestykseen tarjoaa tehokkaan väritysalgoritmin sointukaavioille. Vertailukelpoisuusgraafit ovat myös täysin järjestettäviä, joissa täydellisen järjestyksen määrää graafin transitiivisen orientaation topologinen järjestys [1] [2] .
Toinen hyvin järjestettyjen graafien luokka koostuu graafista G siten, että missä tahansa G :n viiden kärjen osajoukossa vähintään yhdellä viidestä pisteestä on suljettu naapurusto , joka on toisen suljetun lähialueen osajoukko (tai yhtä suuri kuin). pisteitä viiden parhaan joukkoon. Vastaavasti nämä ovat kaavioita, joissa joukkojen sisällyttämisellä määritetyn suljettujen lähialueiden osittaisen järjestyksen leveys on enintään 4. Sykligraafin , jossa on 5 kärkeä, on osittaisnaapuruusjärjestys, jonka leveys on viisi, joten neljä on suurin leveys joka tarjoaa täydellisen järjestyksen. Kuten sointukaavioiden tapauksessa (mutta ei yleensä täysin järjestettävien graafien tapauksessa yleensä), neljän leveyden kuvaajat tunnistetaan polynomiajassa [4] [5] .
Konsepti sointukaavioiden täydellisen eliminointijärjestyksen ja täydellisen järjestyksen välillä on puolitäydellisen eliminaatiojärjestyksen käsite . Täydellisessä eliminointikonseptissa ei ole 3-pisteistä generoitua polkua , jossa keskipiste eliminoidaan ensin, ja puolitäydellisessä eliminointijärjestyksessä ei ole 4-pisteen generoituja polkuja, joissa yksi keskipisteistä poistetaan ennen muut neljästä. Tällaisen järjestyksen kääntäminen täyttää siis täydellisen järjestyksen vaatimukset, joten graafit, joissa on puolitäydellinen eliminointijärjestys, ovat täysin järjestettävissä [6] [7] . Erityisesti leksikografista leveysensimmäistä hakualgoritmia , jota käytetään täydellisen poissulkemisjärjestyksen löytämiseen sointukaavioille, voidaan käyttää etäisyyden perittyjen graafien puolitäydellisen poissulkemisjärjestyksen löytämiseen , jotka ovat siten myös täysin järjestettäviä [8] .
Graafit, joille mikä tahansa kärkijärjestys on täydellinen, ovat cographs , jotka ovat sekä sointu- että etäisyyden periytyviä graafeja [9] . Koska kopiot eivät sisällä generoituja neljän kärjen polkuja, ne eivät voi rikkoa vaatimusta, jonka mukaan polut on järjestettävä täydellisessä järjestyksessä.
Joitakin muita täysin järjestettävien graafien luokkia tunnetaan [10] [6] [11] [2] [12] .