Graad (grafentheorie)

De graad of valentie van een knoop in een graaf is het aantal buren van die knoop. Grafen zijn het onderwerp van studie van de grafentheorie. De graad is in een niet-gerichte graaf dus het aantal bogen dat in de knoop samenkomt. Er wordt voor een gerichte graaf onderscheid gemaakt tussen de inkomende en de uitgaande graad, het aantal bogen dat in een knoop samenkomt en het aantal bogen dat vertrekt.

ongerichte graaf waarin de graad van elke knoop is aangeduid

twee grafen met grafische lijst (3,2,2,2,2,1,1,1)

Een knoop met graad 0 is een geïsoleerde knoop. Een graaf waarin alle knopen dezelfde graad hebben is een reguliere graaf. Als die graad gelijk aan k is noemen we het een k-reguliere graaf. Een 3-reguliere graaf noemt men ook wel een kubieke graaf.