Der Grad (englisch degree) eines Knotens in einem Graphen gibt an, wie viele Kanten an ihm anliegen. Ein Knoten mit drei Verbindungen hat den Grad 3.
Eingangsgrad und Ausgangsgrad
In gerichteten Graphen unterscheidet man den Eingangsgrad (in-degree, eingehende Kanten) vom Ausgangsgrad (out-degree, ausgehende Kanten). Der Gesamtgrad ist die Summe beider Werte. In sozialen Netzwerken entspricht der Eingangsgrad den Followern, der Ausgangsgrad den gefolgten Accounts.
Handshake-Lemma
Eine zentrale Eigenschaft: Die Summe aller Knotengrade ist immer genau doppelt so groß wie die Anzahl der Kanten. Jede Kante trägt zu genau zwei Knotengraden bei. Daraus folgt, dass die Anzahl der Knoten mit ungeradem Grad immer gerade ist.
Grad in Algorithmen
Der Grad ist eine nützliche Kennzahl: In der Adjazenzliste ist er die Länge der Liste eines Knotens, in der Adjazenzmatrix die Zeilen- oder Spaltensumme. Der Kahn-Algorithmus für die topologische Sortierung startet mit allen Knoten, deren Eingangsgrad 0 ist, und reduziert den Grad bei jeder entfernten Kante. Bei der Tiefensuche und Breitensuche bestimmt der Grad, wie viele Nachbarn von einem Knoten aus erreichbar sind.