Teilgraphen

In der Mathematik, insbesondere in der Graphentheorie, ist ein Teilgraph G'=(V',E') eines Graphen G=(V,E) ein Graph, der aus einer Teilmenge V'⊆V der Knoten und einer Teilmenge E'⊆E der Kanten von G besteht, wobei jede Kante in E' zwei Endpunkte in V' verbindet. Formal gilt: V'⊆V, E'⊆E, und für jede Kante {u,v}∈E' liegen u und v in V'.

Induzierter Teilgraph: Für eine Teilmenge V'⊆V(G) besitzt der induzierte Teilgraph G[V'] die Vertexmenge V' und die Kantenmenge E'={ {u,v} ∈ E(G) : u∈V' und v∈V' }. Er enthält alle Kanten von G, deren Endpunkte in V' liegen.

Arten: Neben induzierten Teilgraphen gibt es allgemeinere Untergraphen, bei denen E'⊆E gewählt wird, ohne dass alle Kanten zwischen V' enthalten sein müssen. Eine weitere übliche Unterkategorie ist der edge-induced subgraph, bei dem eine Kantenmenge E'⊆E gewählt wird und die Vertexmenge durch die Endpunkte von E' festgelegt wird.

Beispiel: Sei G ein Graph mit V={a,b,c,d} und E={(a,b),(b,c),(c,d),(d,a)}. Wählt man V'={a,b,c}, erhält man den induzierten Teilgraphen G[V'] mit V' und E'={(a,b),(b,c)}. Als Untergraph könnte man E''={{a,b}} und damit V''={a,b} betrachten.

Verwendung: Teilgraphen dienen der Untersuchung von Strukturen, Pfaden, Kreisen und anderen Eigenschaften von Graphen. Sie sind grundlegende Bausteine in Algorithmen zur Erkennung von Unterstrukturen, zur Analyse von Planarität, Konnektivität und zur Formulierung von Theoremen über globale Eigenschaften anhand lokaler Strukturen.