Definition - Valenz

• Konstrukte:
  • Valenzsequenz
• Generalisierungen:
  • Valenz gerichteter Graphen
• Eigenschaften:
  • Ablesen der Valenz aus der Adjazenzmatrix
• Involvierte Definitionen:
  • Knoten
  • Kante
  • Graph
  • Adjazenz
• Veranstaltung: AlMa
• Referenz: @herzogWiSe22

⠀

Definition: Valenz

Sei ein Graph.

Als Knotengrad, auch Valenz, eines Knotens bezeichnen wir die Anzahl der Nachbarn eines Knotens, bzw. der Kanten, die von ausgehen.

Es gilt:

Anmerkung

Was ist mit den Kanten, die in enden?

Da ein ungerichteter Graph ist, gilt . Würden wir beide Richtungen zählen, dann würden wir die Anzahl der Nachbarn von um das doppelte überschätzen. Deshalb zählen wir nur die von ausgehenden Kanten. Wir könnten stattdessen aber auch genauso gut die Kanten zählen, die in enden. Das ist schließlich alles dasselbe.

In gerichteten Graphen unterscheidet man übrigens zwischen ausgehendem und eingehendem Valenzgrad. Aber das ist ein anderes Thema.