imported>Maximum 2520: /* Kombinatorik */ Diagramm hinzugefügt

2025-05-01T19:42:14Z

Kombinatorik: Diagramm hinzugefügt

Neue Seite

[[Datei:ZusammenhängenderGraphMitKantenzug.PNG|200px|mini|Ein zusammenhängender Graph: Je zwei Knoten sind durch eine Kantenfolge verbunden. Exemplarisch ist eine Kantenfolge zwischen den Knoten v und w rot hervorgehoben.]]
Der '''Zusammenhang''' ist ein mathematischer Begriff aus der [[Graphentheorie]]. Ein [[Graph (Graphentheorie)|Graph]] heißt zusammenhängend, wenn seine [[Knoten (Graphentheorie)|Knoten]] paarweise durch eine [[Kantenfolge]] verbunden sind.

== Definition ==
=== Ungerichtete Graphen ===
[[Datei:UnzusammenhängenderGraphZweiKomponenten.PNG|200px|mini|Dieser nicht zusammenhängende Graph hat zwei Komponenten. Die Knoten v und w sind nicht durch einen Weg verbunden.]]
Ein [[ungerichteter Graph]] <math>G=(V,E)</math> heißt ''zusammenhängend'', falls es zu je zwei beliebigen [[Knoten (Graphentheorie)|Knoten]] <math>v</math>,<math>w</math> <math>\in V</math> einen [[Ungerichteter Weg|ungerichteten Weg]] in <math>G</math> mit <math>v</math> als Startknoten und <math>w</math> als Endknoten gibt.

Einen maximalen zusammenhängenden [[Teilgraph]]en eines Graphen nennt man eine ''Komponente'' oder ''Zusammenhangskomponente''. Ein nicht zusammenhängender Graph wird durch seine Zusammenhangskomponenten partitioniert. Die größte Zusammenhangskomponente eines Graphen spielt im [[Zufallsgraph|Erdős-Rényi-Modell]] eine wichtige Rolle.

=== Gerichtete Graphen ===
Ein [[gerichteter Graph]] <math>G=(V,E)</math> heißt ''zusammenhängend von einem Knoten'' <math>v</math> ''aus'', falls es zu jedem Knoten <math>w</math> aus <math>V</math> einen [[Gerichteter Weg|gerichteten Weg]] in <math>G</math> von <math>v</math> nach <math>w</math> gibt. <math>G</math> heißt ''stark zusammenhängend'', falls <math>G</math> von jedem Knoten aus zusammenhängend ist. Anders formuliert heißt <math>G</math> ''stark zusammenhängend'', falls es zwischen zwei beliebigen Knoten <math>v</math> und <math>w</math> aus <math>V</math> sowohl einen gerichteten Weg von <math>v</math> nach <math>w</math> als auch einen gerichteten Weg von <math>w</math> nach <math>v</math> in <math>G</math> gibt.

Ein induzierter [[Teilgraph]] <math>G[U]</math> für eine Knotenmenge <math>U\subset V</math> heißt ''starke Zusammenhangskomponente'' von <math>G</math>, falls <math>G[U]</math> stark zusammenhängend ist und nicht zu einem größeren stark zusammenhängenden Teilgraphen von <math>G</math> erweitert werden kann.

Ein [[gerichteter Graph]] heißt ''(schwach) zusammenhängend'', falls der zugehörige ungerichtete Graph (also der Graph, der entsteht, wenn man jede gerichtete Kante durch eine ungerichtete Kante ersetzt) zusammenhängend ist.

== Wichtige Aussagen und Sätze ==
Relativ leicht zeigt man folgende Aussagen:
#Jeder zusammenhängende [[Ungerichteter Graph|ungerichtete Graph]] mit <math>n</math> [[Knoten (Graphentheorie)|Knoten]] enthält mindestens <math>n-1</math> [[Kante (Graphentheorie)|Kanten]].
#Jeder stark zusammenhängende [[Gerichteter Graph|gerichtete Graph]] mit <math>n</math> Knoten enthält mindestens <math>n</math> Kanten.
#Ein ungerichteter Graph ist genau dann zusammenhängend, wenn er einen [[Spannbaum]] enthält.
#Ein gerichteter Graph ist genau dann stark zusammenhängend, wenn seine [[Adjazenzmatrix]] [[Irreduzible Matrix|irreduzibel]] ist. Damit ist auch ein ungerichteter Graph genau dann zusammenhängend, wenn seine Adjazenzmatrix irreduzibel ist.
#Die Klasse aller zusammenhängenden Graphen ist nicht axiomatisierbar.<ref>{{Literatur |Autor=Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas |Titel=Einführung in die mathematische Logik |Datum=2018 |DOI=10.1007/978-3-662-58029-5}}</ref>

