Grad (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.

In einem ungerichteten Graphen ${\displaystyle G}${\displaystyle G} ist für jeden Knoten ${\displaystyle v}${\displaystyle v} der Grad ${\displaystyle d_{G}(v)}${\displaystyle d_{G}(v)} definiert als die Anzahl aller Kanten von ${\displaystyle G}${\displaystyle G}, die an ${\displaystyle v}${\displaystyle v} angrenzen. Sofern vorhanden werden Schlingen dabei doppelt gezählt.

Statt ${\displaystyle d_{G}(v)}${\displaystyle d_{G}(v)} wird oft auch die Notation ${\displaystyle \deg _{G}(v)}${\displaystyle \deg _{G}(v)} verwendet. Der Index ${\displaystyle G}${\displaystyle G} kann weggelassen werden, falls klar ist, um welchen Graphen es sich handelt.

Den kleinsten Grad eines Knotens in ${\displaystyle G}${\displaystyle G} nennt man den Minimalgrad von ${\displaystyle G}${\displaystyle G} und bezeichnet diesen mit ${\displaystyle \delta (G)}${\displaystyle \delta (G)}, den größten Grad eines Knotens in ${\displaystyle G}${\displaystyle G} nennt man den Maximalgrad von ${\displaystyle G}${\displaystyle G}, dieser wird meist mit ${\displaystyle \Delta (G)}${\displaystyle \Delta (G)} bezeichnet. Der Durchschnitt aller Knotengrade von ${\displaystyle G}${\displaystyle G} wird Durchschnittsgrad genannt und mit ${\displaystyle d(G)}${\displaystyle d(G)} bezeichnet.

In einem gerichteten Graphen ${\displaystyle G}${\displaystyle G} wird unterschieden, ob eine Kante an einem Knoten beginnt oder endet. Mit ${\displaystyle d_{G}^{-}(v)}${\displaystyle d_{G}^{-}(v)} bezeichnet man den Eingangsgrad des Knotens ${\displaystyle v}${\displaystyle v} in einem gerichteten Graphen ${\displaystyle G}${\displaystyle G} und mit ${\displaystyle d_{G}^{+}(v)}${\displaystyle d_{G}^{+}(v)} dessen Ausgangsgrad.

Dabei ist ${\displaystyle d_{G}^{-}(v)}${\displaystyle d_{G}^{-}(v)} die Anzahl aller Kanten, die in ${\displaystyle v}${\displaystyle v} enden und ${\displaystyle d_{G}^{+}(v)}${\displaystyle d_{G}^{+}(v)} die Anzahl aller Kanten, die in ${\displaystyle v}${\displaystyle v} starten.

Einen Knoten ohne Eingangskanten (${\displaystyle d_{G}^{-}(v)=0}${\displaystyle d_{G}^{-}(v)=0}) nennt man Quelle, einen Knoten ohne Ausgangskanten (${\displaystyle d_{G}^{+}(v)=0}${\displaystyle d_{G}^{+}(v)=0}) nennt man Senke.

• Man nennt einen Knoten isoliert, wenn er:
  • in einem ungerichteten Graphen: keine Nachbarn besitzt, ${\displaystyle d_{G}=0}${\displaystyle d_{G}=0}.
  • in einem gerichteten Graphen: keine Vorgänger und keine Nachfolger besitzt, ${\displaystyle d_{G}^{+}=d_{G}^{-}=0}${\displaystyle d_{G}^{+}=d_{G}^{-}=0}.

• Ein ungerichteter Graph oder Hypergraph ${\displaystyle G}${\displaystyle G} heißt regulär, falls alle seine Knoten denselben Grad besitzen. Besitzen alle seine Knoten Grad ${\displaystyle k}${\displaystyle k}, so bezeichnet man ${\displaystyle G}${\displaystyle G} als k-regulär. Einen 3-regulären Graphen bezeichnet man auch als kubisch.

• Ein gerichteter Graph ${\displaystyle G}${\displaystyle G} heißt regulär, falls alle seine Knoten denselben Eingangs- und Ausgangsgrad besitzen. Besitzen alle seine Knoten Eingangs- und Ausgangsgrad ${\displaystyle k}${\displaystyle k}, so bezeichnet man ${\displaystyle G}${\displaystyle G} als k-regulär.

• Ein Hypergraph ${\displaystyle G}${\displaystyle G} heißt uniform, wenn alle Kanten von ${\displaystyle G}${\displaystyle G} die gleiche Anzahl Knoten enthalten. Enthalten alle Kanten von ${\displaystyle G}${\displaystyle G} genau ${\displaystyle k}${\displaystyle k} Knoten, so nennt man ${\displaystyle G}${\displaystyle G} k-uniform.

• Stets gilt ${\displaystyle \delta (G)\leq d(G)\leq \Delta (G)}${\displaystyle \delta (G)\leq d(G)\leq \Delta (G)}. Gleichheit tritt z. B. bei vollständigen Graphen, allgemein bei regulären Graphen ein.
• Es gilt ${\displaystyle 2\cdot |E|=\sum _{v\in V(G)}d_{G}(v)}${\displaystyle 2\cdot |E|=\sum _{v\in V(G)}d_{G}(v)}, wobei ${\displaystyle |E|}${\displaystyle |E|} 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.

Zusammenhängende planare Graphen mit ${\displaystyle |V|}${\displaystyle |V|} Knoten, ${\displaystyle |E|}${\displaystyle |E|} Kanten und ${\displaystyle |F|}${\displaystyle |F|} Flächen erfüllen die Ungleichung ${\displaystyle 2\cdot |E|\geq 3\cdot |F|}${\displaystyle 2\cdot |E|\geq 3\cdot |F|}, weil jede Fläche benachbart zu mindestens drei Kanten und jede Kante genau zwei Flächen begrenzt. Daraus und aus der Gleichung ${\displaystyle |V|-|E|+|F|=2}${\displaystyle |V|-|E|+|F|=2} (Eulerscher Polyedersatz) folgt ${\displaystyle |E|\leq 3\cdot |V|-6}${\displaystyle |E|\leq 3\cdot |V|-6} und daraus folgt für den durchschnittlichen Knotengrad

${\displaystyle d(G)={\frac {\sum _{v\in V}d_{G}(v)}{|V|}}={\frac {2\cdot |E|}{|V|}}\leq {\frac {2\cdot (3\cdot |V|-6)}{|V|}}={\frac {6\cdot |V|-12}{|V|}}<6}${\displaystyle d(G)={\frac {\sum _{v\in V}d_{G}(v)}{|V|}}={\frac {2\cdot |E|}{|V|}}\leq {\frac {2\cdot (3\cdot |V|-6)}{|V|}}={\frac {6\cdot |V|-12}{|V|}}<6}

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.

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

Das folgende Beispiel in der Programmiersprache C# zeigt die Implementierung eines ungerichteten Graphen mit Adjazenzlisten. Der ungerichtete Graph wird als Klasse UndirectedGraph deklariert. Bei der Ausführung des Programms wird die Methode Main verwendet, die den Minimalgrad, den Maximalgrad und die entsprechenden Knoten des Graphen auf der Konsole ausgibt.^[1]

usingSystem;
usingSystem.Collections.Generic;
// Deklariert die Klasse für die Knoten des Graphen
classNode
{
publicintindex;
publicstringvalue;
publicHashSet<Node>adjacentNodes=newHashSet<Node>();// Menge der Nachbarknoten
}
// Deklariert die Klasse für den ungerichteten Graphen
classUndirectedGraph
{
publicHashSet<Node>nodes=newHashSet<Node>();

// Diese Methode verbindet die Knoten node1 und node2 miteinander.
publicvoidConnectNodes(Nodenode1,Nodenode2)
{
node1.adjacentNodes.Add(node2);
node2.adjacentNodes.Add(node1);
}
}
classProgram
{
// Diese Methode gibt die Knoten in der Form A, B, C, ... als Text zurück.
publicstaticstringToString(HashSet<Node>nodes)
{
stringtext="";
foreach(Nodenodeinnodes)// foreach-Schleife, die alle Knoten der Komponente durchläuft
{
text+=node.value+", ";
}
text=text.Substring(0,text.Length-2);
returntext;
}

// Hauptmethode, die das Programm ausführt
publicstaticvoidMain(string[]args)
{
// Deklariert und initialisiert 5 Knoten
Nodenode1=newNode{index=0,value="A"};
Nodenode2=newNode{index=1,value="B"};
Nodenode3=newNode{index=2,value="C"};
Nodenode4=newNode{index=3,value="D"};
Nodenode5=newNode{index=4,value="E"};
// Deklariert und initialisiert ein Array mit den Knoten
Node[]nodes={node1,node2,node3,node4,node5};
// Erzeugt einen ungerichteten Graphen
UndirectedGraphundirectedGraph=newUndirectedGraph();
intnumberOfNodes=nodes.Length;
for(inti=0;i<numberOfNodes;i++)// for-Schleife, die alle Knoten durchläuft
{
undirectedGraph.nodes.Add(nodes[i]);// Fügt die Knoten dem Graphen hinzu
}
// Verbindet Knoten des Graphen miteinander
undirectedGraph.ConnectNodes(node1,node2);
undirectedGraph.ConnectNodes(node3,node4);
undirectedGraph.ConnectNodes(node4,node5);

intminimumDegree=numberOfNodes;
HashSet<Node>nodesWithMinimumDegree=newHashSet<Node>();
intmaximumDegree=0;
HashSet<Node>nodesWithMaximumDegree=newHashSet<Node>();
for(inti=0;i<numberOfNodes;i++)// for-Schleife, die alle Knoten durchläuft
{
// Bestimmt den Minimalgrad und den Maximalgrad und die entsprechenden Knoten des Graphen
Nodenode=nodes[i];
intdegree=node.adjacentNodes.Count;// Knotengrad = Anzahl der Nachbarknoten
if(degree<minimumDegree)
{
minimumDegree=degree;
nodesWithMinimumDegree.Clear();
nodesWithMinimumDegree.Add(node);
}
if(degree==minimumDegree)
{
nodesWithMinimumDegree.Add(node);
}
if(degree>maximumDegree)
{
maximumDegree=degree;
nodesWithMaximumDegree.Clear();
nodesWithMaximumDegree.Add(node);
}
if(degree==maximumDegree)
{
nodesWithMaximumDegree.Add(node);
}
}
Console.WriteLine("Minimalgrad: "+minimumDegree);// Ausgabe auf der Konsole
Console.WriteLine("Knoten mit Minimalgrad: "+ToString(nodesWithMinimumDegree));// Ausgabe auf der Konsole
Console.WriteLine("Maximalgrad: "+maximumDegree);// Ausgabe auf der Konsole
Console.WriteLine("Knoten mit Maximalgrad: "+ToString(nodesWithMaximumDegree));// Ausgabe auf der Konsole

Console.ReadLine();
}
}

• Reinhard Diestel: Graphentheorie. Springer, Berlin 2010, ISBN 978-3-642-14911-5. 

1. ↑ GeeksforGeeks: Print nodes having maximum and minimum degrees

• Grundbegriff (Graphentheorie)