Een introductie tot grafentheorie

Hoe modelleer je paargewijze verbindingen tussen objecten? 

Met een wiskundige structuur die een graaf heet. En dat is de kern van de grafentheorie – de studie van grafen.  

De fundamentele elementen van grafentheorie zijn knopen (ook wel nodes genoemd) en kanten (ook wel links). Een knoop staat voor een individuele entiteit of een punt binnen een graaf, terwijl een kant een verbinding of relatie tussen twee knopen aanduidt. Samen vormen deze componenten de structuur van een graaf, die gericht of ongericht, gewogen of ongewogen kan zijn, afhankelijk van de specifieke aard van de gemodelleerde relaties.

In de informatica vormt grafentheorie de basis van veel algoritmen en datastructuren die gebruikt worden om netwerken te representeren, zoals het internet, sociale netwerken en communicatiesystemen. Het biedt ook tools om problemen op te lossen rond netwerkconnectiviteit, het vinden van paden en optimalisatie, en is fundamenteel voor het begrijpen van diverse wiskundige structuren en concepten zoals bomen, cycli en vlakke grafen.

In dit artikel leren we je wat je moet weten om met grafentheorie aan de slag te gaan.  

Gemaakt door auteur met Midjourney

Wat is grafentheorie?

Grafentheorie is een tak van de wiskunde die de eigenschappen en toepassingen van grafen bestudeert. Een graaf definieert een verzameling objecten, knopen (of nodes) genoemd, die verbonden zijn door kanten (of links). 

Het primaire doel van grafentheorie is het begrijpen van de structuur van deze grafen en het verkennen van uiteenlopende problemen rond connectiviteit, padvinding en netwerkoptimalisatie.

Door deze relaties te analyseren, stelt grafentheorie ons in staat om inzicht te krijgen in talloze real-world problemen in diverse vakgebieden.

Waar komt grafentheorie vandaan?

De oorsprong van de grafentheorie gaat terug tot de 18e eeuw met het werk van de Zwitserse wiskundige Leonhard Euler. Eulers oplossing voor het Königsbergse bruggenprobleem in 1736 wordt beschouwd als een van de eerste problemen in de grafentheorie. Dit probleem draaide om het vinden van een wandelroute door de stad Königsberg die elk van de zeven bruggen precies één keer zou oversteken. Eulers benadering legde de basis voor wat later een formele studie van grafen zou worden.

In de 19e en 20e eeuw ontwikkelde de grafentheorie zich aanzienlijk dankzij bijdragen van wiskundigen zoals Carl Friedrich Gauss, die de eigenschappen van veelvlakken onderzocht, en latere onderzoekers die concepten formaliseerden en algoritmen voor graafgerelateerde problemen ontwikkelden. 

De opkomst van de informatica in het midden van de 20e eeuw versnelde de groei van de grafentheorie verder, wat leidde tot brede toepassingen in computeralgoritmen, netwerkanalyse en datastructuren.

Fundamentele concepten van grafentheorie

Het begrijpen van de basis van grafentheorie vormt de basis voor het verkennen van meer geavanceerde onderwerpen in het vakgebied. Dus om je op weg te helpen, leggen we eerst wat fundamenten… 

Grafen als geordende paren

Een graaf wordt formeel gedefinieerd als een geordend paar G = (V, E), waarbij:

• V een verzameling knopen (of nodes) is, die de individuele entiteiten in de graaf representeren.
• E een verzameling kanten (of links) is, die de verbindingen tussen paren van knopen representeren.

Knopen (V) en kanten (E)

• Knopen (V): Dit zijn de fundamentele eenheden of punten in een graaf. Elke knoop stelt een entiteit of locatie voor in de structuur die wordt gemodelleerd.

• Kanten (E): Dit zijn de verbindingen of relaties tussen paren van knopen. Elke kant verbindt twee knopen en geeft een relatie of een pad tussen hen aan.

Typen kanten

• Gerichte kanten: In een gerichte graaf (of digraaf) hebben kanten een richting, wat betekent dat ze van de ene knoop naar een specifieke andere knoop gaan. Deze richting wordt vaak weergegeven met een pijl. Gerichte kanten zijn nuttig om asymmetrische relaties te modelleren, zoals verkeersstromen of volgordebeperkingen in planningen.

• Ongerichte kanten: In een ongerichte graaf hebben kanten geen richting en verbinden ze simpelweg twee knopen. Dit type graaf wordt gebruikt om symmetrische relaties te representeren, zoals wederzijdse vriendschappen of verbindingen in een netwerk waar richting niet relevant is.

Basisbegrippen en -terminologie in grafentheorie

