Inden du begynder at tænke over, hvad en graf er, må du hellere få en definition. En graf består af en række knuder (eng. nodes) som er forbundne ved hjælp af kanter (eng. edges).

Der er ingen begrænsning på om to knuder er forbundne med mere end en kant. Antallet af kanter en knude har, omtales som knudens valens.

En kæde danner du ved at se på en række forbundne kanter. Det betyder, at du skal kunne følge en kæde med en blyant uden af løfte denne fra papiret.

En vigtig type graf er den sammenhængende graf. Her kan du komme fra en knude til en anden ved hjælp af en kæde.

Grafen fortæller ikke om placeringen af knuderne i et fysisk rum. Med andre ord, grafen kan være en meget abstrakt model af virkeligheden.

Grafteori er en meget gammel gren af matematikken. Den tyske matematiker Leonard Euler udvikler i 1736 de første elementer af grafteorien. Anekdoten er, at Euler ønskede at beskrive sin aftentur rundt i hjembyens gader.

Leonars Euler ville engang i 1730’erne ud og gå en tur, det udviklede sig til de første elementer i grafteorien - og den dag i dag hedder en sammenhængende graf en Euler-tur.

Hvor finder du grafer?

Grafteori er en del af matematikken – det område som ofte omtales som »diskret matematik«. Diskret matematik handler om regning med hele tal, mængdelære og altså også grafer. Det er vigtig at forstå, at en graf i denne artikel ikke er en tegning af en funktion i et koordinatsystem – det er et helt andet emne.

Du finder grafer overalt i din hverdag. Et netværk af computere, switches, printer og andet udstyr kan beskrives som en graf. Hvert stykke hardware kan opfattes som en knude, mens netværkskablerne er kanterne i grafen.

Tænker du i et større perspektiv, kan du se hele internettet som en stor graf. Alle computere er i princippet forbundet – men det behøver ikke at være direkte.

Det er også muligt at beskrive molekyler som grafer. Atomerne er forbundne efter særlige (kemiske) regler og danner på en måde grafer. Forbindelserne mellem atomerne omtales i kemien som kemiske bindinger, og hvert grundstof har en fast valens (kemikere kalder det faktisk også valens – selvom de ikke altid tænker i grafteori).

Du udgør også selv en knude i en graf. Forbindelserne i denne graf er relationerne til andre mennesker (familie, venner, kolleger, og så videre). En sådan graf omtales ofte som dit sociale netværk. Du har måske en gang fået et nyt job gennem dit netværk (»en ven af en ven«) - i sådan en situation har du brugt en kæde i din personlige graf.

Euler-tur

Tilbage til Eulers aftenture. Euler ville gerne gå en tur, men ville kun gå en gang ad samme gade. Det kræver planlægning, og grafteori kan hjælpe ham. Oversat til grafteori, ønsker Euler at finde en kæde, som indeholder hver kant én gang – og kun en gang! Kæden omtales som en Euler-kæde eller Euler-tur.

Som du hurtig kan indse, skal grafen være sammenhængende, men det er ikke nok. Euler finder heldigvis løsningen: En sammenhængende graf har en Euler-tur, hvis antallet af knuder med ulige valens er 0 eller 2. Men det betyder ikke, at Euler ender samme sted, som han begyndte på sin aftentur.

DAG

Der findes forskellige typer grafer. En af de vigtigste er DAG (Directed Acyclic Graph). I en DAG har kanterne orientering, det vil sige; en kant siges at gå fra en knude til en anden. Du kan tænke på det som en ensrettet gade. For at være grafen acyklisk, må der ikke være en kæde, som begynder og slutter samme sted.

I din computer finder du et eksempel på en DAG: Filsystemet. Din harddisk er organiseret i et træ, hvor bladene er filer og grenene er foldere. Det er en særlig udgave af en DAG.

Er du Linux- eller UNIX-bruger (herunder Mac OS X), kender du til symbolske links på filsystemet. Et symbolsk link bryder egentlig træstrukturen, og dit filsystem får karakter af en graf.

Kommer du til at bryde det acykliske med et symbolsk link (og antagelsen om at filsystemet er en DAG), vil der sikkert være en eller flere applikationer, som ender i en uendelig løkke.

DAG finder du også i anvendelse andre steder i din computer. Bruger du Linux, vil du sikkert have set beskeden »calculating dependencies« eller »udregner afhængigheder« som forberedelse til installation eller opdatering af en applikation.

