Netværk findes overalt: trafiknetværk, sociale netværk, molekyler sammensat af atomer, elektriske netværk osv. 
Internettet er et netværk. Grafteori er den matematiske abstraktion af netværk. Mens matematikken er flere tusinde år gammel, så er grafteori en forholdsvis ny gren. Som tidlige eksempler på grafteoretiske problemstillinger kan man nævne de Königsbergske broers problem fra 1700-tallet, Kirchhoffs love for elektriske netværk fra midten af 1800-tallet samt det berømte 4-farve-problem fra cirka samme tid. 
4-farve-problemet illustrerer et væsentligt træk ved grafteori: Der findes problemer, der er lette at forstå, men ekstremt vanskelige at løse. 4-farve-problemet går ud på at farvelægge landene i et vilkårligt landkort, så nabolande altid får forskellige farve, og så man benytter så få farver som muligt. Spørgsmålet er, om man altid kan klare sig med 4 farver. Svaret er ja, men det tog over 100 år at få det bevist. For et konkret landkort kan man stille spørgsmålene: Kan man farve det med kun 3 farver? Kan man farve det med kun 2 farver? Mens 2-farve-spørgsmålet er yderst let at besvare, så kender man ingen effektive metode til at besvare 3-farve-spørgsmålet. Dette forhold illustrerer et andet fascinerende forhold, nemlig at lette og vanskelige problemer ligger tæt ved hinanden, og at den menneskelige intuition ikke er meget bevendt, når man skal afgøre, om en matematisk påstand er sand eller falsk. Det eneste, der hjælper, er præcis og detaljeret matematisk argumentation. Således kan grafteori også tjene som et nyttigt pædagogisk værktøj i forbindelse med matematisk argumentation. 

Sidstnævnte illustreres fint af nærværende bog, der fokuserer på det aspekt, der måske bedst forklarer grafteoriens eksplosive udvikling siden 1930’erne, nemlig de mange praktiske anvendelser, der opstår i samspillet mellem grafteori og algoritmer. Som sådan udgør bogen en grundig introduktion til en markant anvendelse af moderne matematik inden for programmering og computervidenskab. 
Med computerens indtog opstod der i forbindelse med talrige problemstillinger spørgsmålet: Kan en konkret instans af problemet løses ved hjælp af en effektiv algoritme? Det skulle hurtigt vise sig, at grafteorien udgjorde et potent værktøj i denne henseende. 

Denne bog gennemgår nogle af de mest berømte eksempler på anvendelsen af grafteori inden for algoritmik og fokuserer både på at træne anvendelsen af algoritmer på konkrete problemer og på bevisførelse inden for grafteori. Algoritmerne er ikke vanskelige at forstå. Udfordringen består i at give et matematisk bevis for, at algoritmerne opnår det, man ønsker, de skal opnå. 

December, 2020 
Carsten Thomassen 
Professor i Matematik ved DTU 
 

• Diskret matematik. Et forløb i grafteori
• Indhold
• 1 Introduktion
  • 1.1 Grafer og netværk
  • 1.2 Læseguide til beviser
  • 1.3 Læseguide til bogen
  • 1.4 Mængdenotation
  • 1.5 Modstridsbeviser
• 2 Definitioner, begreber og notation
  • 2.1 Definitioner, begreber og basale observationer
  • 2.2 To slags grafer: veje og kredse
  • 2.3 Delgrafer og sammenhængskomponenter
  • 2.4 Overblik
  • 2.5 Øvelser til kapitel 2
  • Facitliste
• 3 Den korteste vej fra A til B
  • 3.1 Afstandsklasser
  • 3.2 Dijkstras algoritme
  • 3.3 (En guide til) Et bevis for Dijkstras algoritme*
    • 3.3.1 Vi viser, at (v) dist(s, v)
    • 3.3.2 Vi viser, at (v) dist(s, v)
  • 3.4 Overblik
  • 3.5 Øvelser til kapitel
    • Facitliste
• 4 Forbinderproblemet
  • 4.1 Træer og udspændende træer
  • 4.2 Kruskals algoritme
  • 4.3 (En guide til) Et bevis for Kruskals algoritme*
  • 4.4 Overblik
  • 4.5 Øvelser til kapitel 4
  • Facitliste
• 5 Supplerende øvelser
• 6 Afsluttende kommentarer
• Indeks