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 graaf, want elke verbinding werkt in beide richtingen. De bijbehorende verbindingsmatrix is vierkant en symmetrisch t.o.v. de hoofddiagonaal, elk kental is 0 (geen verbinding) of 1 (wel een verbinding). (Bij meerdere verbindingen tussen twee punten wordt het kental toch 1 omdat het alleen gaat om wel of geen rechtstreekse verbinding zonder tussenstation.) 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 de reistijden geldt iets vergelijkbaars.

Is er sprake van éénrichtingsverkeer op één of meer verbindingen, dan onstaat er een gerichte graaf. Pijltjes in de verbindingslijnen geven dan de richting in de graaf aan en je spreekt niet van verbindingen maar van wegen. De bijbehorende directe-wegen-matrix is dan niet symmetrisch meer. De graad van verbinding is nu het aantal wegen gedeeld door het mogelijke aantal wegen.