Teilgraphen und Minoren

Definitionen

Untergraph bzw. Induzierter Teilgraph

Gilt zusätzlich:

• in Graphen ohne Mehrfachkanten,
  
  , d.h. G₁ enthält alle Kanten zwischen den Knoten in V₁, die auch in G₂ vorhanden sind.
• in ungerichteten Graphen mit Mehrfachkanten,
  
  für alle zweielementigen Teilmengen v von V₂,
• in gerichteten Graphen mit Mehrfachkanten,
  
  für alle v aus dem kartesischen Produkt V₂xV₂,

so bezeichnet man G₁ auch als den durch V₁ induzierten Teilgraph von G₂ und notiert diesen auch mit G₂ [V₁ ] oder auch einfach G_A (G=G₂, A=V₁).

Bemerkungen:

• Induzierte Teilgraphen sind immer eindeutig durch die entsprechende Knotenmenge festgelegt.
• Besonders wichtige Teilgraphen entstehen durch das Weglassen von Knoten bzw. Kanten. Sei der Graph G(V,E) gegeben, dann bezeichnet
  
  den Graphen, der durch Weglassen der Knoten aus A und aller mit diesen Knoten inzidenten Kanten entsteht. Die so entstehenden Teilgraphen sind immer induzierte Teilgraphen.

Copyright- und Lizenzinformationen: Diese Seite basiert auf dem Artikel Teilgraphen und Minoren aus der freien Enzyklοpädιe Wιkιpedιa und steht unter der Lizenz Creative Commons CC-BY-SA 3.0 Unported (Kurzfassung). Liste der Autoren

Anbieterkennzeichnung