IT-lexikon › Programmering › Grafteori

Grafteori

Programmering In English → Uppdaterad: 2026-05-24

Matematisk studie av grafer (noder + kanter). Leonhard Euler grundade 1736 med Königsbergs sju broar-problemet. Bas för all modern algoritm- och nätverksteori.

Grenar: planar grafer (kan ritas utan kant-korsningar), färgningsteori (4-färgsatsen 1976), spektral grafteori (egenvärden av adjacency-matriser), random grafer (Erdős–Rényi). Praktiska konsekvenser: sociala nätverksanalys, Google PageRank (1998 — eigenvektor av webbens länkmatris), epidemiologi, neurala nätverk. Erdős nummer mäter hur många mellan-författarsteg du är från Paul Erdős.

← Tillbaka till lexikonet