Grafteori

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. På figuren er et eksempel på en graf med fem hjørner og åtte kanter.

graf.png

Formelt er det vanlig å definere 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.

Grafteori ble grunnlagt av Leonhard Euler i 1736 da han publiserte en artikkel om problemet Broene i Königsberg.

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.

Matematikk

Gourt Home::Gourt :: Grafteori