Grafteori er det matematiske studiet av nettverk bestående av en samling punkter og koblinger. Et slikt nettverk kalles i matematikken en graf, og punktene kalles gjerne noder og koblingene for kanter. En graf må ikke forvirres med grafen til en funksjon – dette er to forskjellige konsepter.
grafteori
En graf med noder (svarte) og kanter (røde).
Historie og kjente problemer
Det königsbergske broproblemet fremstilt som en graf. Hver node (blå prikk) er et landområde, og hver kant (linje) er en bro.
Grafteorien har sin historiske opprinnelse sammen med topologien i Leonard Eulers løsning av det Köningsbergske broproblem i 1736. Euler beskrev byen Köningsberg – som nå heter Kaliningrad – og de syv 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 og dermed vise at det var ingen måte å gå en rundtur i byen der man kun krysset hver av de de syv bruene en gang.
Det Köningsbergske broproblem er en del av en klasse problemer som omhandler hvordan man kan reise mellom ulike steder på en optimal måte. Andre slike problemer er handelsreisendeproblemet, tretjenesteproblemet og det Kinesiske postmanproblemet.
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? Problemet ble løst i 1976 ved hjelp av grafteori og datamaskinberegninger og regnes som den første store matematiske formodningen løst via maskinassisterte metoder.
Bruksområder
Av
Romainbehar.
Lisens:
Falt i det fri (Public domain)
Begrepet «graf» ble først brukt av James Sylvester i en artikkel publisert i 1878, der han sammenligner matematiske systemer med molekyldiagrammer. Siden dette har grafteori vært viktig i: utviklingen av datastrukturer og internett innen datavitenskapen; syntaks- og semantikkanalyse innen ligvistikk; Feynman-diagrammer i fysikken; samt andre vitenskapelige grener som kjemi, sosialvitenskap og selvfølgelig matematikken selv.
I nyere tid er kanskje eksempelet med kunstig intelligens og maskinlæring mest fremtredende. I bunn og grunn er maskinlæring en graf, der man tolker en del av nodene som «input» og en del av nodene som «output». Mellom disse to gjøres mange beregninger basert på grafens struktur og algoritmens vekter.
Et annet kjent eksempel er Gustav Kirchoffs to lover for konservering av ladning og energi i elektriske kretser.
Les mer i Store norske leksikon
Fagansvarlig for Topologi
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.