Neljän värin lause

Nelivärilauseen mukaan mikä tahansa tasossa tai pallolla oleva kartta voidaan värjätä korkeintaan neljällä eri värillä (maalilla) siten, että kahdella alueella, joilla on yhteinen rajasegmentti, on eri värinen. Samanaikaisesti alueet on yhdistettävä [1] (eli alue ei voi koostua kahdesta tai useammasta erillisestä "palasta") ja rajan tulee olla ei-pisteinen (yhdessä pisteessä niin monta aluetta kuin haluat voivat koskettaa kulmillaan, mukaan lukien samalla värillä maalatut).

Vuonna 1852 Francis Guthrie , kun hän laati karttaa Englannin kreivikunnista, huomasi, että neljä väriä riittää tähän tarkoitukseen. Hänen veljensä Frederick ilmoitti tästä havainnosta kuuluisalle matemaatikolle Augustus de Morganille , joka kertoi siitä matemaattiselle yhteisölle. Hypoteesin tarkan muotoilun julkaisi Arthur Cayley (1878) [2] . Lauseen todistaminen kesti kauan. Useita yrityksiä yritettiin sekä todistaa että kumota, ja tätä ongelmaa kutsuttiin neljän värin ongelmaksi [3] .

Yksinkertaisille kartoille riittää kolme väriä, ja neljäs väri tarvitaan esimerkiksi silloin, kun yhtä aluetta ympäröi pariton määrä muita, jotka koskettavat toisiaan muodostaen syklin. Viiden värin teoreemalla, joka väittää, että viisi väriä riittää, oli lyhyt, yksinkertainen todistus ja se todistettiin 1800-luvun lopulla, mutta lauseen todistaminen neljän värin tapauksessa kohtasi merkittäviä vaikeuksia.

Neljän värin lauseen todistivat vuonna 1976 Kenneth Appel ja Wolfgang HakenIllinoisin yliopistossa . Se oli ensimmäinen suuri matemaattinen lause, joka todistettiin tietokoneella. Todistuksen ensimmäinen vaihe oli osoittaa tietyn vuoden 1936 korttisarjan olemassaolo, joista yksikään ei voinut sisältää pienempää korttia, joka kumoaisi lauseen. Kirjoittajat käyttivät erityistä tietokoneohjelmaa todistaakseen tämän ominaisuuden jokaiselle vuoden 1936 kortille. Tämän tosiasian todistaminen kesti satoja sivuja. Sen jälkeen Appel ja Haken tulivat siihen tulokseen, että lauseelle ei ole pienintä vastaesimerkkiä, koska muuten sen pitäisi sisältää jokin näistä vuoden 1936 korteista, mitä siinä ei ole. Tämä ristiriita sanoo, että vastaesimerkkiä ei ole ollenkaan.

Aluksi kaikki matemaatikot eivät hyväksyneet todistetta, koska sitä ei voida tarkistaa käsin. Myöhemmin se sai laajemman hyväksynnän, vaikka jotkut epäilivät sitä pitkään. Jäljelle jääneiden epäilyjen hälventämiseksi Robertson, Sanders, Seymour ja Thomas julkaisivat vuonna 1997 yksinkertaisemman todisteen, jossa käytettiin samanlaisia ​​ideoita, mutta joka tehtiin silti tietokoneella. Lisäksi vuonna 2005 todistuksen suoritti Georges Gonteer käyttämällä erikoisohjelmistoa ( Coq v7.3.1) [4] .

Vastaavat formulaatiot

Graafiteoriassa neljän värin lauseella on seuraavat muotoilut:

• Tasograafin kromaattinen luku ei ylitä 4 [5] .
• Pallon mielivaltaisen kolmion reunat voidaan värjätä kolmella värillä siten, että kunkin kolmion kaikki sivut ovat erivärisiä. [6]

Tunnetaan monia muita vastaavia formulaatioita [5] .

Historiallisia todisteita

Tunnetuimmat todistusyritykset ovat:

• Alfred Campe ehdotti todistetta vuonna 1879 [7] , se kumottiin vuonna 1890, mutta hänen ideoidensa perusteella pystyttiin todistamaan, että mikä tahansa kartta voidaan värittää viidellä värillä [3] .
• Peter Tait ehdotti toista todistetta vuonna 1880 [3] [8] ja se kumottiin vuonna 1891.
• Maliev M. Neljän värin ongelma , 1914.

Muunnelmia ja yleistyksiä

Muut pinnat

Samankaltaiset ongelmat muille pinnoille ( torus , Klein -pullo jne.) osoittautuivat paljon yksinkertaisemmiksi. Kaikille suljetuille pinnoille, lukuun ottamatta palloa (ja sitä vastaavaa tasoa ja sylinteriä) ja Klein-pulloa , tarvittava määrä värejä voidaan laskea sen suvusta käyttämällä seuraavaa Percy John Heawoodin vuonna 1890 ehdottamaa kaavaa : [9]

