From Wikipedia, the free encyclopedia
Grafteori er en gren i matematikk og informatikk der man studerer egenskapene til grafer. Grafer er matematiske strukturer som brukes til å lage modeller for parvise relasjoner mellom objekter. I informatikken regnes graf som en abstrakt datastruktur, en teoretisk struktur som kan implementeres på ulike måter. Studier av algoritmer som behandler grafer er en viktig disiplin med mange praktiske anvendelser, i dag er dette i stor grad knyttet mot moderne datateknikk, men slike algoritmer var også utviklet før den digitale tidsalderen.[1] Grafer og behandling av grafer er viktige verktøy i mange hverdagslige problemstillinger som f.eks. ruteplanlegging, datanettverk og design av mikrobrikker.
| Eksempelgrafer | ||
|---|---|---|
 | ||
| Planar | Ikke planar | |
 |
 | |
 |
 | |
Opprinnelsen til grafteori anses for å være en artikkel publisert av Leonhard Euler i 1736, som tok for seg problemet Broene i Königsberg.
En graf består av en mengde noder (også kalt hjørner), og en mengde kanter, der hver kant forbinder to noder med hverandre. Figuren ovenfor viser et eksempel på en graf med ti noder og femten kanter, kjent som Petersen-grafen.
Formelt defineres en graf som et par , der er en ikke-tom mengde med noder og er en mengde med nodepar der angir at grafen inneholder en kant mellom nodene u og v. Dette er en urettet graf. I en rettet graf går kantene bare en vei. Hvis en rettet graf inneholder kanten angir at det er en kant fra node u til node v, men ikke nødvendigvis den andre veien. Slike grafer blir gjerne tegnet med piler mellom nodene.
En graf er simpel, hvis det aldri er mer enn én kant mellom to gitte noder, og hvis ingen kanter forbinder en node med seg selv. En slik kant kalles en løkke (loop). En graf som inneholder en løkke, eller noder som er forbundet med mer enn en kant, kalles en multigraf.
En planar graf er en graf som kan tegnes i planet (eller ekvivalent, på en kuleoverflate) slik at ingen kanter krysser hverandre. Grafer som ikke er planare, er og .
To noder er naboer hvis de er forbundet med en kant. En kant er insident til nodene den forbinder.
En vei i en graf består av en mengde kanter i rekkefølge, slik at to på hverandre følgende kanter alltid har en node felles. En sti er en vei hvor hver node besøkes høyst én gang. En sykel er en vei hvor det første og det siste noden er det samme, men hvor alle andre noder opptrer høyst én gang.
En graf er sammenhengende hvis ethvert par av noder er forbundet til hverandre av en sti.
To grafer er isomorfe hvis det finnes en avbildning fra nodene til den ene grafen til nodene i den andre grafen, slik at to noder er naboer i den første grafen hvis og bare hvis de korresponderende nodene er naboer i den andre grafen.
Graden til en node er antall kanter som starter eller slutter i denne noden. Vanligvis er dette antall naboer til denne noden, men en løkke øker graden med 2. For rettede grafer skiller vi mellom inngrad, som er antall kanter som går til denne noden, og utgrad, som er antall kanter som går fra denne noden.
I en regulær graf av grad n, har alle nodene grad n.
I en komplett graf, er alle nodene direkte forbundet med hverandre. Hvis grafen har N noder, er dette en regulær graf av grad N-1.
Å finne korteste vei i en graf er en grunnleggende operasjon som trengs i mange sammenhenger f.eks. for å planlegge en reiserute.
I en uvektet graf kan man finne korteste vei fra en bestemt node ved å merke alle nodene avstand 1. Deretter tar man alle de umerkede nodene som har avstand 2 og så videre. Alle nodene blir da merket med korteste tilgjengelige rute. Tidsbruken til denne algoritmen øker eksponensielt med antall noder. En mer effektiv metode er å bruke en "kø" der man først setter inn den noden man starter på. Så lenge køen ikke er tom tar man ut første node og legger nodene som kommer etter denne sist i køen. Nodene kommer da i riktig rekkefølge med en lineær tidsbruk.[2]
Dijkstras algoritme er en grådig algoritme som kan brukes for å finne korteste vei i en vektet graf uten negative kanter.[3] Algoritmen er mye brukt i transport-, tele- og datanettverk.
Fremgangsmåten er at alle noder merkes med en avstand og en peker til noden man kom fra for å få denne avstanden. I tillegg merkes hver node med kjent eller ukjent. Man begynner med å sette alle nodene til avstand uendelig og "ukjent". Noden man begynner med får avstand 0. Først merkes alle nodene rundt startnoden med avstand og deretter tar man utgangspunkt i den noden med lavest avstand til start. Denne merkes som kjent og kan deretter ikke endres. Man merker så avstand til start på nodene rundt den nye kjente og det merkes hvilken node man kom fra. Hvis algoritmen finner en ny og kortere vei til en node må den merkes om med ny avstand og ny bakoverpeker. Når alle nodene er merket kjent er hele grafen kartlagt.[4]
Dijkstras algoritme øker eksponensielt med antall noder. Dette gir god ytelse for grafer med mange kanter og få noder. I grafer med få kanter og mange noder kan ytelsen økes ved å legger noder under behandling i en prioritetskø.[4]
Algoritmen kan håndtere negative kanter hvis man håndterer noder som oppdateres med en kø istedenfor å merke noder med kjent og ukjent. Dette minker imidlertid algoritmens effektivitet vesentlig. Man må også gardere seg mot negative sykler i grafen (som fører til evige løkker).
Et minimalt spenntre er en sammenbinding av alle nodene i en graf med minimal lengde på kantene. Et praktisk eksempel kan være å legge kabel mellom hus i et boligområde – hvor skal kablene gå for at den samlede strekningen skal bli så kort som mulig?
Prims algoritme er en grådig algoritme som begynner i en tilfeldig node og fortsetter med å velge veien til den noden som er nærmest en valgt node helt til alle noder er valgt.[4]
Kruskals algoritme er en grådig algoritme som tar utgangspunkt i de kantene i grafen som har lavest vekt. Først knytter den sammen nodene som det er kortest mellom, deretter nodene som er nest kortest og så videre. Algoritmen må hele tiden sjekke at det ikke oppstår sykler, hvis det allerede finnes en vei fra en node til en annen skal den ikke knyttes sammen på flere måter.[4]
Man fargelegger en graf når man tilegner hver node i grafen en farge slik at ingen nabonoder har samme farge. Gitt en graf er det et mål å bruke så få farger totalt som mulig slik at det fortsatt går an å fargelegge grafen. Det er enkelt å vise at det alltid går an å fargelegge en planar graf med maksimalt 5 farger totalt. Et kjent problem kalt 4-fargeteoremet sier at det alltid går an å fargelegge en planar graf med maksimalt 4 farger totalt. Dette er blitt bevist ved hjelp av datamaskiner som har tatt for seg alle mulige typer planare grafer, men er aldri blitt bevist med enklere metoder og regnes derfor idag fortsatt av noen som et uløst problem.
Topologisk sortering vil si å lage en lovlig rekkefølge av alle elementer i en graf med rettede kanter. En svært enkel algoritme for å gjøre dette er å finne en node med null inn-kanter, føre den opp i lista/utskriften, fjerne den og oppdatere inngraden til nodene den peker mot for så å gjenta til det ikke er flere noder igjen. Dette er imidlertid svært lite effektivt, man risikerer eksponensiell økning i tidsbruken med økende datamengde. En forbedret algoritme tar ut alle nodene med inngrad null og setter dem i en "boks". Den tar så en node fra boksen, registrerer noden i utskriften, fjerner den fra grafen og oppdaterer inngraden til nodene rundt. Den sjekker så om noen av nodene rundt har fått inngrad null, og hvis de har det settes de inn i boksen. Så tar den for seg neste node i boksen.[2]
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
