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.

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.^[1]

Bronnen, noten en/of referenties

1. A Tripathi, S Venugopalan en DB West. A short constructive proof of the Erdös-Gallai characterization of graphic lists, 28 februari 2010. in Discrete Mathematics, 310, 4 blz 843–844 . Gearchiveerd op 20 oktober 2021.