Yläraja saadaan melko yksinkertaisesti, sen todisti Heawood itse (pallolle kaava antaa oikean vastauksen - 4, mutta Heawoodin todistus ei sovellu siihen). Alempi todistetaan upottamalla koko graafi vastaavaan pintaan; todistuksen rakensi vuosina 1952-1968 ryhmä matemaatikoita, viimeisen askeleen tekivät Gerhard Ringel ja John Youngs . [10] [11] [12]

Möbius -nauhalle (samoin kuin projektiivitasolle ) tarvitaan 6 väriä. Suvun yksipuolisille pinnoille [ 11]

Klein-pullon (suku ) kohdalla luku on 6 (eikä 7, kuten kaavan mukaan) - tämän osoitti P. Franklin vuonna 1934. [13]

Saaren kartta

Nelivärilauseesta seuraa, että kartta saaresta, jossa kullakin maalla on pääsy merelle, voidaan värittää kolmella värillä. Tällä väitteellä on kuitenkin myös alkeelliset todisteet.

Empire-ongelma

Percy John Heawood pohti samanlaista ongelmaa siirtomaavaltakuntia sisältävien karttojen kohdalla (eli mailla, jotka koostuvat useista erillisistä "palasista" kartalla, joiden lukumäärä on m ) . Kun vastaa . Yläraja saadaan melko yksinkertaisesti; sen todisti Heawood itse. Alempi todistetaan upottamalla koko graafi vastaavaan pintaan; Todisteen ovat antaneet Gerhard Ringel ja Brad Jackson. [neljätoista]

Ongelman variantti valtakunnista, jolla on siirtokuntia muilla planeetoilla, on edelleen avoin. Esimerkiksi, jos jokaisella maan maalla on siirtokunta Kuussa, tiedetään vain arvioita

Suuremmat mitat

Korkeammissa ulottuvuuksissa ongelman yleistäminen ei ole järkevää, koska on helppo keksiä kolmiulotteinen kartta, jossa on mielivaltainen määrä alueita, jotka kaikki koskettavat toisiaan .

Peli "neljä väriä"

Stephen Barr ehdotti paperilogiikkapeliä kahdelle pelaajalle nimeltä "Four Colors". Martin Gardnerin sanoin :  "En tiedä parempaa tapaa ymmärtää neliväriongelman ratkaisemiseen liittyviä vaikeuksia kuin vain pelaamalla tätä uteliasta peliä" [15] .

Tämä peli vaatii neljä värikynää. Ensimmäinen pelaaja aloittaa pelin piirtämällä mielivaltaisen tyhjän alueen. Toinen pelaaja maalaa sen millä tahansa neljästä väristä ja piirtää vuorostaan ​​tyhjän alueensa. Ensimmäinen pelaaja maalaa toisen pelaajan alueen ja lisää uuden alueen ja niin edelleen - jokainen pelaaja maalaa vastustajan alueen ja lisää oman. Tässä tapauksessa alueet, joilla on yhteinen raja, tulee maalata eri väreillä. Se, joka vuorollaan joutuu ottamaan viidennen värin, häviää.

Tässä pelissä yhden pelaajan menetys ei ole ollenkaan todiste lauseen virheellisyydestä (neljä väriä ei riittänyt), vaan vain esimerkki siitä, että pelin ehdot ja lauseet ovat hyvin erilaisia. . Pelissä saadun kartan lauseen oikeellisuuden tarkistamiseksi sinun on tarkistettava piirrettyjen alueiden liitettävyys ja poistamalla siitä värit selvitettävä, onko mahdollista selviytyä vain neljällä värillä maalaamaan tuloksena oleva kartta (lause sanoo, että se on mahdollista).

Pelistä löytyy myös seuraavat muunnelmat:

1. Kartta on jaettu etukäteen satunnaisesti erikokoisiin alueisiin. Jokaisella siirrolla alueen maalannut pelaaja vaihtuu ja väri vaihtuu tiukasti järjestyksessä. Siten jokainen pelaaja maalaa kortin vain kahdella värillä. Pelaaja jättää väliin, jos hän ei pysty maalaamaan aluetta siten, että vierekkäisten alueiden väri on erilainen. Peli päättyy, kun kukaan pelaajista ei voi tehdä enää liikkeitä. Voittaja on se, jolla on suurempi varjostettujen alueiden kokonaispinta-ala.
2. Neliö, jonka sivut ovat erivärisiä jollakin neljästä väristä, jaetaan useisiin neliöihin (yleensä 4 × 4). Ensimmäinen siirto maalaa sivun viereisen ruudun päälle, ja myöhemmissä siirroissa voit maalata ruudun, joka on yhden täytetyn ruudun vieressä. Et voi maalata neliön päälle väreillä, joilla jokin sen vieressä olevista ruuduista tai neliön viereinen sivu on maalattu. Pelaaja, joka tekee viimeisen liikkeen, voittaa.

Kulttuurissa

• Viiden värin saari on Martin Gardnerin fantasianovelli .

Katso myös

• Todistuslaskenta
• Nelson-Erdős-Hadwiger-ongelma

Muistiinpanot

