Grafteori

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.Goodrich, Michael T./ Tamassia, Roberto: Data Structures & Algorithms in Java. John Wiley & Sons, Inc. 2006. Grafer og behandling av grafer er viktige verktøy i mange hverdagslige problemstillinger som f.eks. ruteplanlegging, datanettverk og design av mikrobrikker.

Opprinnelsen til grafteori anses for å være en artikkel publisert av Leonhard Euler i 1736, som tok for seg problemet Broene i Königsberg.

 Grafteoretiske begreper 
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 kanter. Hva slags objekter man lar elementene i  være, gir opphav til ulike slags grafer. I en simpel urettet graf er kantene en 2-mengde  der  angir at grafen inneholder en kant mellom nodene  og . Siden mengder ikke kan inneholde to av samme objekt, medfører dette at en simpel graf ikke har multiple kanter. I en simpel rettet graf består kantene av ordnede par. Hvis en rettet graf inneholder kanten  angir at det er en kant fra node  til node . 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. Eksempler på grafer som er ikke-planare, er  og .

To noder  er naboer hvis de er forbundet med en kant. En kant er insident til nodene den forbinder. 

En tur i en graf er en følge av noder i rekkefølge, det vil si at hvert ledd i følgen er nabo med det foregående og etterfølgende leddet i følgen i grafen. En løype er en tur hvor hver kant besøkes høyst én gang. En sti er en løype hvor hver node besøkes maksimalt én gang. En sykel er en sti der første og siste ledd i stien er lik hverandre.

En graf er sammenhengende dersom for alle par av noder i grafen, så finnes det en sti mellom dem.

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.

Korteste vei
Å 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.

Dijkstras algoritme er en grådig algoritme som kan brukes for å finne korteste vei i en vektet graf uten negative kanter.Dijkstra, Edsger W.: A note on two problems in connexion with graphs. In Numerische Mathematik 1 (1959), S. 269–271. 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.Johnsen, Einar Broch: Grafer II . Forelesningsslides INF2220 høsten 2008. Universitetet i Oslo. 

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ø.

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).

Minimalt spenntre

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.

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.

Fargelegging av grafer
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
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.Johnsen, Einar Broch: Grafer . Forelesningsslides INF2220 høsten 2008. Universitetet i Oslo.

Referanser


Kategori:Informatikk