Grad (Graphentheorie)

Eigenschaft eines Knotens in der Graphentheorie

Grad (auch Knotengrad oder Valenz) ist ein grundlegender Begriff der Graphentheorie, eines Teilgebiets der Mathematik. Der Grad eines Knotens ist die Anzahl von Kanten, die an ihn angrenzen.

DefinitionBearbeiten

Ungerichtete GraphenBearbeiten

 
Ein ungerichteter Graph. Die Knoten sind mit ihrem Grad beschriftet.

In einem ungerichteten Graphen   ist für jeden Knoten   der Grad   definiert als die Anzahl aller Kanten von  , die an   angrenzen. Sofern vorhanden werden Schlingen dabei doppelt gezählt.

Statt   wird oft auch die Notation   verwendet. Der Index   kann weggelassen werden, falls klar ist, um welchen Graphen es sich handelt.

Den kleinsten Grad eines Knotens in   nennt man den Minimalgrad von   und bezeichnet diesen mit  , den größten Grad eines Knotens in   nennt man den Maximalgrad von  , dieser wird meist mit   bezeichnet. Der Durchschnitt aller Knotengrade von   wird Durchschnittsgrad genannt und mit   bezeichnet.

Gerichtete GraphenBearbeiten

 
Ein gerichteter Graph mit beschrifteten Knoten: (Eingangsgrad, Ausgangsgrad)

In einem gerichteten Graphen   wird unterschieden, ob eine Kante an einem Knoten beginnt oder endet. Mit   bezeichnet man den Eingangsgrad des Knotens   in einem gerichteten Graphen   und mit   dessen Ausgangsgrad.

Dabei ist   die Anzahl aller Kanten, die in   enden und   die Anzahl aller Kanten, die in   starten.

Einen Knoten ohne Eingangskanten ( ) nennt man Quelle, einen Knoten ohne Ausgangskanten ( ) nennt man Senke.

Verwandte BegriffeBearbeiten

  • Man nennt einen Knoten isoliert, wenn er:
    • in einem ungerichteten Graphen: keine Nachbarn besitzt  .
    • in einem gerichteten Graphen: keine Vorgänger und keine Nachfolger besitzt.  .
  • Ein ungerichteter Graph oder Hypergraph   heißt regulär, falls alle seine Knoten denselben Grad besitzen. Besitzen alle seine Knoten Grad  , so bezeichnet man   als k-regulär. Einen 3-regulären Graphen bezeichnet man auch als kubisch.
  • Ein gerichteter Graph   heißt regulär, falls alle seine Knoten denselben Eingangs- und Ausgangsgrad besitzen. Besitzen alle seine Knoten Eingangs- und Ausgangsgrad  , so bezeichnet man   als k-regulär.
  • Ein Hypergraph   heißt uniform, wenn alle Kanten von   die gleiche Anzahl Knoten enthalten. Enthalten alle Kanten von   genau   Knoten, so nennt man   k-uniform.

EigenschaftenBearbeiten

  • Stets gilt  . Gleichheit tritt z. B. bei vollständigen Graphen, allgemein bei regulären Graphen ein.
  • Es gilt  , wobei   die Anzahl der Kanten des Graphen bezeichnet. Da die Summe der Knotengrade also stets gerade ist, ist auch die Anzahl der Knoten mit ungeradem Grad stets gerade.

Planare GraphenBearbeiten

Zusammenhängende planare Graphen mit   Knoten,   Kanten und   erfüllen die Ungleichung  , weil jede Fläche benachbart zu mindestens drei Kanten und jede Kante genau zwei Flächen begrenzt. Daraus und aus der Gleichung   (Eulerscher Polyedersatz) folgt   und daraus folgt für den durchschnittlichen Knotengrad

 

Das heißt, dass für endliche planare Graphen der durchschnittliche Knotengrad kleiner als 6 ist. Graphen mit höherem durchschnittlichen Knotengrad können nicht planar sein.

VerwendungBearbeiten

Der Grad gehört zu den Grundbegriffen der Graphentheorie und liefert viele wichtige Abschätzungen für Grapheneigenschaften wie z. B. die Kantenfärbungszahl.

LiteraturBearbeiten