Grafteori er et matematisk fagområde inden for kombinatorik. En graf består af punkter og kanter; hver kant i grafen forbinder to af grafens punkter. En graf illustreres ofte ved at tegne hvert punkt som en lille cirkel og hver kant som en linje eller kurve, der forbinder de to tilsvarende punkter. I den rene grafteori er kurvernes geometri uden betydning, idet kun rent kombinatoriske egenskaber studeres.
grafteori
Grafteori i mange fagområder
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.
Grafteori i historisk perspektiv
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.
Kommentarer
Kommentarer til artiklen bliver synlige for alle. Undlad at skrive følsomme oplysninger, for eksempel sundhedsoplysninger. Fagansvarlig eller redaktør svarer, når de kan.
Du skal være logget ind for at kommentere.