Anvendelser af grafteori
Plane grafer
En graf G siges at være plan, hvis den kan repræsenteres på et plan på en sådan måde, at toppunktene alle er forskellige punkter, kanterne er enkle kurver, og ingen to kanter møder hinanden undtagen ved deres terminaler. F.eks. Er K 4, den komplette graf på fire hjørner, plan, som figur 4A viser.
To grafer siges at være homomorfe, hvis begge kan opnås fra den samme graf ved underinddeling af kanter. For eksempel er graferne i figur 4A og figur 4B homeomorfe.
Km , n- grafen er en graf, som toppunktet kan opdeles i to undergrupper, det ene med m-hjørner og det andet med n-hjørner. Eventuelle to hjørner i den samme undergruppe er ikke nærliggende, mens andre to hjørner af forskellige undergrupper er tilstødende. Den polske matematiker Kazimierz Kuratowski i 1930 beviste følgende berømte teorem:
En nødvendig og tilstrækkelig betingelse for en graf G at være plan er, at den ikke indeholder en undergraf homeomorphic til enten K 5 eller K 3,3 vist i figur 5.
En elementær sammentrækning af en graf G er en transformation af G til en ny graf G 1, således, at to tilstødende knudepunkter u og vc af G er erstattet med en ny toppunkt w i G 1 og w er tilstødende i G 1 til alle vertices til som enten u eller υ er tilstødende i G. En graf G * siges at være en sammentrækning af G, hvis G * kan opnås fra G ved en række af elementære sammentrækninger. Følgende er en anden karakterisering af en plan graf på grund af den tyske matematiker K. Wagner i 1937.
En graf er plan, hvis og kun hvis den ikke kan samles med K 5 eller K 3,3.
Fire-farve kortproblemet
I mere end et århundrede undgik løsningen af kortfarveproblemet enhver analytiker, der forsøgte det. Problemet kan have vakt opmærksomhed fra Möbius, men den første skriftlige henvisning til det ser ud til at være et brev fra ene Francis Guthrie til sin bror, en elev af Augustus De Morgan, i 1852.
Problemet vedrører plane kort - det vil sige underinddelinger af flyet i ikke-overlappende regioner afgrænset af enkle lukkede kurver. På geografiske kort er det observeret empirisk, i så mange specielle tilfælde, som er blevet prøvet, at der højst er behov for fire farver for at farve regionerne, så to regioner, der deler en fælles grænse, altid farves forskelligt, og i visse tilfælde, hvor mindst fire farver er nødvendige. (Regioner, der kun mødes på et tidspunkt, såsom delstaterne Colorado og Arizona i USA, anses ikke for at have en fælles grænse). En formalisering af denne empiriske observation udgør det, der kaldes ”firefarvet teorem”. Problemet er at bevise eller modbevise påstanden om, at dette er tilfældet for hvert plane kort. At tre farver ikke vil være tilstrækkelige, demonstreres let, mens tilstrækkeligheden af fem farver blev bevist i 1890 af den britiske matematiker PJ Heawood.
I 1879 foreslog AB Kempe, en engelskmand, en løsning af firefarveproblemet. Selvom Heawood viste, at Kempes argument var mangelfuld, var to af dens koncepter frugtbare ved senere undersøgelse. En af disse, kaldet uundgåelighed, angiver korrekt umuligheden ved at konstruere et kort, hvor hver og en af fire konfigurationer er fraværende (disse konfigurationer består af et område med to naboer, en med tre, en med fire og en med fem). Det andet koncept, reducerbarheden, henter sit navn fra Kempes gyldige bevis for, at hvis der er et kort, der kræver mindst fem farver, og som indeholder et område med fire (eller tre eller to) naboer, så skal der være et kort, der kræver fem farver for et mindre antal regioner. Kempes forsøg på at bevise reducerbarheden af et kort, der indeholder et område med fem naboer, var fejlagtigt, men det blev rettet i et bevis, der blev offentliggjort i 1976 af Kenneth Appel og Wolfgang Haken fra De Forenede Stater. Deres bevis tiltrak en vis kritik, fordi det nødvendiggjorde evaluering af 1.936 forskellige sager, der hver involverede op til 500.000 logiske operationer. Appel, Haken og deres samarbejdspartnere udtænkte programmer, der gjorde det muligt for en stor digital computer at håndtere disse detaljer. Computeren krævede mere end 1.000 timer for at udføre opgaven, og det resulterende formelle bevis er flere hundrede sider langt.
Euleriske cykler og Königsberg-broproblemet
En multigraph G består af et ikke-tomt sæt V (G) af hjørner og en undergruppe E (G) af sættet med uordnede par af forskellige elementer af V (G) med en frekvens f ≥ 1 knyttet til hvert par. Hvis parret (x 1, x 2) med frekvens f hører til E (G), er sammenhøjninger x 1 og x 2 forbundet med f kanter.
En eulerisk cyklus af en multigraf G er en lukket kæde, hvor hver kant vises nøjagtigt en gang. Euler viste, at en multigraph besidder en eulerisk cyklus, hvis og kun hvis den er forbundet (bortset fra isolerede punkter), og antallet af vertikater med ulige grad er enten nul eller to.
Dette problem opstod først på følgende måde. Pregel-floden, dannet ved sammenløbet af dens to grene, løber gennem byen Königsberg og strømmer på hver side af øen Kneiphof. Der var syv broer, som vist i figur 6A. Beboerne spekulerede på, om det var muligt at gå en tur og krydse hver bro kun én gang. Dette svarer til at finde en eulerisk cyklus for multigrafen i figur 6B. Euler viste, at det var umuligt, fordi der er fire højdepunkter med ulige orden.