1. ↑ Frank Harari. Neljän värin arvelu // Graph Theory = Graph Theory. - M .: Mir , 1973. - S. 17-18.
2. ↑ Samokhin A.V. Neljän värin ongelma: keskeneräinen  todistehistoria // Sorovskin koulutuslehti. - 2000. - T. 6 , nro 7 .
3. ↑ 1 2 3 J. J. O'Connor, E. F. Robertson. Neljän värin lause . MacTutor Matematiikan historia -arkisto . Matematiikan ja tilastotieteen laitos, St Andrewsin yliopisto, Skotlanti (syyskuu 1996). (määrätön)
4. ↑ Georges Gonthier. Tietokoneella tarkistettu todiste neljän värin lauseesta  . Microsoft Research Cambridge (2005). Arkistoitu alkuperäisestä 5. kesäkuuta 2022.
5. ↑ 1 2 Shor N. Z. , Donets G. A. Neljän värin ongelmasta // Mathematics today / toim. prof. A. Ya. Dorogovtseva  - Kiova, Vishcha-koulu, 1982. - Levikki 3000 kappaletta. - c. 33-53
6. ↑ Lakeev A.V. Tavallisten graafien teorian elementit. - Irkutsk: IGU Publishing House, 2014. - S. 7. - 92 s.
7. ↑ A.B. Kempe. Neljän värin maantieteellisestä ongelmasta  (englanniksi)  // Amer. J Math. . - 1879. - Voi. 2 . - s. 193-200 .
8. ↑ P.G. Tait. Huomautus asemageometrian lauseesta   // Trans . Roy. soc. Edinburgh . - 1880. - Voi. 29 . - s. 657-660 .
9. ↑ Percy John Heawood. Map-Color Theorem  (englanniksi)  // Quarterly Journal of Mathematics, Oxford. - 1890. - Voi. 24 . - s. 332-338 .
10. ↑ G. Ringel, JWT Youngs. Heawood-kartan värjäysongelman ratkaisu   // Proc . Nat. Acad. sci. USA. - 1968. - Voi. 60 , iss. 2 . - s. 438-445 . - doi : 10.1073/pnas.60.2.438 . — PMID 16591648 .
11. ↑ 1 2 Ringel G. Kartan värityslause / Englannista kääntänyt V. B. Alekseev. - M .: Mir, 1977. - 256 s.
12. ↑ Boltyansky, 1982 , s. 77.
13. ↑ P. Franklin. Kuuden värin ongelma  //  J. Math. Phys. - 1934. - Voi. 13 . - s. 363-369 .
14. ↑ Jackson, Brad; Ringel, Gerhard. Heawoodin valtakuntaongelma  //  J. Combin. Teoria Ser. B. - 1985. - Voi. 38 , ei. 2 . - s. 168-178 .
15. ↑ Martin Gardner. Neljän värin ongelma // Mathematical puzzles and diversions = Mathematical puzzles and diversions: [käännös. englannista  . ]. - 2. painos - M  .: Mir , 1999. - S. 389-390. — 447 s. — ISBN 5-03-003340-8 .
16. ↑ Martin Gardner. Viiden värin saari . N.Y .: Fantasia Mathematica , 1958.

Kirjallisuus

• Ian Stewart . Suurin matemaattinen ongelma = Suuria matemaattisia ongelmia. - M. : Dynastia : ANF, 2015. - 459 s. : ill., välilehti. — ISBN 978-5-91671-318-3
• A. A. Zykov. Graafiteorian perusteet. - M . : Vuzovskaja kirja, 2000. - S. 367-386.
• R. Courant, G. Robbins Mitä matematiikka on?
• Samokhin A. V. Neljän värin ongelma: todistuksen keskeneräinen historia  // SOZH . - 2000. - Nro 7 . - S. 91-96 .  (Käytetty: 7. marraskuuta 2018)
• Rodionov VV Menetelmät tasograafien kärkien neliväriseksi värjäykseen. - M . : KomKniga, 2000. - 48 s. - 2005 kappaletta.  — ISBN 5-484-00127-7 .
• Thomas, Robin The Four Color Theorem Arkistoitu 21. joulukuuta 2007 Wayback Machinessa
• Ringel G. Kartan värityslause / Englannista kääntänyt V. B. Alekseev. - M .: Mir, 1977. - 256 s.  - kirja, jossa on todiste ongelmasta kaikille pinnoille paitsi tasolle ja pallolle
• Boltyansky V. G. , Efremovich V. A. Visuaalinen topologia. - M .: Nauka, 1982. - 160 s. - ( Kirjasto "Kvantti" ).
• Donets GA, Shor NZ Algebrallinen lähestymistapa tasograafien värityksen ongelmaan. - Kiova: Naukova Dumka , 1982. - 144 s.
• Harari F. Graafiteoria. - M., Mir, 1973. - 304 s.

Sanakirjat ja tietosanakirjat	Suuri katalaani iso kiinalainen Iso venäläinen Britannica (verkossa) Britannica (verkossa) Universalis