imported>DeWikiMan: /* Verwandte Begriffe */ wikilink, der Begriff "Nachbar" wurde weiter oben noch nicht eingeführt

2024-08-19T19:37:52Z

Verwandte Begriffe: wikilink, der Begriff "Nachbar" wurde weiter oben noch nicht eingeführt

Neue Seite

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

== Definition ==
=== Ungerichtete Graphen ===
[[Datei:UndirectedDegrees.svg|mini|Ein ungerichteter Graph. Die Knoten sind mit ihrem Grad beschriftet.]]

In einem [[Ungerichteter Graph|ungerichteten Graphen]] <math>G</math> ist für jeden [[Knoten (Graphentheorie)|Knoten]] <math>v</math> der Grad <math>d_G(v)</math> definiert als die Anzahl aller Kanten von <math>G</math>, die an <math>v</math> angrenzen.
Sofern vorhanden werden [[Schlinge (Graphentheorie)|Schlingen]] dabei doppelt gezählt.

Statt <math>d_G(v)</math> wird oft auch die Notation <math>\deg_G(v)</math> verwendet. Der Index <math>G</math> kann weggelassen werden, falls klar ist, um welchen Graphen es sich handelt.

Den kleinsten Grad eines [[Knoten (Graphentheorie)|Knotens]] in <math>G</math> nennt man den '''Minimalgrad''' von <math> G </math> und bezeichnet diesen mit <math> \delta (G)</math>, den größten Grad eines Knotens in <math> G </math> nennt man den '''Maximalgrad''' von <math> G </math>, dieser wird meist mit <math> \Delta ( G ) </math> bezeichnet. Der [[Mittelwert|Durchschnitt]] aller Knotengrade von <math> G</math> wird '''Durchschnittsgrad''' genannt und mit <math> d(G) </math> bezeichnet.

=== Gerichtete Graphen ===
[[Datei:DirectedDegrees.svg|mini|Ein gerichteter Graph mit beschrifteten Knoten: (Eingangsgrad, Ausgangsgrad)]]
In einem [[Gerichteter Graph|gerichteten Graphen]] <math>G</math> wird unterschieden, ob eine [[Kante (Graphentheorie)|Kante]] an einem [[Knoten (Graphentheorie)|Knoten]] beginnt oder endet. Mit <math>d^-_G(v)</math> bezeichnet man den '''Eingangsgrad''' des Knotens <math>v</math> in einem gerichteten Graphen <math>G</math> und mit <math>d_G^+(v)</math> dessen '''Ausgangsgrad'''.

Dabei ist <math>d_G^-(v)</math> die Anzahl aller Kanten, die in <math>v</math> enden
und <math>d_G^+(v)</math> die Anzahl aller Kanten, die in <math>v</math> starten.

Einen [[Knoten (Graphentheorie)|Knoten]] ohne Eingangskanten (<math>d_G^-(v)=0</math>) nennt man '''Quelle''', einen Knoten ohne Ausgangskanten (<math>d_G^+(v)=0</math>) nennt man '''Senke'''.

== Verwandte Begriffe ==
* Man nennt einen [[Knoten (Graphentheorie)|Knoten]] '''isoliert''', wenn er:
** in einem [[Ungerichteter Graph|ungerichteten Graphen]]: keine [[Nachbarschaft (Graphentheorie) |Nachbarn]] besitzt, <math>d_G =0</math>.
** in einem [[Gerichteter Graph|gerichteten Graphen]]: keine Vorgänger und keine Nachfolger besitzt, <math>d_G^+ = d_G^- =0</math>.

* Ein ungerichteter [[Graph (Graphentheorie)|Graph]] oder [[Hypergraph]] <math>G</math> heißt [[Regulärer Graph|regulär]], falls alle seine Knoten denselben Grad besitzen. Besitzen alle seine Knoten Grad <math>k</math>, so bezeichnet man <math>G</math> als ''k-regulär''. Einen 3-regulären Graphen bezeichnet man auch als [[Kubischer Graph|kubisch]].

* Ein gerichteter Graph <math>G</math> heißt ''regulär'', falls alle seine Knoten denselben Eingangs- und Ausgangsgrad besitzen. Besitzen alle seine Knoten Eingangs- und Ausgangsgrad <math>k</math>, so bezeichnet man <math>G</math> als ''k-regulär''.

* Ein [[Hypergraph]] <math>G</math> heißt '''uniform''', wenn alle [[Kante (Graphentheorie)|Kanten]] von <math>G</math> die gleiche Anzahl Knoten enthalten. Enthalten alle Kanten von <math>G</math> genau <math>k</math> Knoten, so nennt man <math>G</math> '''k-uniform'''.

== Eigenschaften ==
* Stets gilt <math> \delta (G) \leq d (G) \leq \Delta (G)</math>. Gleichheit tritt z. B. bei [[Vollständiger Graph|vollständigen Graphen]], allgemein bei [[Regulärer Graph|regulären Graphen]] ein.
* Es gilt <math>2 \cdot |E| = \sum_{v \in V(G)}d_G(v)</math>, wobei <math>|E|</math> 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ängender Graph|Zusammenhängende]] [[Planarer Graph|planare Graphen]] mit <math> |V| </math> [[Knoten (Graphentheorie)|Knoten]], <math> |E| </math> [[Kante (Graphentheorie)|Kanten]] und <math> |F| </math> Flächen erfüllen die [[Ungleichung]] <math> 2 \cdot |E| \geq 3 \cdot |F|</math>, weil jede Fläche benachbart zu mindestens drei Kanten und jede Kante genau zwei Flächen begrenzt. Daraus und aus der Gleichung <math> |V| - |E| + |F| = 2 </math> ([[Eulerscher Polyedersatz]]) folgt <math> |E| \leq 3 \cdot |V| - 6</math> und daraus folgt für den durchschnittlichen Knotengrad

: <math> 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</math>

Das heißt, dass für endliche [[Planarer Graph|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-Sharp|C#]] zeigt die Implementierung eines ungerichteten Graphen mit [[Adjazenzliste|Adjazenzlisten]]. Der ungerichtete Graph wird als [[Klasse (Objektorientierung)|Klasse]] ''UndirectedGraph'' deklariert. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''Main'' verwendet, die den Minimalgrad, den Maximalgrad und die entsprechenden [[Knoten (Graphentheorie)|Knoten]] des Graphen auf der Konsole ausgibt.<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/print-nodes-having-maximum-and-minimum-degrees/ Print nodes having maximum and minimum degrees]</ref><syntaxhighlight lang="c#">
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();
}
}
</syntaxhighlight>

== Literatur ==
* {{Literatur
|Autor=Reinhard Diestel
|Titel=Graphentheorie
|Verlag=Springer
|Ort=Berlin
|Datum=2010
|ISBN=978-3-642-14911-5}}

== Einzelnachweise ==
<references />

[[Kategorie:Grundbegriff (Graphentheorie)]]

Grad (Graphentheorie) - Versionsgeschichte

imported>DeWikiMan: /* Verwandte Begriffe */ wikilink, der Begriff "Nachbar" wurde weiter oben noch nicht eingeführt