De fleste Linux-distributioner indeholder i dag information, om hvilke pakker applikationen afhænger af. Hver af disse pakker kan afhænge af andre pakker og så videre. En DAG er perfekt til at repræsentere afhængigheder.

Knuderne er de enkelte pakker, og orientering af kanterne viser, hvilke pakker/knuder en pakke/knude afhænger af. For at udregne rækkefølgen for installationen, så skal den pakke, som ikke afhænger af andre, installeres først, kan du bruge en topologisk sortering.

Det lyder nok eksotisk, men algoritmen er ganske enkel at implementere. Du finder et eksempel på en implementering i Javascript på de sidste sider af artiklen.

Netværk

Netværk er en af de vigtigste anvendelser af grafteori. Betegnelsen netværksanalyse (eng. network analysis) vil du høre ofte i den forbindelse. Det er ikke kun computernetværk, som kan beskrives ved hjælp af grafer, vand- og kloakledninger, vejnet og elforsyning bruger netværksanalyse som et værktøj til at planlægge vedligeholdelse og udbygning.

For at kunne modellere for eksempel vandforsyning bedre, er det nødvendigt at indføre en vægt eller kapacitet for hver kant. Kanterne er med andre ord forskellige.

Hvis det er vandforsyning, du vil modellere, er vægten eller kapaciteten den mængde vand, som vandledningen kan transportere, i enheden liter/minut (eller noget tilsvarende). Computernetværk måles kapaciteten i kbps (kilobits per sekund).

Netværksanalyse kan du bruge til at maksimere udnyttelsen af kapaciteten i et netværk. Det kan du gøre ved at finde et udspændt træ (eng. spanning tree) til dit netværk (eller graf om du vil).

Et udspændt træ er en undergraf, som forbinder alle knuderne, uden at der er løkker (kæder som begynder og ender i samme knude). Det er ikke nødvendigt, at alle kanter bruges, når du skal konstruere et udspændt træ.

Et minimalt udspændt træ (eng. Minimum Spanning Tree) er det træ, hvor summen af kanternes vægt er mindre end alle andre udspændte træer.

Ejer du en nyere switch til dit netværk, kan du sandsynligvis slå Spanning Tree til. Switchen vil så forsøge at minimere omkostninger (eller maksimere kapaciteten) i dit computernetværk ved at udspænde træer over dit netværk – og gøre det hele tiden.

Sociale netværk

Vi mennesker indgår også i netværk. Du kan se menneskeheden som en stor graf, hvor menneskene er knuder, og de indbyrdes relationer er kanter. Facebook og LinkedIn har gjort en dyd ud af at tilbyde brugerne at dyrke deres sociale netværk.

Men ideen om sociale netværk og analyse af dem går tilbage til slutningen af 1800-tallet. Der er dog ikke tale om en datalogisk analyse men nærmere en sociologisk analyse af fænomenet.

Tilbage i 1929 får den ungarske forfatter Frigyes Karinthy den skøre idé, at alle mennesker er forbundne gennem højst seks led. Formuleret med grafteori er Karinthys hypotese, at ingen kæde mellem to knuder har mere end 5 kanter.

