Anvendelser av grafteori
Plan graf
En graf G sies å være plan hvis den kan være representert på et plan på en slik måte at toppunktene er forskjellige punkter, kantene er enkle kurver, og ingen to kanter møter hverandre bortsett fra ved terminalene. For eksempel er K 4, den komplette grafen på fire hjørner, plan, som figur 4A viser.
To grafer sies å være homomorfe hvis begge kan oppnås fra den samme grafen ved inndelinger av kanter. For eksempel er grafene i figur 4A og figur 4B homeomorfe.
K m, n- grafen er en graf som toppunktet kan deles inn i to undergrupper, det ene med m-hjørner og det andre med n-hjørner. Alle to hjørner av samme undergruppe er ikke tilstøtende, mens to toppunkt av forskjellige undergrupper er tilstøtende. Den polske matematikeren Kazimierz Kuratowski i 1930 beviste følgende berømte teorem:
En nødvendig og tilstrekkelig betingelse for en graf G for å være plan, er at den ikke inneholder en subgraf homøomorfiske til enten K 5 eller K 3,3 er vist i figur 5.
En elementær sammentrekning av en graf G er en transformasjon fra G til en ny graf G 1, slik at to hosliggende hjørner u og Uq G er erstattet med en ny verteks w i G 1 og w er tilstøtende i G 1 til alle vertekser for å som enten u eller υ er tilstøtende i G. En graf G * sies å være en sammentrekning av G hvis G * kan oppnås fra G ved en sekvens av elementære sammentrekninger. Følgende er en annen karakterisering av en plan graf på grunn av den tyske matematikeren K. Wagner i 1937.
En graf er plan hvis og bare hvis den ikke kan avtales med K 5 eller K 3,3.
Fire-fargekartproblemet
I mer enn et århundre unnvikte løsningen av det firefargede kartproblemet enhver analytiker som forsøkte det. Problemet kan ha vakt oppmerksomheten til Möbius, men den første skriftlige referansen til det ser ut til å være et brev fra ene Francis Guthrie til broren, en student av Augustus De Morgan, i 1852.
Problemet angår plane kart - det vil si underinndelinger av flyet i ikke-overlappende regioner avgrenset av enkle lukkede kurver. I geografiske kart er det observert empirisk, i så mange spesielle tilfeller som har blitt prøvd, at det på det meste er behov for fire farger for å fargelegge regionene slik at to regioner som deler en felles grense alltid farges annerledes, og visse tilfeller som minst fire farger er nødvendig. (Regioner som bare møtes på et tidspunkt, for eksempel delstatene Colorado og Arizona i USA, anses ikke å ha en felles grense). En formalisering av denne empiriske observasjonen utgjør det som kalles ”firfarges teorem.” Problemet er å bevise eller motbevise påstanden om at dette er tilfelle for hvert plane kart. At tre farger ikke vil være tilstrekkelig, er lett å demonstrere, mens tilskuddet til fem farger ble bevist i 1890 av den britiske matematikeren PJ Heawood.
I 1879 foreslo AB Kempe, en engelskmann, en løsning på firfarges problemet. Selv om Heawood viste at Kempes argumentasjon var mangelfull, viste to av konseptene seg fruktbare ved senere etterforskning. En av disse, kalt uunngåelig, sier riktig umuligheten av å konstruere et kart der hver av fire konfigurasjoner er fraværende (disse konfigurasjonene består av et område med to naboer, en med tre, en med fire og en med fem). Det andre konseptet, det med reduserbarhet, tar navnet fra Kempes gyldige bevis på at hvis det er et kart som krever minst fem farger og som inneholder et område med fire (eller tre eller to) naboer, må det være et kart som krever fem farger for et mindre antall regioner. Kempes forsøk på å bevise reduserbarheten av et kart som inneholder et område med fem naboer var feil, men det ble utbedret i et bevis publisert i 1976 av Kenneth Appel og Wolfgang Haken i USA. Beviset deres vakte en del kritikk fordi det nødvendiggjorde evaluering av 1 936 forskjellige saker, som hver involverte så mange som 500 000 logiske operasjoner. Appel, Haken og deres samarbeidspartnere utviklet programmer som gjorde det mulig for en stor digital datamaskin å håndtere disse detaljene. Datamaskinen krevde mer enn 1000 timer for å utføre oppgaven, og det resulterende formelle beviset er flere hundre sider langt.
Euleriske sykluser og Königsbergbro-problemet
En multigraph G består av et ikke-tomt sett V (G) av hjørner og et delmengde E (G) av settet med uordnede par av distinkte elementer av V (G) med en frekvens f ≥ 1 festet til hvert par. Hvis paret (x 1, x 2) med frekvens f tilhører E (G), blir sammenhengene x 1 og x 2 forbundet med f kanter.
En eulerisk syklus av en multigraf G er en lukket kjede der hver kant vises nøyaktig en gang. Euler viste at en multigraf besitter en eulerisk syklus hvis og bare hvis den er koblet til (bortsett fra isolerte punkter) og antall toppunkt med ulik grad er enten null eller to.
Dette problemet oppstod først på følgende måte. Pregelelven, dannet av samløpet av de to grenene, renner gjennom byen Königsberg og renner på hver side av øya Kneiphof. Det var syv broer, som vist i figur 6A. Beboerne lurte på om det var mulig å gå en tur og krysse hver bro bare én gang. Dette tilsvarer å finne en eulerisk syklus for multigrafen i figur 6B. Euler viste at det var umulig, fordi det er fire hjørner med merkelig orden.