== Verallgemeinerungen ==
Eine wesentliche Verallgemeinerung des Begriffs stellt der Begriff des [[K-Zusammenhang|k-fachen Knotenzusammenhangs]], der [[Kantenzusammenhang]] und der [[Bogenzusammenhang]] dar.

== Algorithmen ==
Mittels [[Tiefensuche]] lässt sich ein [[linearer Algorithmus]] implementieren, der die Zusammenhangskomponenten eines ungerichteten Graphen berechnet und somit auch testet, ob der Graph zusammenhängend ist. Der Test, ob ein gerichteter Graph von einem Knoten ''v'' aus zusammenhängend ist, funktioniert analog. Von [[Robert Tarjan|Tarjan]] (1972) stammt ein linearer [[Algorithmus von Tarjan zur Bestimmung starker Zusammenhangskomponenten|Algorithmus zum Bestimmen der starken Zusammenhangskomponenten]] in gerichteten Graphen. Leicht modifiziert findet dieser Algorithmus in ungerichteten Graphen die [[K-Zusammenhang#Definition|Blöcke]] und [[Gelenkpunkt (Graphentheorie)|Artikulationen]] ebenfalls in linearer Zeit.<ref>Robert Tarjan: ''Depth-first search and linear graph algorithms''. In: ''SIAM Journal on Computing''. Bd. 1 (1972), Nr. 2, S. 146–160, {{DOI|10.1137/0201010}}.</ref>

Ein einfacher Algorithmus, der prüft, ob ein Graph zusammenhängend ist, kann wie folgt formuliert werden:

* Beginne an einem beliebigen Knoten des Graphen.
* Durchsuche von diesem Knoten aus entweder mit [[Tiefensuche]] oder mit [[Breitensuche]] den Graphen weiter, solange noch unbesuchte Nachbarknoten existieren.
* Der Graph ist genau dann zusammenhängend, wenn am Ende die Anzahl der von der Suche erreichten Knoten gleich der Anzahl der Knoten des Graphen ist.

== Kombinatorik ==
[[Datei:4 vertices-connected graphs.svg|mini|Die 38 verschiedenen Graphen mit 4 (implizit) nummerierten [[Knoten (Graphentheorie)|Knoten]]. Diese 38 Graphen bilden 6 [[Isomorphieklasse]]n. Die Graphen mit 5 [[Kante (Graphentheorie)|Kanten]] (Spalte 5) bilden 1 Isomorphieklasse, ebenso der [[Vollständiger Graph|vollständige Graph]] in Spalte 6. Die Graphen in Spalte 3 bilden 2 Isomorphieklassen, ebenso die Graphen in Spalte 4.]]
Die Anzahl der zusammenhängenden [[Ungerichteter Graph|ungerichteten Graphen]] mit <math>n</math> [[Knoten (Graphentheorie)|Knoten]] steigt rasant mit der Anzahl der Knoten, und zwar etwa [[Exponentieller Verlauf|exponentiell]] zur Anzahl <math>\tfrac{n \cdot (n - 1)}{2}</math> der [[Kante (Graphentheorie)|Kanten]] des [[Vollständiger Graph|vollständigen Graphen]] <math>K_n</math>, also etwa [[Proportionalität|proportional]] zu <math>2^{\tfrac{n \cdot (n - 1)}{2}}</math>. Wenn die Knoten nicht nummeriert sind, [[Isomorphie von Graphen|isomorphe Graphen]] also nicht mitgezählt werden, ist diese Anzahl etwa [[Proportionalität|proportional]] zu <math>\tfrac{1}{n!} \cdot 2^{\tfrac{n \cdot (n - 1)}{2}}</math>, weil für die meisten [[Isomorphieklasse]]n alle <math>n!</math> Graphen, die sich durch [[Permutation]] der nummerierten Knoten ergeben, verschieden sind. Die folgende [[Tabelle]] zeigt die mit Hilfe eines [[Computer]]s bestimmten Anzahlen für <math>n \leq 8</math>:<ref>{{OEIS|A001187}}</ref><ref>{{OEIS|A001349}}</ref>

{| class="wikitable" style="text-align:right"
! colspan="3"|Anzahl der zusammenhängenden ungerichteten Graphen
|-
! n
! mit nummerierten Knoten
!ohne nummerierte Knoten
|-
! 2
| 1
|1
|-
! 3
| 4
|2
|-
! 4
| 38
|6
|-
! 5
| 728
|21
|-
! 6
| 26704
|112
|-
! 7
| 1866256
|853
|-
! 8
| 251548592
|11117
|}

== Programmierung ==
Das folgende Beispiel in der [[Programmiersprache]] [[C-Sharp|C#]] zeigt die Implementierung eines ungerichteten Graphen mit [[Adjazenzliste]]n. Der ungerichtete Graph wird als [[Klasse (Objektorientierung)|Klasse]] ''UndirectedGraph'' deklariert. Bei der Ausführung des Programms wird die [[Methode (Programmierung)|Methode]] ''Main'' verwendet, die die Anzahl der Komponenten des Graphen auf der Konsole ausgibt.<ref>GeeksforGeeks: [https://www.geeksforgeeks.org/connected-components-in-an-undirected-graph/ Connected Components in an undirected graph]</ref>
<syntaxhighlight lang="c#">
using System;
using System.Collections.Generic;
using System.Linq;

// 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 Komponente des Graphen 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);
text += ")";
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);
HashSet<Node> remainingNodes = new HashSet<Node>(); // Menge der verbleibender Knoten, die noch nicht durchlaufen wurden
for (int i = 0; i < numberOfNodes; i++)
{
remainingNodes.Add(nodes[i]); // Fügt die Knoten der Menge der verbleibender Knoten hinzu
}
int numberOfComponents = 1;
HashSet<Node> newNodes = new HashSet<Node>(); // Menge der neu durchlaufenen Knoten
newNodes.Add(remainingNodes.ElementAt(0)); // Dieser Menge einen neuen Knoten hinzufügen
HashSet<Node> currentComponent = new HashSet<Node>(); // Menge der Knoten für die aktuelle Komponente
while (remainingNodes.Count > 0) // So lange noch nicht alle Knoten durchlaufen wurden
{
HashSet<Node> currentNodes = new HashSet<Node>(); // Menge für die aktuell durchlaufenen Knoten
if (newNodes.Count == 0) // Wenn keine neuen Knoten durchlaufen wurden
{
Console.WriteLine(ToString(currentComponent)); // Gibt die Knoten der aktuellen Komponente auf der Konsole aus
currentComponent.Clear();
numberOfComponents++; // Zähler für die Anzahl der Komponenten um 1 erhöhen
currentNodes.Add(remainingNodes.ElementAt(0)); // Neuen Knoten durchlaufen
}
else
{
foreach (Node node in newNodes) // foreach-Schleife, die alle neuen Knoten durchläuft
{
currentNodes.Add(node); // Fügt die neuen Knoten der Menge der aktuellen Knoten hinzu
}
}
newNodes.Clear(); // Leert die Menge der neu durchlaufenen Knoten
foreach (Node node in currentNodes) // foreach-Schleife, die alle aktuellen Knoten durchläuft
{
if (remainingNodes.Contains(node)) // Wenn der aktuelle Knoten noch nicht durchlaufen wurde
{
currentComponent.Add(node); // Fügt den aktuellen Knoten der Menge der Knoten für die aktuellen Komponente hinzu
remainingNodes.Remove(node);
}
foreach (Node nextNode in node.adjacentNodes) // foreach-Schleife, die alle benachbarten Knoten des aktuellen Knotens durchläuft
{
if (remainingNodes.Contains(nextNode))
{
currentComponent.Add(nextNode); // Fügt den benachbarten Knoten der Menge der Knoten für die aktuellen Komponente hinzu
newNodes.Add(nextNode); // Fügt diesen Knoten der Menge der neu durchlaufenen Knoten
remainingNodes.Remove(nextNode);
}
}
}
}
Console.WriteLine(ToString(currentComponent)); // Gibt die Knoten der aktuellen Komponente auf der Konsole aus
Console.WriteLine("Der Graph besteht aus " + numberOfComponents + " Komponenten."); // Ausgabe auf der Konsole

Console.ReadLine();
}
}
</syntaxhighlight>

== Literatur ==
* Lutz Volkmann: ''Fundamente der Graphentheorie.'' Springer, Wien 2001, ISBN 3-211-82774-9.
* Reinhard Diestel: ''Graphentheorie.'' Springer 2006, ISBN 3-540-21391-0 ([https://diestel-graph-theory.com/basic.html englische Version]).

== Weblinks ==
* Wolfram Mathworld: [https://mathworld.wolfram.com/ConnectedGraph.html ''Connected Graph'']

== Einzelnachweise ==
<references />

[[Kategorie:Grundbegriff (Graphentheorie)]]

Zusammenhang (Graphentheorie) - Versionsgeschichte

imported>Maximum 2520: /* Kombinatorik */ Diagramm hinzugefügt