Zusammenhang (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Zusammenhang von Graphen)
Datei:ZusammenhängenderGraphMitKantenzug.PNG
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 heißt zusammenhängend, wenn seine Knoten paarweise durch eine Kantenfolge verbunden sind.

Definition

Ungerichtete Graphen

Dieser nicht zusammenhängende Graph hat zwei Komponenten. Die Knoten v und w sind nicht durch einen Weg verbunden.

Ein ungerichteter Graph 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=(V,E)} heißt zusammenhängend, falls es zu je zwei beliebigen 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} , 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 \in V} einen ungerichteten Weg 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} 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} als Startknoten 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 w} als Endknoten gibt.

Einen maximalen zusammenhängenden Teilgraphen 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 Erdős-Rényi-Modell eine wichtige Rolle.

Gerichtete Graphen

Ein gerichteter Graph 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=(V,E)} heißt zusammenhängend von einem 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} aus, falls es zu jedem 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 w} aus 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} einen gerichteten Weg 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} 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 v} nach gibt. heißt stark zusammenhängend, falls 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} von jedem Knoten aus zusammenhängend ist. Anders formuliert heißt 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} stark zusammenhängend, falls es zwischen zwei beliebigen 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} 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 w} aus 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} sowohl einen gerichteten Weg 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 v} nach 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 w} als auch einen gerichteten Weg 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 w} nach 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 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} gibt.

Ein induzierter Teilgraph 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[U]} für eine Knotenmenge 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 U\subset V} heißt starke Zusammenhangskomponente 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} , falls stark zusammenhängend ist und nicht zu einem größeren stark zusammenhängenden Teilgraphen 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} 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:

  1. Jeder zusammenhängende ungerichtete Graph 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 n} Knoten enthält mindestens 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 n-1} Kanten.
  2. Jeder stark zusammenhängende gerichtete Graph 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 n} Knoten enthält mindestens 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 n} Kanten.
  3. Ein ungerichteter Graph ist genau dann zusammenhängend, wenn er einen Spannbaum enthält.
  4. Ein gerichteter Graph ist genau dann stark zusammenhängend, wenn seine Adjazenzmatrix irreduzibel ist. Damit ist auch ein ungerichteter Graph genau dann zusammenhängend, wenn seine Adjazenzmatrix irreduzibel ist.
  5. Die Klasse aller zusammenhängenden Graphen ist nicht axiomatisierbar.[1]

Verallgemeinerungen

Eine wesentliche Verallgemeinerung des Begriffs stellt der Begriff des 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 Tarjan (1972) stammt ein linearer Algorithmus zum Bestimmen der starken Zusammenhangskomponenten in gerichteten Graphen. Leicht modifiziert findet dieser Algorithmus in ungerichteten Graphen die Blöcke und Artikulationen ebenfalls in linearer Zeit.[2]

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

Die Anzahl der zusammenhängenden ungerichteten 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 n} Knoten steigt rasant mit der Anzahl der Knoten, und zwar etwa exponentiell zur Anzahl 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 \tfrac{n \cdot (n - 1)}{2}} der Kanten des vollständigen Graphen , also etwa proportional zu 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^{\tfrac{n \cdot (n - 1)}{2}}} . Wenn die Knoten nicht nummeriert sind, isomorphe Graphen also nicht mitgezählt werden, ist diese Anzahl etwa proportional zu 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 \tfrac{1}{n!} \cdot 2^{\tfrac{n \cdot (n - 1)}{2}}} , weil für die meisten Isomorphieklassen alle Graphen, die sich durch Permutation der nummerierten Knoten ergeben, verschieden sind. Die folgende Tabelle zeigt die mit Hilfe eines Computers bestimmten Anzahlen für 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 n \leq 8} :[3][4]

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# 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 die Anzahl der Komponenten des Graphen auf der Konsole ausgibt.[5] 

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();
	}
}

Literatur

  • Lutz Volkmann: Fundamente der Graphentheorie. Springer, Wien 2001, ISBN 3-211-82774-9.
  • Reinhard Diestel: Graphentheorie. Springer 2006, ISBN 3-540-21391-0 (englische Version).

Weblinks

Einzelnachweise

  1. ↑ Heinz-Dieter Ebbinghaus, Jörg Flum, Wolfgang Thomas: Einführung in die mathematische Logik. 2018, doi:10.1007/978-3-662-58029-5.
  2. ↑ 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.
  3. ↑ Folge A001187 in OEIS
  4. ↑ Folge A001349 in OEIS
  5. ↑ GeeksforGeeks: Connected Components in an undirected graph
Abgerufen von „https://de.wikiup.org/index.php?title=Zusammenhang_(Graphentheorie)&oldid=223538114“