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

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

In einem ungerichteten Graphen $G$ ist für jeden Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} der Grad Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d_G(v)} definiert als die Anzahl aller Kanten von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} , die an Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} angrenzen. Sofern vorhanden werden Schlingen dabei doppelt gezählt.

Statt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d_G(v)} wird oft auch die Notation Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \deg_G(v)} verwendet. Der Index Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} kann weggelassen werden, falls klar ist, um welchen Graphen es sich handelt.

Den kleinsten Grad eines Knotens in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} nennt man den Minimalgrad von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G } und bezeichnet diesen mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \delta (G)} , den größten Grad eines Knotens in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G } nennt man den Maximalgrad von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G } , dieser wird meist mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Delta ( G ) } bezeichnet. Der Durchschnitt aller Knotengrade von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} wird Durchschnittsgrad genannt und mit $d(G)$ bezeichnet.

Gerichtete Graphen

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

In einem gerichteten Graphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} wird unterschieden, ob eine Kante an einem Knoten beginnt oder endet. Mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d^-_G(v)} bezeichnet man den Eingangsgrad des Knotens Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle v} in einem gerichteten Graphen Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} und mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d_G^+(v)} dessen Ausgangsgrad.

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

Einen Knoten ohne Eingangskanten (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d_G^-(v)=0} ) nennt man Quelle, einen Knoten ohne Ausgangskanten (Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle d_G^+(v)=0} ) nennt man Senke.

Eigenschaften

Stets gilt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 $2\cdot |E|=\sum _{v\in V(G)}d_{G}(v)$ , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

Planare Graphen

Zusammenhängende planare Graphen mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |V| } Knoten, $|E|$ Kanten und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |F| } Flächen erfüllen die Ungleichung Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |V| - |E| + |F| = 2 } (Eulerscher Polyedersatz) folgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle |E| \leq 3 \cdot |V| - 6} und daraus folgt für den durchschnittlichen Knotengrad

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\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.

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.^[1]

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

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

Einzelnachweise

↑ GeeksforGeeks: Print nodes having maximum and minimum degrees

[1] GeeksforGeeks: Print nodes having maximum and minimum degrees

[1]

Anonym

Suche

Grad (Graphentheorie)

Namensräume

Mehr

Seitenaktionen

Inhaltsverzeichnis

Definition

Ungerichtete Graphen

Gerichtete Graphen

Verwandte Begriffe

Eigenschaften

Planare Graphen

Verwendung

Programmierung

Literatur

Einzelnachweise

Navigation

Navigation

Mitmachen

Wikiwerkzeuge

Wikiwerkzeuge

Anonym

Suche

Grad (Graphentheorie)

Definition

Ungerichtete Graphen

Gerichtete Graphen

Verwandte Begriffe

Eigenschaften

Planare Graphen

Verwendung

Programmierung

Literatur

Einzelnachweise

Navigation

Wikiwerkzeuge

Seitenwerkzeuge

Weitere Projekte

Kategorien