Graad (grafentheorie)

ongerichte graaf waarin de graad van elke knoop is aangeduid

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

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.

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.

Grafische lijsten

De graden van alle knopen in een graaf, gerangschikt in een niet-stijgende rij, noemt men een grafische lijst, in het Engels graphic list, maar meer de degree sequence van de graaf. Er bestaan in het algemeen meer grafen met een verschillende topologie die dezelfde grafische lijst hebben, zoals hiernaast is geïllustreerd. Ieder van deze grafen noemt men een realisatie van de gegeven grafische lijst.

Niet iedere willekeurige niet-stijgende lijst van natuurlijke getallen is een grafische lijst. (3,3,3,1) is bijvoorbeeld geen grafische lijst: het is onmogelijk een graaf te maken waar dit de grafische lijst van is. De stelling van Erdős en Gallai geeft er een noodzakelijke en voldoende voorwaarde voor dat er gegeven een grafische lijst een graaf met die grafische lijst kan bestaan. Er bestaan verschillende bewijzen van deze stelling, waaronder een constructief bewijs waarin een graaf wordt geconstrueerd met de gegeven lijst als grafische lijst.

Bronnen, noten en/of referenties