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
Arten: Neben induzierten Teilgraphen gibt es allgemeinere Untergraphen, bei denen E'⊆E gewählt wird, ohne dass alle
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
Verwendung: Teilgraphen dienen der Untersuchung von Strukturen, Pfaden, Kreisen und anderen Eigenschaften von Graphen. Sie sind