Laten we nu enkele basisbegrippen en -concepten definiëren: 

Knoop (Node)

Dit concept vertegenwoordigt een individuele entiteit of een punt binnen de graafstructuur. In een sociale netwerkgraaf kan bijvoorbeeld elke persoon als een knoop worden weergegeven.

Graad van een knoop

De graad van een knoop is het aantal kanten dat eraan is verbonden. Dit geeft inzicht in de connectiviteit en het belang ervan binnen een graaf. De beste manier om dit te visualiseren is een persoon, weergegeven als een knoop, in een sociaal netwerk. Als er veel kanten van de knoop uitgaan, zeggen we dat hij een “hoge graad” heeft, wat ook een zeer invloedrijke persoon aanduidt. Als we een vervoersnetwerk modelleren, zou een knoop met een hoge graad aangeven dat het knooppunt een centraal hub in het netwerk is, met directe verbindingen naar de meeste andere locaties.   

Pad

Een pad in een graaf is een reeks knopen waarbij elk aangrenzend paar verbonden is door een kant. Paden kunnen eenvoudig zijn (geen herhaalde knopen) of algemeen (met herhalingen). Bijvoorbeeld: in een graaf met knopen A, B, C en D kan een pad A → B → C → D zijn, waarbij elke knoop met de volgende is verbonden door een kant.

Cyclus

Een cyclus is een pad dat begint en eindigt bij dezelfde knoop, zonder andere herhalingen van knopen of kanten. Cycli kunnen eenvoudig zijn (geen herhaalde kanten of knopen behalve begin en eind) of algemeen. Een voorbeeld: in een graaf met knopen A, B, C en D kan een eenvoudige cyclus A → B → C → D → A zijn.

Verbonden grafen

Een graaf is verbonden als er een pad is tussen elk paar knopen. Met andere woorden: elke knoop in een verbonden graaf kan elke andere knoop bereiken via een of andere reeks kanten. Een goed voorbeeld is een sociale netwerkgraaf waarin iedereen vanuit iedereen te bereiken is.

Typen grafen

Grafentheorie omvat verschillende typen grafen, elk geschikt voor andere toepassingen en analyses. In dit gedeelte verkennen we deze typen, bespreken we hun basisstructuren en geven we voorbeelden van toepassingen. Dit helpt je te begrijpen wanneer je elk type gebruikt om specifieke problemen op te lossen en realistische scenario's nauwkeurig te modelleren.

Eenvoudige graaf

Visualisatie van een eenvoudige graaf Bron: Wikipedia

Een eenvoudige graaf is een type graaf zonder meervoudige kanten (meer dan één kant tussen een paar knopen) of lussen (kanten die een knoop met zichzelf verbinden). Elke kant in een eenvoudige graaf verbindt twee verschillende knopen.

Voorbeelden:

• Een basis sociaal netwerk waarin elke vriendschap wordt weergegeven door één link tussen twee personen.
• Een kaart met steden verbonden door enkele, directe wegen zonder meerdere routes of zelfverbindingen.

Multigrafen

Een visualisatie van een multigraaf met meerdere kanten in het rood, en verschillende lussen in het blauw Bron: Wikipedia

Een multigraaf staat meerdere kanten (parallelle kanten) toe tussen hetzelfde paar knopen en kan ook lussen bevatten. Dit type graaf kan situaties representeren waarin meerdere interacties of verbindingen tussen entiteiten bestaan.

Voorbeelden:

• Een vervoersnetwerk waarin meerdere luchtvaartmaatschappijen vluchten uitvoeren tussen dezelfde steden.
• Een communicatienetwerk met meerdere kanalen die hetzelfde paar communicatieknooppunten verbinden.

Gewogen grafen

Een visualisatie van een gewogen graaf Bron: Hyperskill

In een gewogen graaf heeft elke kant een bijbehorend gewicht of kosten, wat een kwantitatieve maat vertegenwoordigt zoals afstand, tijd of capaciteit. Gewogen grafen worden gebruikt om problemen te modelleren waarbij de kanten verschillende sterktes of kosten hebben.

Toepassingen:

• In een kaart van steden die door wegen zijn verbonden, kunnen de gewichten afstanden of reistijden tussen steden voorstellen.
• In een netwerkoptimalisatieprobleem kunnen gewichten bandbreedte of kosten van communicatielinks voorstellen.

Gerichte grafen (digrafen)

Visualisatie van een gerichte graaf Bron: Wikipedia

