grafteori – Store norske leksikon (original) (raw)
En graf med noder (svarte) og kanter (røde).
Det königsbergske broproblemet fremstilt som en graf. Hver node (blå prikk) er et landområde, og hver kant (linje) er en bro.
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.
Kjente resultater
Selv om begrepet «graf» først ble brukt av James Sylvester i en artikkel publisert i 1878, har grafteorien sin historiske opprinnelse i Leonard Eulers løsning av det köningsbergske broproblemet i 1736. Dette regnes også som begynnelsen på fagområdet topologi.
Det köningsbergske broproblemet
Det köningsbergske 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öningsberg – 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.
Firefargeproblemet
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.
Bruksområder
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
- utviklingen av datastrukturer og internett
- syntaks- og semantikkanalyse innen lingvistikk
- Gustav Kirchoffs to lover for konservering av ladning og energi i elektriske kretser
- Feynman-diagrammer i fysikk
- kunstig intelligens og maskinlæring