grafteori

Grafteorien henter sin terminologi og sine problemstillinger fra mange fagområder. Punkterne i en graf kan eksempelvis være atomerne i et molekyle, hvori to punkter er forbundet med en kant, når de to atomer har en direkte kemisk binding. I matematikken kan punkterne være de variable i et polynomium af \(n\) variable \(x_1, x_2, \cdots, x_n\), hvor to punkter \(x_i\) og \(x_j\) er forbundet med lige så mange kanter som det antal gange, \((x_i-x_j)\) går op i polynomiet. Punkterne kan også være aktiviteter (fx undervisningstimer eller eksaminer), hvor to punkter er forbundet med en kant, når de to aktiviteter ikke kan foregå samtidigt. Eller punkterne kan være computere i et netværk, hvor to punkter er forbundet med en kant, når de to computere kan kommunikere direkte med hinanden. Som et sidste eksempel kan punkterne være personer, hvor to punkter er forbundet med en kant, når de to personer er venner.

Grafteorien tog sin begyndelse i 1736, da L. Euler studerede problemet om broerne i Königsberg. Den moderne grafteori udvikledes i slutningen af 1800-tallet gennem arbejder af bl.a. G.R. Kirchhoff om elektriske netværk, af J.J. Sylvester om kemiske forbindelser, af den engelske matematiker Percy John Heawood (1861-1955) om farvning af landkort og af danskeren Julius Petersen om faktorisering af polynomier. Et teoretisk fundament blev etableret af den ungarske matematiker Dénes König (1884-1944), som i 1936 skrev den første lærebog i grafteori. König fremhævede Petersens resultater, bl.a. sætningen: I en graf, hvor alle punkter har den samme lige valens \(2k\), dvs. at der fra hvert punkt udgår præcis \(2k\) kanter, kan kanterne farves med \(k\) farver, så hver kant får en farve, og så hver farve forekommer præcis to gange ved hvert punkt. Grafteoriens vækst tog fart i sidste halvdel af 1900-tallet i forbindelse med udviklingen inden for operationsanalyse, netværksteori og teoretisk datalogi.

• kombinatorik
• diskret matematik
• Königsbergs broproblem