• Artiklens indhold er godkendt af redaktionen

grafteori

Oprindelig forfatter BT Seneste forfatter Redaktionen

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. 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, 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.

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 x1,x2,...,xn, hvor to punkter xi og xj er forbundet med lige så mange kanter som det antal gange, (xi−xj) 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-t. gennem arbejder af bl.a. G.R. Kirchhoff om elektriske netværk, af J.J. Sylvester om kemiske forbindelser, af P.J. Heawood om farvning af landkort og af danskeren Julius Petersen om faktorisering af polynomier. Et teoretisk fundament blev etableret af den ungarske matematiker D. König, 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 har taget fart i sidste halvdel af 1900-t. i forbindelse med udviklingen inden for operationsanalyse, netværksteori og teoretisk datalogi.

Annonce

Referér til denne tekst ved at skrive:
Bjarne Toft: grafteori i Den Store Danske, Gyldendal. Hentet 4. april 2020 fra http://denstoredanske.dk/index.php?sideId=85299