Matrices en grafen > Grafen
123456Grafen

Theorie

Je ziet hier een graaf met 5 knooppunten en 6 verbindingslijnen. De lengte en de vorm van de verbindingslijnen en de plaats van de knooppunten zijn niet van belang. Twee grafen zijn namelijk gelijk als ze hetzelfde aantal knooppunten en dezelfde onderlinge verbindingen hebben.

Een verbindingsgraaf zoals deze is een ongerichte, enkelvoudige graaf, want elke verbinding werkt in beide richtingen en er is altijd hoogstens één verbindingslijn. De bijbehorende verbindingsmatrix is vierkant en symmetrisch t.o.v. de hoofddiagonaal, elk kental is 0 (geen verbinding) of 1 (wel verbinding). De graad van verbinding is het aantal bestaande verbindingen gedeeld door het totaal aantal mogelijke verbindingen.

Je kunt bij een dergelijke graaf ook de afstanden bij de verbindingen zetten, dan krijg je een afstandengraaf met een bijbehorende afstandenmatrix. En voor reistijden geldt iets vergelijkbaars.

Is er sprake van éénrichtingsverkeer op één of meer verbindingen, dan onstaat er een gerichte, enkelvoudige graaf. Pijltjes in de verbindingslijnen geven dan de richting in de graaf aan en je spreekt niet van verbindingen maar van wegen.
Laat je meerdere verbindingslijnen tussen twee punten toe, dan spreek je van een meervoudige graaf. De graaf kan dan ook getallen groter dan bevatten. De bijbehorende directe-wegen-matrix hoeft dan niet symmetrisch meer te zijn. De graad van verbinding heeft dan geen betekenis meer.

verder | terug