Graafiateooria rakendused
Tasapinnalised graafikud
Graafi G peetakse tasapinnaliseks, kui seda saab tasapinnal kujutada nii, et kõik tipud on selgelt eristatavad punktid, servad on lihtsad kõverad ja kaks serva ei vasta üksteisele, välja arvatud nende otstes. Näiteks on K 4, nelja tipu täielik graaf, tasapinnaline, nagu näitab joonis 4A.
Kaks graafi on homeomorfsed, kui mõlemad graafid on võimalik saada samast graafist servade alajaotuse teel. Näiteks joonistel 4A ja 4B olevad graafikud on homomorfsed.
K m, n graafik on graaf, mille tippude kogumi saab jagada kaheks alamhulgaks, millest üks koosneb m tipust ja teine n tipust. Sama alamhulga kaks tippu ei ole külgnevad, samas kui erinevate alamhulkade kaks tippu on külgnevad. Poola matemaatik Kazimierz Kuratowski tõestas 1930. aastal järgmise kuulsa teoreemi:
Graafi G tasapinnaliseks vajalikuks ja piisavaks tingimuseks on, et see ei sisalda joonisel 5 näidatud alamgraafi homeomorfset väärtust K 5 või K 3,3.
Graafi G elementaarne kokkutõmbumine on G teisendus uueks graafiks G 1, nii et G kaks kõrvutiasetsevat tippu u ja υ asendatakse uue tipuga w G 1-s ja w on G 1-s kõrvuti kõigi tippudega mis kas u või υ on G-ga külgnevad. Graaf G G on G kokkutõmbumine, kui G * saab G-st elementaarsete kokkutõmmete jada abil. Järgnev on veel üks tasapinnalise graafiku iseloomustus, mis tuleneb saksa matemaatiku K. Wagneri 1937. aastast.
Graafik on tasapinnaline siis ja ainult siis, kui see ei ole kokkusurutav K 5 või K 3,3-ga.
Nelja värvi kaardi probleem
Juba enam kui sajandi vältel lahendas neljavärvilise kaardi probleem kõik analüütikud, kes seda proovisid. Võimalik, et probleem on pälvinud Möbiuse tähelepanu, kuid esimene kirjalik viide sellele näib olevat ühe Francis Guthrie kiri tema vennale, Augustus De Morgani õpilasele, 1852. aastal.
Probleem on seotud tasapinnaliste kaartidega - st tasapinna alajaotustega mittekattuvateks piirkondadeks, mis on piiratud lihtsate suletud kõveratega. Geograafilistel kaartidel on empiiriliselt täheldatud, nii paljudel erijuhtudel kui on proovitud, et piirkondade värvimiseks on vaja maksimaalselt nelja värvi, nii et kahte ühist piiri jagavat piirkonda värvitakse alati erinevalt ja teatud juhtudel on vaja vähemalt nelja värvi. (Piirkondi, mis kohtuvad ainult ühes punktis, näiteks Colorado osariigid ja Arizona USA-s, ei peeta ühiseks piiriks). Selle empiirilise vaatluse vormistamine moodustab nn neljavärvilise teoreemi. Probleem on tõestada või ümber lükata väide, et see kehtib kõigi tasapinnaliste kaartide kohta. Kolmest värvitoonist ebapiisavus on hõlpsasti tõestatav, samas kui viie värvi piisavust tõestas 1890. aastal Briti matemaatik PJ Heawood.
1879. aastal pakkus inglane AB Kempe välja lahendus neljavärvi probleemile. Ehkki Heawood näitas, et Kempe argument oli puudulik, osutusid selle kaks mõistet hilisemas uurimisel viljakaks. Neist üks, mida nimetatakse vältimatuks, väidab õigesti, et on võimatu konstrueerida kaarti, kus puudub igas neljast konfiguratsioonist (need koosseisud koosnevad piirkonnast, kus on kaks naabrit, üks kolmega, üks neljaga ja üks viiest). Teine mõiste - redutseeritavus - pärineb Kempe kehtivast tõestusest, et kui on kaart, mis nõuab vähemalt viit värvi ja mis sisaldab piirkonda, kus on neli (või kolm või kaks) naabrit, siis peab olema ka kaart, mis nõuab viit värvid väiksema arvu piirkondade jaoks. Kempe'i katse tõestada viie naabriga piirkonda sisaldava kaardi loetavust oli ekslik, kuid see parandati tõendis, mille avaldasid 1976. aastal Ameerika Ühendriikide Kenneth Appel ja Wolfgang Haken. Nende tõend pälvis teatavat kriitikat, kuna see tingis vajaduse hinnata 1936 erinevat juhtumit, millest igaüks hõlmas koguni 500 000 loogilist operatsiooni. Appel, Haken ja nende kaastöötajad kavandasid programme, mis võimaldasid suurel digitaalarvutil neid detaile käsitleda. Arvutil kulus ülesande täitmiseks rohkem kui 1000 tundi ja sellest tulenev ametlik tõend on mitusada lehekülge pikk.
Euleri tsüklid ja Königsbergi silla probleem
Mitmikgraaf G koosneb tippude mittetühjast hulgast V (G) ja V (G) eraldiseisvate elementide järjestamata paaride komplektist A (G), mille sagedus f ≥ 1 on ühendatud iga paari külge. Kui paar (x 1, x 2) sagedusega f kuulub E (G), siis tipud x 1 ja x 2 on ühendatud f servadega.
Mitmegraafilise G Euleri tsükkel on suletud ahel, milles iga serv on täpselt üks kord. Euler näitas, et multigraaf omab Euleri tsüklit ainult siis, kui see on ühendatud (peale isoleeritud punktide) ja paaritu kraadi tippude arv on kas null või kaks.
Esmalt tekkis see probleem järgmisel viisil. Pregeli jõgi, mis on moodustatud selle kahe haru ühinemisest, kulgeb läbi Königsbergi linna ja suubub mõlemal pool Kneiphofi saart. Seal oli seitse silda, nagu on näidatud joonisel 6A. Linnarahvas mõtiskles, kas on võimalik jalutada ja ületada igat silda ainult üks kord. See on samaväärne joonise 6B multigraafi jaoks Euleri tsükli leidmisega. Euler näitas, et see on võimatu, kuna paaritu järjekorra tippe on neli.
