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.

Definition

Ungerichtete Graphen 

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 Graphen 

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 Begriffe 
 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.

Eigenschaften 
 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 Graphen 
Zusammenhängende planare Graphen mit  Knoten,  Kanten und  Flächen 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.

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

Programmierung 
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.using System;
using System.Collections.Generic;

// Deklariert die Klasse für die Knoten des Graphen
class Node
{
	public int index;
	public string value;
	public HashSet<Node> adjacentNodes = new HashSet<Node>(); // Menge der Nachbarknoten
}

// Deklariert die Klasse für den ungerichteten Graphen
class UndirectedGraph
{
	public HashSet<Node> nodes = new HashSet<Node>();
	
	// Diese Methode verbindet die Knoten node1 und node2 miteinander.
	public void ConnectNodes(Node node1, Node node2)
	{
		node1.adjacentNodes.Add(node2);
		node2.adjacentNodes.Add(node1);
	}
}

class Program
{
	// Diese Methode gibt die Knoten in der Form A, B, C, ... als Text zurück.
	public static string ToString(HashSet<Node> nodes)
	{
		string text = "";
		foreach (Node node in nodes) // foreach-Schleife, die alle Knoten der Komponente durchläuft
		{
			text += node.value + ", ";
		}
		text = text.Substring(0, text.Length - 2);
		return text;
	}
	
	// Hauptmethode, die das Programm ausführt
	public static void Main(string[] args)
	{
		// Deklariert und initialisiert 5 Knoten
		Node node1 = new Node{index = 0, value = "A"};
		Node node2 = new Node{index = 1, value = "B"};
		Node node3 = new Node{index = 2, value = "C"};
		Node node4 = new Node{index = 3, value = "D"};
		Node node5 = new Node{index = 4, value = "E"};
		// Deklariert und initialisiert ein Array mit den Knoten
		Node[] nodes = {node1, node2, node3, node4, node5};
		// Erzeugt einen ungerichteten Graphen
		UndirectedGraph undirectedGraph = new UndirectedGraph();
		int numberOfNodes = nodes.Length;
		for (int i = 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);
		
		int minimumDegree = numberOfNodes;
		HashSet<Node> nodesWithMinimumDegree = new HashSet<Node>();
		int maximumDegree = 0;
		HashSet<Node> nodesWithMaximumDegree = new HashSet<Node>();
		for (int i = 0; i < numberOfNodes; i++) // for-Schleife, die alle Knoten durchläuft
		{
			// Bestimmt den Minimalgrad und den Maximalgrad und die entsprechenden Knoten des Graphen
			Node node = nodes[i];
			int degree = 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();
	}
}

Literatur

Einzelnachweise 

Grundbegriff (Graphentheorie)