Een gerichte graaf, of digraaf, heeft kanten met een specifieke richting, wat betekent dat elke kant van de ene knoop naar een andere, verschillende knoop gaat. De richting wordt vaak weergegeven door een pijl, die de stroom of een eenrichtingsrelatie aangeeft.

Use cases:

• Een workflowdiagram waarin taken in een specifieke volgorde moeten worden voltooid.
• Een linkstructuur van webpagina's, waarbij hyperlinks van de ene pagina naar de andere verwijzen en zo een eenrichtingsverbinding representeren.

Ongerichte grafen

Een visualisatie van een ongerichte graaf Bron: Baeldung

In een ongerichte graaf hebben kanten geen richting. Een kant verbindt simpelweg twee knopen, en de relatie is wederzijds of bidirectioneel. De volgorde van de knopen in een kant maakt niet uit.

Voorbeelden:

• Een netwerk van vrienden waarbij vriendschap wederzijds is en de verbindingen bidirectioneel zijn.
• Een ongerichte wegenkaart waarop wegen steden in beide richtingen verbinden zonder een richting te specificeren.

Boomgrafen in de grafentheorie

Een boom is een type graaf die verbonden en acyclisch is, wat betekent dat hij geen cycli bevat. Een boom met $$n$$ knopen heeft precies $$n−1$$ kanten. Elk paar knopen in een boom is verbonden door één enkel pad, wat ervoor zorgt dat er een uniek pad is tussen willekeurige twee knopen.

Hier is een snelle uiteenzetting van de eigenschappen van een boomgraaf: 

• Verbonden. Er is een pad tussen elk paar knopen.
• Acyclisch. Er zijn geen cycli, wat ervoor zorgt dat er geen gesloten lussen zijn.
• Uniek pad. Er is precies één pad tussen willekeurige twee knopen, wat impliceert dat de graaf minimaal verbonden is.
• Aantal kanten. Een boom met $$n$$ knopen heeft $$n−1$$ kanten.
• Subboom: Elke deelverzameling van een boom, inclusief een enkele knoop, is zelf een boom, een subboom genoemd.
• Bladknopen. Knopen met precies één kant worden bladeren of bladknopen genoemd. Het zijn de eindpunten van de boom.

Hoe verschillen boomgrafen van andere grafen? 

In tegenstelling tot algemene grafen bevatten bomen geen cycli. Dit betekent dat elke graaf met cycli niet als boom kan worden geclassificeerd. 

Een boom met $$n$$ knopen heeft precies $$n−1$$ kanten, terwijl algemene grafen een variabel aantal kanten kunnen hebben, inclusief meerdere kanten en zelflussen. Een ander verschil is dat bomen altijd verbonden zijn, terwijl algemene grafen onsamenhangend kunnen zijn en uit meerdere componenten kunnen bestaan die elk een boom kunnen zijn. 

Bovendien is er in een boom precies één pad tussen willekeurige twee knopen, in tegenstelling tot andere grafen waarin meerdere paden kunnen bestaan tussen knopen, met name in grafen die cycli of meervoudige kanten bevatten.

Toepassingen

Bomen zijn fundamenteel in zowel theoretische als praktische aspecten van computing en gegevensorganisatie. Ze bieden uiterst efficiënte oplossingen voor veel structurele en algoritmische problemen. Bijvoorbeeld: 

Datastructuren

• Binaire bomen: Gebruikt in de informatica voor hiërarchische organisatie van data. Voorbeelden zijn binaire zoekbomen, die snelle gegevensopvraging en -sortering mogelijk maken.
• Heaps: Een type binaire boom dat in prioriteitswachtrijen wordt gebruikt om het maximum- of minimumelement efficiënt te beheren en op te halen.
• B-trees: Gebruikt in databases en bestandssystemen voor efficiënte gegevensopslag en -opvraging, met ondersteuning voor operaties zoals invoegen, verwijderen en zoeken.

Netwerkontwerp

• Routing: Bomen worden in netwerkrouteringsprotocollen (zoals spanning trees) gebruikt om het meest efficiënte pad voor datatransmissie door een netwerk te bepalen.
• Broadcasting: In netwerkontwerp helpen boomstructuren bij efficiënte dataverspreiding, zodat data met minimale redundantie alle knopen bereikt.

Hiërarchieën weergeven

• Bestandssystemen: Bestandssystemen gebruiken vaak boomstructuren om mappen en submappen weer te geven, wat de hiërarchische organisatie van bestanden weerspiegelt.
• Organigrammen: Bomen worden gebruikt om organisatiehiërarchieën te modelleren, met weergave van rapporteringslijnen en relaties tussen verschillende rollen.

Parsen en syntactische analyse