Et studium for et par år siden (Planetary-Scale Views on an Instant-Messaging Network – se http://arxiv.org/abs/0803.0939v1) af 240 mio. MSN-brugeres 30 milliarder beskeder viser, at der i gennemsnit er 6.6 led mellem to brugere.

Der findes en open source applikation til analyse af sociale netværk. Applikationen hedder SocNetV, og bruger du Ubuntu Linux, kan du uden videre installere applikationen med kommandoen sudo apt-get install socnetv.

Applikationen SocNetV er her i gang med at analysere Alt om Datas hjemmeside.

Google og Page Rank

Internettet består af en række websider (i formatet html). Mange sider har forbindelser til andre sider i form af links. Der er med andre ord ikke langt fra internettets indhold til en graf. Internettet kan opfattes som en række knuder (websider) forbundet med orienterede kanter (links).

Larry Page (grundlæggeren af Google) bruger denne idé til at analysere indholdet af internettet. Hans algoritme bærer hans navn: Page Rank (og nej, Page kommer fra hans navn, og ikke at det handler om sider).

Den grundlæggende idé er, at et link fra side X til side Y skal opfattes, som stemmer på Y og derved sige, at side Y er god/vigtig/troværdig. En sides troværdighed omtales i søgemaskinesprog som page rank (og her refererer ordet page faktisk til, at der er tale om en webside – det skal ikke være nemt).

Men stemmer siden X på mange andre sider (siden X har mange links), tæller side X’s stemmer ikke så meget som en side med få links. Det er for at udgå, at doorway pages tæller med.

En doorway page er en side, hvis formål er at have links til en masse sider og derved forsøge at stemme disse sider op. Mange andre søgemaskiner end Google tjekker ikke for doorway pages, og du kan derved snyde dig til en højere placering (bare ikke hos Google).

En graf med 6 knuder forbundet med en række kanter. Der er flere kæder, f.eks. A → C → B → F og grafen er sammenhængende.

Matematisk set kan du udtrykke en sides rank som summen af de andre siders rank divideret med antal links.Men det betyder, at du først kan regne en sides rank ud, når du kender alle siders rank.

Tricket er at give et gæt på rank for alle sider og så udregne en ny rank for siderne på den baggrund. Sidernes nye rank bruges som gæt til næste udregning af rank, og dette cirkus fortsætter, indtil sidernes rank ikke ændrer sig. Når du søger med Google, finder Google siderne som passer til din søgning. Rækkefølgen, Google viser siderne, er bestemt af sidernes rank.

Afslutning

Denne artikel er mere matematisk end de fleste andre artikler normalt på denne side. Men det er relevant matematik for netværksforståelse, og forhåbentlig har du fået lyst til at udforske grafer og netværk i dit nærmiljø. Tænk på, at du gennem en vens, vens, ven måske kender den amerikanske præsident eller årets Nobelpristager i fysik eller Alt om DATAs chefredaktør. Hvem ved?

Grafteori er sjovt at lege med, og min personlige erfaring er, at selv 8-årige kan forstå de mest basale begreber i denne afdeling af matematikken.

Topologisk sortering i Javascript

function Graph() {
this.name = ’undefined’;
this.nodes = [];
}

Graph.prototype = {
// return index to node, -1 if not found
find_node: function(id) {
var i;
var found;

if (this.nodes.length === 0) {
return -1;
}

i = 0;
found = false;
while (i if (this.nodes[i].id == id) {
found = true;
}
if (found) {
break;
}
i++;
}
if (found) {
return i;
} else {
return -1;
}
},

// add nodes - id is a unique string for identification
add_node: function(id, payload) {
if (this.find_node(id) < 0) {
var edges = [];
var n = {id: id, visited: false, edges: edges,
payload: payload};
this.nodes.push(n);
}
},

Topologisk sortering i Javascript

// add edge - work well for DAGs
// if you don’t work with DAGs, then use
// add_edge(i, j) ; add_edge(j, i);
add_edge: function(src, dst) {
var n;
var i = this.find_node(src);
var j = this.find_node(dst);
if (i>=0 && j>=0) {
n = this.nodes[i].edges.push(j);
}
},

// topological sorting - return array of IDs
// see http://en.wikipedia.org/wiki/Topological_sort
// (alternative algorithm)
sort: function() {
var i, j, m;
var L = [], Lid = [];
var that = this;

for (i in this.nodes) {
this.nodes[i].visited = false;
}

function _visit(n) {
var j;
if (!that.nodes[n].visited) {
that.nodes[n].visited = true;
for (j in that.nodes[n].edges) {
m = that.nodes[n].edges[j];
_visit(m);
}
L.push(n);
}
}
for (i in this.nodes) {
_visit(i);
}

for (i in L) {
j = L[i];
Lid.push(this.nodes[j].id);
}
return Lid;
}
};

// Test case
g = new Graph;
g.add_node(’Emacs’, {version: ’23.1’});
g.add_node(’GTK’, {version: ’2.18.3’});
g.add_node(’Cairo’, {version: ’1.8.8’});
g.add_node(’glib’, {version: ’2.22.3’});
g.add_node(’libc’, {version: ’2.10.1’});
g.add_edge(’Emacs’, ’libc’);
g.add_edge(’Emacs’, ’GTK’);
g.add_edge(’GTK’, ’glib’);
g.add_edge(’GTK’, ’Cairo’);
g.add_edge(’Cairo’, ’libc’);
g.add_edge(’glib’, ’libc’);
list = g.sort();
print(’Topological sort: ’+list.join(’->’));