Grafteori

Grafteori er den greina av matematikk der ein studerer eigenskapane til grafar. Ein graf består av ei mengd hjørne eller nodar, og ei mengd kantar, der kvar kant bind saman to hjørne. På figuren er eit døme på ein graf med fem nodar og ti kantar.

Formelt er det vanleg å definera ein graf ${\displaystyle G}$ som eit par ${\displaystyle (V,E)}$, der ${\displaystyle V}$ er ei ikkje-tom mengd med nodar, og ${\displaystyle E}$ er ei mengd med undermengder av ${\displaystyle V}$ der kvar undermengd har to element. Strengt tatt er grafen desse mengdene av hjørne og kantar – ikkje teikninga av dei.

Grafteori vart grunnlagd av Leonhard Euler då han publiserte ein artikkel om problemet «Bruene i Königsberg» i 1736.