Hadwigerin arvelu (graafiteoria)

Hadwigerin arvelu (graafiteoria) on yksi graafiteorian ratkaisemattomista hypoteeseista . Se on muotoiltu seuraavasti: jokainen -kromaattinen graafi on kutistettavissa täydelliseksi graafiksi pisteillä . $k$ $k$

Muu sanamuoto

Hadwigerin olettamus voidaan muotoilla eri tavalla: jokaisessa -kromaattisessa graafissa on välttämättä ei-leikkaavia yhteenliitettyjä aligraafia siten, että minkä tahansa kahden välillä on reuna. $k$ $k$

Jos graafille otetaan käyttöön Hadwiger-luku — maksimi siten, että supistumme täydelliseen graafiin pisteissä, niin hypoteesi muotoillaan epäyhtälönä , jossa on graafin kromaattinen luku . $h(G)$ $k$ $G$ $k$ $\chi(G) \leqslant h(G)$ $\chi (G)$

Erikoistapaukset

Tapaukset ja ovat ilmeisiä: ensimmäisessä tapauksessa graafi sisältää vähintään yhden reunan, joka on täydellinen graafi ; toisessa tapauksessa graafi ei ole kaksiosainen ja sisältää syklin, joka voidaan supistaa . $k = 2$ $k = 3$ $K_{2}$ $K_{3}$

Hadwiger julkaisi tapauksen todisteet samassa paperissa, jossa olettamus esitettiin. $k = 4$

Tapauksen Hadwiger-oletuksesta seuraa neljän värin ongelman pätevyys (nyt todistettu): supistusoperaatio säilyttää tasomaisuuden ja jos olisi tasomainen 5-kromaattinen graafi, niin graafin upottaminen tasoon , jonka olemattomuus seuraa Eulerin kaavasta . Vuonna 1937 Klaus Wagner todisti neljän värin ongelman ja Hadwigerin arvelun vastaavuuden , joten tämä tapaus on myös todistettu. $k = 5$ $K_{5}$ $k = 5$

Vuonna 1993 N. Robertson, P. Seymour ja Robin Thomas osoittivat oletuksen neljän värin ongelman käyttämisestä. [1] Tämä todiste voitti vuoden 1994 Fulkerson-palkinnon . $k = 6$

Sillä tiedetään, että jos graafi ei täytä hypoteesia, niin se on supistettavissa sekä kahden osapuolen graafien kanssa, joilla on osat kardinaliteetti 4 ja 4 ja kardinaliteetti 3 ja 5, sekä täydennettäväksi . $k = 7$ $K_{4,4}$ $K_{3,5}$

Hadwiger-numero

On mahdollista määritellä kuvaus , joka määrittää maksimaalisen graafin siten, että supistumme pisteissä täydelliseen graafiin . Tietyn graafin Hadwiger-luvun löytäminen on NP-kova ongelma . Missä tahansa graafissa , jolle on olemassa asteen kärki . [2] Ahneesta graafin väritysalgoritmia soveltaen tästä väitteestä voidaan päätellä, että . $h(G)$ $G$ $k$ $G$ $k$ $G$ $h(G) = k$ $O(k \sqrt{\log k})$ $\chi (G) = O(h(G) \sqrt {\log h(G)})$

Katso myös

Hadwigerin arvelu (kombinatorinen geometria)

Muistiinpanot

↑ Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), "Hadwigerin arvelu K6-vapaille kaavioille" Arkistoitu 10. huhtikuuta 2009 Wayback Machinessa
↑ Kostochka, AV (1984), "Hadwigerin graafien lukumäärän alaraja niiden keskimääräisen asteen mukaan"