Grafteori
Fra Wikipedia, den frie encyklopedi
| Eksempelgrafer | ||
|---|---|---|
| Planar | Ikke planar | |
|
 |
|
|
|
|
Grafteori er den grenen av matematikk hvor man studerer egenskapene til grafer.
En graf består av en mengde hjørner eller noder, og en mengde kanter, der hver kant forbinder to noder med hverandre. Figuren viser et eksempel på en graf med ti noder og femten kanter, kjent som Petersen-grafen.
Formelt defineres en graf G som et par (V,E), der V er en ikke-tom mengde med noder og E er en mengde med nodepar 
der {u,v} 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 (u,v) 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.
Opprinnelsen til grafteori ansees for å være en artikkel publisert av Leonhard Euler i 1736, som tok for seg problemet Broene i Königsberg.
[rediger] Grafteoretiske begreper
En graf er simpel, hvis det aldri er mer enn én kant mellom to gitte hjørner, og hvis ingen kanter forbinder et hjørne med seg selv. En slik kant kalles en loop. En graf som inneholder en loop, eller hjørner 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 K3,3 og K5
To hjørner er naboer hvis de er forbundet med en kant. En kant er insident til hjørnene 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 hvert hjørne 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 hjørner 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 loop ø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
[rediger] 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.
