Grafteori
Fra Wikipedia, den frie encyklopedi
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 hjørner med hverandre. Figuren viser et eksempel på en graf med ti hjørner og femten kanter, kjent som Petersen-grafen.
Formelt defineres en graf G som et par (V,E), der V er en ikke-tom mengde og E er en mengde bestående av undermengder av V med to elementer.
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.
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 et hjørne 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 hjørnet er det samme, men hvor alle andre hjørner 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 hjørnene til den ene grafen til hjørnene i den andre grafen, slik at to hjørner er naboer i den første grafen hvis og bare hvis de korresponderende hjørnene er naboer i den andre grafen.
[rediger] Fargelegging av grafer
Man fargelegger en graf når man tilegner hvert hjørne i grafen en farge slik at ingen nabohjørner 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 som et uløst problem.
