Content-Length: 48490 | pFad | https://snl.no/grafteori
Det königsbergske broproblemet fremstilt som en graf. Hver node (blå prikk) er et landområde, og hver kant (linje) er en bro.
Kirchhoffs lover for elektriske kretser.
Grafteori er det matematiske studiet av nettverk, som består av en samling punkter og koblinger mellom punktene. Et slikt abstrakt nettverk kalles i grafteorien for en graf. Punktene kalles gjerne noder og koblingene for kanter.
En graf i grafteori er ikke det samme som grafen til en funksjon.
Begrepet «graf» ble første gang brukt av den britiske matematikeren James Sylvester i en artikkel publisert i 1878. Grafteori har imidlertid sin historiske opprinnelse enda tidligere, i sveitsiske Leonard Eulers løsning av det königsbergske broproblemet i 1736. Dette regnes også som begynnelsen på fagområdet topologi.
Det königsbergske broproblemet er en del av en klasse matematiske problemer som handler om hvordan man kan reise mellom ulike steder på best mulig måte.
Euler beskrev byen Königsberg – som nå heter Kaliningrad – og de sju broene som koblet de ulike delene av byen sammen, som en graf. Dette gjorde at han enklere kunne konstruere abstrakte matematiske resonnementer om denne grafen. Han greide dermed å vise at det var ingen måte å gå en rundtur i byen der man krysset hver av de sju broene nøyaktig én gang og kom tilbake til starten.
Andre lignende problemer er handelsreisendeproblemet, tretjenesteproblemet og det kinesiske postmann-problemet.
Et av de mest kjente resultatene fra grafteorien er det såkalte firefargeproblemet. Dette problemet kan formuleres på følgende måte: kan et hvilket som helst kart fargelegges med kun fire farger, slik at land med en felles landegrense alltid har ulik farge?
Firefargeproblemet ble løst i 1976 ved hjelp av grafteori og datamaskinberegninger. Dette regnes som den første store matematiske formodningen som ble løst med maskinassisterte metoder.
Ettersom en graf er en matematisk abstraksjon av et nettverk, har grafteori blitt flittig anvendt på problemer som omhandler analyse av data og hvordan informasjon beveger seg i et system. Grafteori er for eksempel viktig i:
Kommentarer
Kommentarer til artikkelen blir synlig for alle. Ikke skriv inn sensitive opplysninger, for eksempel helseopplysninger. Fagansvarlig eller redaktør svarer når de kan. Det kan ta tid før du får svar.
Du må være logget inn for å kommentere.