• Abstracte syntaxisbomen (AST's): Gebruikt in compilers en interpreters om de syntactische structuur van broncode te representeren. AST's maken syntaxiscontroles en codeoptimalisatie mogelijk.

Toepassingen van grafentheorie

Grafentheorie kent een breed scala aan toepassingen in diverse vakgebieden. Het speelt een cruciale rol bij het oplossen van complexe problemen en het optimaliseren van systemen. Voorbeelden hiervan zie je in de volgende toepassingen: 

Informatica: netwerken, algoritmen en datastructuren

Grafentheorie is fundamenteel voor het ontwerpen en analyseren van netwerksystemen, het ontwikkelen van algoritmen en het structureren van data in de informatica. Netwerken leunen bijvoorbeeld sterk op grafentheorie om verbindingen tussen apparaten te modelleren en te beheren. Netwerktopologieën worden als grafen weergegeven om datatransmissie en routering te optimaliseren. 

Algoritmen zoals Dijkstra en Kruskal worden respectievelijk gebruikt om kortste-pad- en minimum-spanningstreeproblemen op te lossen. Daarnaast vormt grafentheorie de basis voor datastructuren zoals adjacency-lijsten en -matrices, die essentieel zijn voor efficiënte gegevensbewerking en -opvraging.

Biologie: biologische netwerken modelleren

Grafentheorie is ook van groot belang in de biologie. Het wordt gebruikt voor het modelleren en analyseren van complexe biologische netwerken, zoals: 

• Eiwit-eiwit-interactienetwerken
• Metabole routes
• Genregulerende netwerken

Deze netwerken worden weergegeven als grafen waarbij knopen biologische entiteiten (bijv. eiwitten, genen) zijn en kanten interacties of relaties tussen hen representeren. 

Deze aanpak helpt onderzoekers om de ingewikkelde relaties binnen biologische systemen te begrijpen, functionele uitkomsten te voorspellen en potentiële doelen voor medicijnontwikkeling te identificeren.

Sociale wetenschappen: sociale netwerkanalyse

In de sociale wetenschappen wordt grafentheorie gebruikt om sociale netwerken te analyseren, waarbij individuen als knopen en hun interacties of relaties als kanten worden weergegeven. 

Deze analyse helpt bij het begrijpen van sociale structuren, invloedspatronen en gemeenschapsdynamiek. Door concepten zoals centraliteit en connectiviteit toe te passen, kunnen onderzoekers sleutelinvloeders identificeren, de verspreiding van informatie bestuderen en sociaal gedrag analyseren.

Vervoer: verkeersstromen en stedelijke planning 

De meeste mensen weten dit niet, maar wegen, kruispunten en OV-routes worden als grafen gemodelleerd om: 

• Verkeersstromen te optimaliseren
• Filevorming te verminderen
• Routeplanning te verbeteren. 

Op grafen gebaseerde algoritmen helpen bij het ontwerpen van efficiënte vervoersnetwerken, het beheren van OV-systemen en het plannen van stedelijke infrastructuur. Door deze netwerken te analyseren kunnen planners weloverwogen beslissingen nemen om mobiliteit en connectiviteit binnen steden te verbeteren.

Stapsgewijze handleiding voor het construeren en analyseren van een eenvoudige graaf

Je beheerst de basis en je begrijpt de toepassingen van grafentheorie. 

Nu ben je klaar om je eigen eenvoudige graaf te maken en te analyseren. Om het eenvoudig te houden, hebben we deze stapsgewijze handleiding in twee delen opgesplitst: 

• Constructie 
• Analyse

Het meest logische onderdeel om mee te beginnen is de constructie – aan de slag dan maar… 

Een eenvoudige graaf construeren

Stap 1: Definieer het probleem. 

Stel dat we een klein netwerk van vrienden in een sociaal netwerk willen modelleren. 

We kunnen de NetworkX-bibliotheek in Python gebruiken, die gemaakt is voor netwerkanalyse, om dit te modelleren. 

Laten we beginnen met het maken van een graaf: 

# Import libraries 
import networkx as nx # Network analysis
import matplotlib.pyplot as plt # Data visualization
import pydot # Python interface to Graphviz
from networkx.drawing.nx_pydot import graphviz_layout
# Create a graph
graph = nx.Graph() 

Stap 2: Identificeer de knopen. 

In ons fictieve sociale netwerk hebben we vier personen: Alice, Bob, Carol en Dave. Deze personen worden als knopen in onze graaf weergegeven – onthoud: dit vertegenwoordigt een entiteit of een locatie in de gemodelleerde structuur.

Zo maken we de knopen in Python:

# Add the nodes 
# graph.add_node("Alice") --> Add one node per time
graph.add_nodes_from([
    "Alice","Bob", "Carol", "Dave"
]) # Add multiple nodes

Stap 3: Bepaal de kanten. 

Stel dat de vriendschapsverbindingen als volgt zijn:

• Alice is bevriend met Bob en Carol.
• Bob is bevriend met Alice en Dave.
• Carol is bevriend met Alice.
• Dave is bevriend met Bob.

Dit betekent dat deze relaties de kanten vormen:

• Alice-Bob
• Alice-Carol
• Bob-Dave

Zo zouden we de kanten in Python definiëren: 

# Add the edges
# graph.add_edge("Alice", "Bob") --> Add one edge per time
graph.add_edges_from([("Alice", "Bob"), 
                      ("Alice", "Carol"),
                      ("Bob", "Dave"),
                      ("Bob", "Alice")  # Ensuring all described edges are included
                     ]) # Add multiple edges

Stap 4: Teken de graaf.

Zodra de knopen en kanten gedefinieerd zijn, kunnen we de graaf tekenen om de relaties te visualiseren. De onderstaande code maakt een grafische weergave van het netwerk met gelabelde knopen en kanten:

# Visualize the plot
pos = graphviz_layout(graph, prog="dot")
nx.draw(graph, 
        pos, 
        with_labels=True, 
        node_size=1000, 
        node_color=["pink", "yellow", "tan", "orange"])
plt.show()

Output: Dit genereert een graaf die de verbindingen tussen Alice, Bob, Carol en Dave weergeeft zoals beschreven.

Deze code produceert de volgende graaf: 

Een eenvoudige graaf die een sociaal netwerk modelleert [gemaakt door de auteur]

Als je je eigen sociale netwerk wilt modelleren, maak dan een kopie van dit DataLab-notebook en pas het naar wens aan. 

De eenvoudige graaf analyseren

Stap 1: Controleer de connectiviteit. 

Omdat we van elke knoop naar elke andere knoop kunnen gaan via een reeks kanten, is de graaf verbonden. 

Om dit beter te begrijpen, hier het pad tussen elk paar knopen: 

• Alice naar Bob: directe kant.
• Alice naar Carol: directe kant.
• Alice naar Dave: via Bob.
• Bob naar Carol: via Alice.
• Bob naar Dave: directe kant.
• Carol naar Dave: via Alice en Bob.

Stap 2: Bepaal de graad van elke knoop. 

We definieerden de graad van een knoop als “het aantal kanten dat ermee verbonden is.” Toegepast op ons voorbeeld vinden we: 

• Alice = graad 2 (verbonden met Bob en Carol)
• Bob = graad 2 (verbonden met Alice en Dave)
• Carol = graad 1 (verbonden met Alice)
• Dave = graad 1 (verbonden met Bob)

Elke graad wordt bepaald door het aantal kanten te tellen dat bij elke knoop hoort, op basis van de gegeven vriendschappen.

Stap 3: Identificeer paden en cycli.

Een pad tussen Alice en Dave kan Alice → Bob → Dave zijn.

De graaf heeft geen cycli, aangezien er geen paden zijn die terugkeren naar de startknoop zonder stappen te herhalen.

Stap 4: Bepaal de centraliteit.

Alice en Bob zijn centraal in dit netwerk, omdat ze elk met drie andere knopen verbinden. Carol en Dave zijn minder centraal: zij verbinden elk met slechts één andere knoop.

Conclusie

Grafentheorie biedt een robuust kader om complexe relaties en structuren te onderzoeken en op te lossen die in uiteenlopende vakgebieden voorkomen. Door kernbegrippen zoals knopen, kanten en verschillende typen grafen te begrijpen, en hun praktische toepassingen te verkennen, kun je waardevolle inzichten opdoen om systemen te optimaliseren en real-world problemen op te lossen.

Onthoud bij het verder verkennen van grafentheorie dat de principes niet alleen theoretisch zijn—ze zijn essentieel om realistische uitdagingen aan te pakken, de connectiviteit te verbeteren en de systeemefficiëntie te verhogen. Een solide begrip van grafentheorie scherpt je probleemoplossend vermogen en biedt een dieper perspectief op de onderling verbonden systemen om ons heen.

Om je begrip van grafentheorie te verdiepen, bekijk deze meer geavanceerde bronnen die voortbouwen op wat we in dit artikel hebben behandeld: 

• Een uitgebreide introductie tot Graph Neural Networks (GNN's) 
• Graafoptimalisatie met NetworkX in Python
• Decision tree-classificatie in Python-tutorial