Tillämpningar av grafteori
Plana diagram
En graf G sägs vara plan om den kan representeras på ett plan på ett sådant sätt att topparna är alla distinkta punkter, kanterna är enkla kurvor och inga två kanter möter varandra utom vid deras terminaler. Till exempel, K 4 är, den fullständiga grafen på fyra hörn, plan, som figur 4A visar.
Två grafer sägs vara homeomorfa om båda kan erhållas från samma graf genom underindelningar av kanter. Exempelvis är graferna i figur 4A och figur 4B homeomorfa.
Km , n- diagrammet är ett diagram för vilket vertexuppsättningen kan delas upp i två underuppsättningar, en med m-hörn och den andra med n-hörn. Två vertikaler i samma delmängd är inte intill varandra, medan två vertikaler med olika undergrupper är intill varandra. Den polska matematikern Kazimierz Kuratowski 1930 bevisade följande berömda teorem:
Ett nödvändigt och tillräckligt villkor för en graf G att vara plan är att den inte innehåller en subgraf homeomorfa till antingen K 5 eller K 3,3 som visas i figur 5.
En elementär sammandragning av en graf G är en transformation av G till en ny graf G 1, så att två närliggande hörn u och v av G ersätts med en ny toppunkt w i G 1 och w är intill varandra i G 1 till alla hörn till som antingen u eller υ gränsar till G. En graf G * sägs vara en sammandragning av G om G * kan erhållas från G genom en sekvens av elementära sammandragningar. Följande är en annan karaktärisering av ett plant diagram på grund av den tyska matematikern K. Wagner 1937.
En graf är plan om och bara om den inte är kontraherbar med K 5 eller K 3,3.
Det fyrfärgiga kartproblemet
I mer än ett århundrade undanröjde lösningen av fyrfärgskartproblemet varje analytiker som försökte det. Problemet kan ha väckt Möbius uppmärksamhet, men den första skriftliga hänvisningen till det verkar vara ett brev från en Francis Guthrie till sin bror, en student av Augustus De Morgan, 1852.
Problemet gäller plana kartor - det vill säga underindelningar av planet i områden som inte överlappar varandra begränsade av enkla stängda kurvor. I geografiska kartor har det observerats empiriskt, i så många speciella fall som har testats, att det som mest behövs fyra färger för att färga regionerna så att två regioner som delar en gemensam gräns alltid färgas annorlunda, och i vissa fall där minst fyra färger är nödvändiga. (Regioner som bara möts vid en punkt, till exempel delstaterna Colorado och Arizona i USA, anses inte ha en gemensam gräns). En formalisering av denna empiriska observation utgör det som kallas ”fyrafärgsteoremet.” Problemet är att bevisa eller motbevisa påståendet att detta är fallet för varje plan karta. Att tre färger inte kommer att räcka visas lätt, medan tillräckligt med fem färger bevisades 1890 av den brittiska matematikern PJ Heawood.
År 1879 föreslog AB Kempe, en engelskman, en lösning av fyrfärgsproblemet. Även om Heawood visade att Kempes argument var bristfälligt, visade sig två av dess begrepp vara fruktbara i senare utredning. En av dessa, kallad oundviklighet, säger korrekt omöjligt att konstruera en karta där var och en av fyra konfigurationer är frånvarande (dessa konfigurationer består av ett område med två grannar, en med tre, en med fyra och en med fem). Det andra konceptet, reducerbarheten, tar sitt namn från Kempes giltiga bevis på att om det finns en karta som kräver minst fem färger och som innehåller en region med fyra (eller tre eller två) grannar, måste det finnas en karta som kräver fem färger för ett mindre antal regioner. Kempes försök att bevisa reducerbarheten av en karta som innehåller en region med fem grannar var felaktig, men den korrigerades i ett bevis som publicerades 1976 av Kenneth Appel och Wolfgang Haken i USA. Deras bevis väckte en del kritik eftersom det krävde utvärdering av 1 936 olika fall, var och en med så många som 500 000 logiska operationer. Appel, Haken och deras kollaboratörer utformade program som gjorde det möjligt för en stor digital dator att hantera dessa detaljer. Datorn krävde mer än 1 000 timmar för att utföra uppgiften, och det resulterande formella beviset är flera hundra sidor långt.
Euleriska cykler och Königsbergbro-problemet
En multigraf G består av en icke-tom uppsättning V (G) vertikaler och en delmängd E (G) av uppsättningen av oordnade par av distinkta element av V (G) med en frekvens f> 1 fäst vid varje par. Om paret (x 1, x 2) med frekvensen f tillhör E (G), sammanfogas vertikalerna x 1 och x 2 av f-kanterna.
En eulersk cykel av en multigraf G är en stängd kedja där varje kant visas exakt en gång. Euler visade att en multigraf har en eulerisk cykel om och bara om den är ansluten (bortsett från isolerade punkter) och antalet vertikaler med udda grader är antingen noll eller två.
Detta problem uppstod först på följande sätt. Floden Pregel, som bildas av sammanflödet av dess två grenar, rinner genom staden Königsberg och rinner på vardera sidan av ön Kneiphof. Det fanns sju broar, som visas i figur 6A. Stadsborna undrade om det var möjligt att gå en promenad och korsa varje bro en gång bara en gång. Detta motsvarar att hitta en eulersk cykel för multigrafen i figur 6B. Euler visade att det var omöjligt eftersom det finns fyra vertikaler med udda ordning.
