Hajos-konstruktio on unkarilaisen matemaatikon György Hajosin [ 1] mukaan nimetty graafioperaatio , jolla voidaan rakentaa mikä tahansa kriittinen graafi tai mikä tahansa graafi, jonka kromaattinen luku on vähintään jokin annettu kynnys.
Olkoot G ja H kaksi suuntaamatonta graafia , vw G :n reuna ja xy H : n reuna . Sitten Hayoshin rakentaminen muodostaa uuden graafin, joka yhdistää kaksi graafia yhdistämällä kärjet v ja x yhdeksi pisteeksi, poistamalla reunat vw ja xy ja lisäämällä uuden reunan wy .
Olkoot esimerkiksi G ja H kaksi täydellistä K 4 -graafia , joissa on neljä kärkeä. Näiden graafien symmetrian vuoksi näiden graafien reunojen valinta ei ole välttämätöntä. Tässä tapauksessa Hajoshin konstruktion soveltamisen tulos on Moser-kara , seitsemän kärjen yksikköetäisyyskaavio , jonka värittämiseen tarvitaan neljä väriä.
Toinen esimerkki, jos G ja H ovat kaksi sykliä, joiden pituus on p ja q , vastaavasti, niin Hyos-konstruktion soveltamisen tulos on jälleen sykli, jonka pituus on p + q − 1 .
Graafin G k sanotaan olevan rakennettavissa (tai k -konstruoitavissa Hajoshin mukaan), jos se on muodostettu jollakin kolmesta tavasta [2] :
Riittää, kun osoitetaan yksinkertaisesti, että mikä tahansa k -konstruoitava graafi vaatii vähintään k väriä värittääkseen graafin oikein. Tämä on todellakin selvää koko graafille K k , ja kahden ei-viereisen kärjen yhdistämisen tulos pakottaa ne värjäämään samalla värillä missä tahansa värjäyksessä, mikä ei vähennä värien määrää. Itse Hajosh-konstruktiossa uusi reuna wy saa ainakin toisen kahdesta pisteestä w ja y värin, joka poikkeaa kärkien v ja x yhdistämisellä saadun kärjen väristä , joten mikä tahansa oikea väritys yhdistetty graafi saa aikaan oikean värityksen kahdesta pienemmästä graafista, joista graafi on saatu, josta taas saadaan k värin tarve [2] .
Haios osoitti tiukemman väitteen, jonka mukaan graafi vaatii vähintään k väriä missä tahansa oikeassa värjäyksessä , jos ja vain jos se sisältää k - konstruoitavan graafin aligraafina. Vastaavasti mikä tahansa k -kriittinen graafi ( kuvaaja , joka vaatii k väriä, mutta mikä tahansa oikea aligraafi, joka vaatii vähemmän värejä) on k -konstruoitava [3] . Vaihtoehtoisesti mikä tahansa graafi, joka vaatii k väriä, voidaan muodostaa yhdistämällä Hayosh-konstruktio, kahden ei-viereisen kärjen yhdistämisoperaatiot ja operaatiot pisteiden tai reunojen lisäämiseksi annettuun graafiin, alkaen täydellisestä graafista K k [4] .
Samanlaista rakennetta voidaan käyttää määrättyyn värjäämiseen tavanomaisen värityksen sijaan [5] [6] .
Kun k =3, mikä tahansa k -kriittinen graafi (eli mikä tahansa pariton jakso) voidaan muodostaa k -konstruoitavaksi graafiksi siten, että kaikki sen rakentamisen aikana muodostuneet graafit ovat myös k -kriittisiä. Kun k =8 , tämä ei pidä paikkaansa – Catlinin [7] löytämä graafi vastaesimerkkinä Hadwigerin olettamukselle, jonka mukaan k - kromaattinen graafi on kutistettavissa täydelliseksi graafiksi K k , on vastaesimerkki tälle ongelmalle. Myöhemmin k -kriittiset, mutta ei k -konstruoitavat graafit löydettiin vain yksinomaan k -kriittisten graafien kautta kaikille k ≥ 4 :lle . Kun k =4 , yksi tällainen esimerkki saadaan dodekaedrigraafista lisäämällä uusi reuna jokaiseen antipodaalipisteen pariin [8] .
Koska kahden ei-viereisen kärjen yhdistäminen vähentää tuloksena olevan graafin kärkien määrää, tietyn graafin G esittämiseen tarvittavien operaatioiden määrä Hyoszin määrittelemillä operaatioilla ei voi ylittää G :n kärkien määrää [9] .
Mansfield ja Welsh [10] määrittelevät k -kromaattisen graafin G Hajosh-luvun h ( G ) vähimmäismääräksi vaiheita, jotka tarvitaan G : n rakentamiseen K k :stä , jossa jokaisessa vaiheessa muodostetaan uusi graafi yhdistämällä kaksi aiemmin muodostettua graafia. , yhdistämällä ennen graafia muodostetun kaksi ei vierekkäistä kärkeä tai lisäämällä reuna aiemmin muodostettuun graafiin. He osoittivat , että graafille G , jossa on n kärkeä ja m reunaa , h ( G ) ≤ 2 n 2 /3 - m + 1 - 1 . Jos jollakin graafilla on polynominen Hayosh-luku, tästä seuraa, että värittömyyden osoittaminen epädeterministisessä polynomiajassa on mahdollista , ja tästä seuraa, että NP = co-NP , jota algoritmien kompleksisuusteoreetikot pitävät epätodennäköisenä [11] . Ei kuitenkaan tiedetä, kuinka ei-polynomiaalisia alarajoja voidaan todistaa Hajos-luvuille ilman teoreettista monimutkaisuutta koskevia olettamuksia, ja jos tällaiset rajat todistetaan, ei-polynomisten rajojen olemassaolo tietyntyyppisille Frege-järjestelmille matemaattisessa tekniikassa . logiikka [11] seuraa välittömästi .
Tietyn graafin G Hyos-konstruktiota kuvaavan lausekepuun vähimmäiskoko voi olla huomattavasti suurempi kuin graafin G Hyos-luku , koska G:n pienin lauseke voi käyttää samoja graafisia useaan kertaan (säästöt eivät ole sallittuja ilmaisupuu). On olemassa 3-kromaattisia kaavioita, joiden pienimmällä sellaisella lausekepuulla on eksponentiaalinen koko [12] .
Köster [13] käytti Hajos-konstruktiota saadakseen äärettömän joukon 4-kriittisiä monitahoisia graafia , joissa jokaisessa on kaksi kertaa niin monta reunaa kuin kärkipisteitä. Vastaavasti Liu ja Zhang [14] käyttivät Grötsch-graafista alkavaa konstruktiota saadakseen monia 4-kriittisiä kolmioita sisältämättömiä kaavioita , joille he osoittivat olevan vaikea löytää värejä perinteisillä paluualgoritmeilla .
Monitahoisten kombinatoriikassa Reinhard Euler [15] käytti Hajos-konstruktiota luodakseen stabiilin polytooppijoukon fasetteja .