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. Broerne i Königsberg, således som de er illustreret i L. Eulers artikel fra 1736. Problemet var, om man kunne gå en rundtur, således at hver bro blev passeret netop én gang. Situationen kan repræsenteres med en graf. Den har fire punkter og syv kanter. Punkternes valenser er 3, 3, 3 og 5. Eulers generelle resultat var, at der findes en løsning, netop når alle valenser i den tilsvarende graf er lige. Da dette ikke er tilfældet for broerne i Königsberg, har problemet ingen løsning.
Grafteori. Petersens graf består af ti punkter og 15 kanter. Den er 3-regulær, dvs. at der fra hvert punkt udgår præcis tre kanter. Petersen konstruerede grafen i 1898 som et eksempel på, at man ikke altid i en 3-regulær graf kan farve kanterne med tre farver, så hver kant får én farve, og så hver farve forekommer netop én gang ved hvert punkt.
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.
Læs mere i Den Store Danske
Fagansvarlig for Geometri
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.