Graafiteorian sovellukset
Tasomaiset kuvaajat
Graafin G sanotaan olevan tasomainen, jos se voidaan esittää tasossa siten, että kaikki kärjet ovat erillisiä pisteitä, reunat ovat yksinkertaisia käyriä ja kukaan kaksi reunaa ei kohtaa toisiaan paitsi niiden navoissa. Esimerkiksi, K 4, täydellinen kuvaaja neljän pisteen, on tasomainen, kuten kuviossa 4A on esitetty.
Kahden kuvaajan sanotaan olevan homeomorfinen, jos molemmat voidaan saada samasta kuvaajasta reunojen alajakoon. Esimerkiksi kuvioiden 4A ja 4B kaaviot ovat homeomorfisia.
K m, n -diagrammi on kuvaaja, jonka kärkijoukko voidaan jakaa kahteen osajoukkoon, joista toisessa on m huippua ja toisessa n kärkipistettä. Saman alajoukon kaikki kaksi kärkeä eivät ole vierekkäisiä, kun taas kaikki eri alajoukkojen kaksi kärkeä ovat vierekkäin. Puolalainen matemaatikko Kazimierz Kuratowski todisti seuraavan kuuluvan lauseen vuonna 1930:
Välttämätön ja riittävä edellytys graafi G on tasomainen on, että se ei sisällä aligraafi homeomorphic joko K 5 tai K 3,3 kuviossa 5 on esitetty.
Elementaarisen supistuminen graafin G on muutos G uuteen graafin G 1, siten, että kaksi vierekkäistä pisteiden u ja υ G korvataan uudella piste w G 1 ja w on vieressä G 1 ja kaikki kärkipisteet joka joko u tai υ on vieressä G: ssä. Graafin G * sanotaan olevan G: n supistuminen, jos G * voidaan saada G: stä alkuaineiden supistumisten sekvenssillä. Seuraava on toinen karakterisointi tasomaisesta kuvaajasta, joka johtuu saksalaisesta matemaatikosta K. Wagnerista vuonna 1937.
Graafi on tasomainen vain silloin, kun se ei ole supistettavissa K 5: lle tai K 3,3: lle.
Nelivärikartta-ongelma
Jo yli vuosisadan ajan nelivärikartta-ongelman ratkaisu vältti jokaista analyytikkoa, joka yritti sitä. Ongelma on saattanut herättää Möbiuksen huomion, mutta ensimmäinen kirjallinen viittaus siihen näyttää olevan yhden Francis Guthrien kirje hänen veljelleen, Augustus De Morganin opiskelijalle, vuonna 1852.
Ongelma koskee tasomaisia karttoja - ts. Tason alajaotuksia limittymättömiksi alueiksi, joita rajoittavat yksinkertaiset suljetut käyrät. Maantieteellisissä karttoissa on kokeellisesti todettu, että niin monissa erityistapauksissa kuin on kokeiltu, että alueiden väritykseen tarvitaan korkeintaan neljä väriä siten, että kaksi yhteistä rajaa jakavaa aluetta väritetään aina eri tavalla, ja tietyissä tapauksissa, että vähintään neljä väriä ovat tarpeen. (Alueilla, jotka kohtaavat vain yhdessä pisteessä, kuten Coloradon osavaltiossa ja Arizonassa Yhdysvalloissa, ei katsota olevan yhteisiä rajoja). Tämän empiirisen havainnon virallistaminen muodostaa niin kutsutun ”neliväriteoreen”. Ongelmana on todistaa tai kiistää väite, että näin on jokaisessa tasomaisessa kartassa. Se, että kolme väriä eivät riitä, voidaan helposti osoittaa, kun taas viiden värin riittävyys osoitettiin vuonna 1890 brittiläisen matemaatikon PJ Heawoodin toimesta.
Vuonna 1879 englantilainen AB Kempe ehdotti ratkaisua neliväritehtävään. Vaikka Heawood osoitti Kempen väitteen olevan virheellinen, kaksi sen käsitettä osoittautui hedelmälliseksi myöhemmässä tutkimuksessa. Yksi näistä, jota kutsutaan väistämättömyydeksi, ilmaisee oikein, että on mahdotonta rakentaa karttaa, jossa jokainen neljästä kokoonpanosta puuttuu (nämä kokoonpanot koostuvat alueesta, jolla on kaksi naapuria, yksi kolmella, yksi neljällä ja yksi viidellä). Toinen käsite, vähennyskelpoisuus, saa nimensä Kempen pätevästä todisteesta, että jos on kartta, joka vaatii vähintään viisi väriä ja joka sisältää alueen, jossa on neljä (tai kolme tai kaksi) naapuria, niin siellä on oltava kartta, joka vaatii viittä värit pienemmälle alueelle. Kempen yritys todistaa viiden naapurimaiden alueen sisältävän kartan korvattavuus oli virheellinen, mutta se oikaistiin vuonna 1976 Kenneth Appelin ja Yhdysvaltojen Wolfgang Hakenin julkaisemassa todistusaineistossa. Niiden todisteet herättivät kritiikkiä, koska se edellytti 1936 erillisen tapauksen arviointia, joista jokaisessa oli peräti 500 000 loogista operaatiota. Appel, Haken ja heidän yhteistyökumppaninsa suunnittelivat ohjelmat, joiden avulla suuri digitaalinen tietokone pystyi käsittelemään näitä yksityiskohtia. Tietokone vaati tehtävän suorittamiseen yli 1000 tuntia, ja tuloksena oleva muodollinen todistus on useita satoja sivuja.
Eulerian syklit ja Königsbergin siltaongelma
Monigrafiikka G koostuu ei-tyhjästä pisteiden joukosta V (G) ja osajoukosta E (G) V: n (G) erillisten elementtien järjestämättömien parien joukosta, joiden taajuus f ≥ 1 on kiinnitetty kuhunkin pariin. Jos pari (x 1, x 2), jonka taajuus on f, kuuluu E (G), niin kärjet x 1 ja x 2 yhdistetään f reunoilla.
Usean kuvan G Eulerian-sykli on suljettu ketju, jossa jokainen reuna esiintyy tarkalleen kerran. Euler osoitti, että monigrafiikalla on Eulerian sykli vain silloin, kun se on kytketty (lukuun ottamatta erillisiä pisteitä) ja pariton asteen huippupisteiden lukumäärä on joko nolla tai kaksi.
Tämä ongelma nousi ensin seuraavalla tavalla. Pregel-joki, joka muodostuu sen kahden haaran yhtymäkohdasta, kulkee Königsbergin kaupungin läpi ja virtaa Kneiphofin saaren kummallakin puolella. Siltoja oli seitsemän, kuten kuviossa 6A esitetään. Kaupunkilaiset ihmettelivät, onko mahdollista käydä kävelyllä ja ylittää jokainen silta vain kerran. Tämä vastaa Eulerian-syklin löytämistä kuvan 6B monikerrokselle. Euler osoitti sen olevan mahdoton, koska parillisessa järjestyksessä on neljä huippua.
