knoopgraad

Knoopgraad is een term uit de grafentheorie die de graad van een knoop (vertex) aanduidt. De knoopgraad van een knoop is het aantal randen dat aan die knoop is verbonden. In een ongerichte grafiek telt elke rand één keer mee bij de graad van de knoop, dus de knoopgraad is gelijk aan het aantal aangrenzende knopen.

Bij gerichte grafieken bestaat er onderscheid tussen in-graad en uit-graad. De in-graad van een knoop is het aantal randen die eindigen op die knoop, de uit-graad het aantal randen die starten bij die knoop. De totale knoopgraad kan worden gezien als de som van in-graad en uit-graad, afhankelijk van de gekozen notatie. Een lus (een rand die van een knoop terug naar dezelfde knoop loopt) telt in een ongerichte grafiek twee mee naar de knoopgraad, en in een gerichte grafiek telt een lus mee voor zowel de in-graad als de uit-graad.

Een fundamentele eigenschap van knoopgraden is de handshaking-lemma: de som van de knoopgraden over alle knopen is gelijk aan twee maal het aantal randen. Als een grafie alle knopen dezelfde graad hebben, spreekt men van een regulaire grafiek. De knoopgraad is een basiskenmerk voor netwerk- en grafische analyses en wordt gebruikt bij het modelleren van sociale netwerken, transportnetwerken en communicatieroutes, evenals bij algoritmes die grafstructuren reconstrueren of analyseren.