Gallai-Hasse-Roy-Vitaver-lause on eräänlainen kaksinaisuus tietyn suuntaamattoman graafin kärkiväritysten ja sen reunojen orientaatioiden välillä . Lause väittää, että minkä tahansa graafin G oikeaan värjäämiseen vaadittava vähimmäisvärien määrä on yksi enemmän kuin maksimipolun pituus [ graafin G orientaatiossa , jossa tämä polun pituus on minimaalinen [1] . Suunta, jossa maksimipituudella on minimipituus, sisältää aina vähintään yhden asyklisen orientaation [2] .
Saman lauseen vaihtoehtoinen muotoilu väittää, että mikä tahansa graafin orientaatio, jonka kromaattinen luku on k , sisältää yksinkertaisen suunnatun polun, jossa on k pistettä [3] . Voidaan asettaa ehtoja niin, että polku alkaa mistä tahansa kärjestä ja että tästä kärjestä on mahdollista saavuttaa mihin tahansa muuhun suunnatun graafin kärkeen [4] [5] .
Kaksiosainen graafi voidaan suunnata osasta toiseen. Tämän orientaation pisimmällä polulla on vain kaksi kärkeä. Käänteisesti, jos graafin orientaatio ei sisällä polkua, jonka pituus on kolme, minkä tahansa kärjen on oltava joko lähde (ei saapuvia kaaria) tai nielu (ei lähteviä kaaria), ja kärkien jakaminen lähteiksi ja nieluiksi osoittaa, että tämä graafi on kaksiosainen.
Parittoman pituisen graafisyklin missä tahansa orientaatiossa on mahdotonta antaa kaikille vierekkäisille reunoille eri suunnat, jolloin kaksi peräkkäistä reunaa muodostavat polun, jossa on kolme kärkeä. Näin ollen parittomien syklien kromaattinen lukumäärä on kolme.
Todistaaksesi, että kromaattinen luku on suurempi tai yhtä suuri kuin maksimipolun minimipituus, oletetaan, että kuvaaja on värjätty k värillä jollekin k :lle . Sitten graafia voidaan suunnata asyklisesti numeroimalla värit ja jokainen reuna voidaan suunnata pienemmän indeksin väristä korkeampaan. Tässä suunnassa väriindeksit kasvavat tiukasti mitä tahansa suunnattua polkua pitkin siten, että jokainen polku sisältää enintään yhden pisteen jokaisesta väristä ja polun kärkien kokonaismäärä ei voi ylittää k :tä (värien lukumäärä).
Todistaaksesi, että kromaattinen luku on pienempi tai yhtä suuri kuin maksimipolun minimipituus, oletetaan, että graafilla on orientaatio, jossa on enintään k kärkeä missä tahansa suunnatussa polussa jollekin k :lle . Graafin kärjet voidaan värjätä k värillä valitsemalla maksimaalisen asyklisen orientaation aligraafin ja värittämällä sitten jokainen kärki värillä, jonka indeksi on yhtä suuri kuin pisimmän polun pituus annettuun kärkeen. Tällaisella värityksellä aligraafin jokainen reuna on suunnattu alhaisemman indeksin kärjestä korkeamman indeksin kärkeen, ja siksi väritys on oikea. Jokaiselle reunalle, joka ei kuulu osagraafiin, tulee olla aligraafin sisällä suunnattu polku, joka yhdistää nämä kaksi kärkeä vastakkaiseen suuntaan, muuten reuna putoaisi aligraafiin. Siten reuna on suunnattu suuremmasta numerosta pienempään eikä riko värityksen oikeellisuutta [6] .
Juri Vladimirovitš Matiyasevitš käytti tämän lauseen todistusta testitapauksena ehdotetulle todistusjärjestelmälle diskreetissä matematiikassa [7] .
Lauseen luonnollinen tulkinta on suunnattujen graafien ja graafihomomorfismien luokissa . Homomorfismi on yhden graafin kärkien kartoitus toisen graafin kärkipisteisiin, jossa vierekkäiset kärjet pysyvät vierekkäin kuvassa. Tällöin suuntaamattoman graafin G k -väritys voidaan kuvata graafin G homomorfismilla täydelliseksi graafiksi K k . Täydellisen kaavion suuntautumisesta tulee turnaus , ja tätä suuntaa voidaan käyttää suuntauksen määrittämiseen kaaviossa G . Erityisesti pisimmän polun antama väritys vastaa homomorfismia transitiiviseksi turnaukseksi (asyklisesti suuntautunut täydellinen graafi), ja mikä tahansa väritys voidaan kuvata sellaisella homomorfismilla transitiiviseksi turnaukseksi.
Jos tarkastellaan homomorfismeja toiseen suuntaan, G : hen , ei G :stä , suunnattu graafi G on asyklinen ja sillä on pisimmällä polulla enintään k kärkeä silloin ja vain, jos polkuhomomorfismia P k + 1 G :hen ei ole .
Siten Gallai-Hasse-Roy-Vitaver-lause vastaa lausetta, jonka mukaan mille tahansa suunnatulle graafille G on olemassa homomorfismi transitiiviseen turnaukseen, jossa on k pistettä, jos ja vain, jos polulta, jossa on ( k + 1) ei ole homomorfismia. kärjet [2] . Siinä tapauksessa, että graafi G on asyklinen, väitettä voidaan pitää Mirskin lauseen muotona, että pisin ketju osittain järjestetyssä joukossa on yhtä suuri kuin pienin määrä antiketjuja, joihin joukko voidaan jakaa [8 ] . Lausunto voidaan yleistää poluista muihin suunnattuihin graafeihin — mille tahansa polypuulle P on olemassa kaksoissuuntainen graafi D siten, että mille tahansa suunnatulle graafille G on olemassa homomorfismi G :stä D :hen, jos ja vain jos ei ole isomorfia P - G [9] .
Gallai-Hasse-Roy-Vitaver-lause on toistuvasti löydetty uudelleen [2] . Lause on saanut nimensä T. Gallain [10] , M. Hassen [11] , B. Royn [12] ja L. M. Vitaverin [13] erillisistä julkaisuista . Roy väittää lauseen muotoilun Claude Bergen ansioksi , joka esitti sen olettamuksena graafiteoriaa käsittelevässä kirjassa vuonna 1958 [12] .