Ein Subgraph (auch Teilgraph) ist ein Ausschnitt eines Graphen: Er besteht aus einer Teilmenge der Knoten und einer Teilmenge der Kanten eines Ausgangsgraphen, wobei jede übernommene Kante ihre beiden Endknoten im Subgraph haben muss. Formal: H = (V', E') ist Subgraph von G = (V, E), wenn V' ⊆ V und E' ⊆ E gilt und alle Kanten in E' zwischen Knoten aus V' verlaufen. Man schreibt H ⊆ G.
Wichtige Spezialfälle
- Induzierter Subgraph: Man wählt nur eine Knotenmenge V' und übernimmt alle Kanten von G, die zwischen Knoten aus V' verlaufen. Das Ergebnis ist durch die Knotenwahl eindeutig bestimmt.
- Aufspannender Subgraph: V' = V, man streicht nur Kanten. Der berühmteste Fall ist der minimale Spannbaum, der alle Knoten mit minimalem Gesamtgewicht verbindet.
- Teilgraph im engeren Sinn: beliebige Auswahl von Knoten und Kanten.
Eigenschaften
Subgraphen erben wichtige Eigenschaften des Ausgangsgraphen, können aber keine neuen hinzufügen: Ein Subgraph eines bipartiten Graphen bleibt bipartit, ein Subgraph eines planaren Graphen bleibt planar (man lässt in der Zeichnung nur Kanten weg), und ein Subgraph eines DAG kann keine neuen Zyklen bekommen. Umgekehrt gilt: Jeder Zusammenhangskomponente eines Graphen ist ein maximaler zusammenhängender Subgraph.
Anwendungen
- Subgraph-Isomorphie: In großen Netzwerken Vorkommen eines Mustergraphen finden (Social-Media-Analyse, Chemie).
- Daten-Modellierung: Ein gerichteter oder ungerichteter Graph teilt sich in relevante Teilgraphen für einzelne Abfragen.
- Visualisierung: Übersichtliche Ausschnitte statt des gesamten Graphen zeichnen.
Einordnung
Der Subgraph ist ein Grundkonzept der Graph-Datenstruktur und der Baum-Datenstruktur (jeder Unterbaum ist ein Subgraph). Zusammen mit gewichteten Graphen ergeben Subgraphen flexible Modelle, etwa Teilnetze mit eigenen Kosten. Bewusst nicht behandelt: die abstrakte Frage, ob zwei Graphen strukturell gleich sind (Graph-Isomorphie) — ein eigenes, komplexes Thema.