Teilgraphen und Minoren

Definitionen

Teilgraph

Ein Graph G₁ = (V₁ , E₁ ) heißt Teilgraph oder Subgraph von G₂ = (V₂ , E₂ ), falls V₁ Teilmenge von V₂, also und

• in Graphen ohne Mehrfachkanten E₁ Teilmenge von E₂ ist, ,
• in ungerichteten Graphen mit Mehrfachkanten für alle zweielementigen Teilmengen v von V₂, also
  
  , gilt, wobei E_1/2 (v) die Menge der Kanten zwischen den Knoten aus v ist,
• in gerichteten Graphen mit Mehrfachkanten für alle Teilmengen v aus dem kartesischen Produkt V₂xV₂ gilt.

Umgekehrt heißt G₂ Supergraph oder Obergraph von G₁.

Bei einem knotengewichteten bzw. kantengewichteten Graph G₂ wird von einem Teilgraph G₁ zudem verlangt, dass die Gewichtsfunktion g₁ von G₁ kompatibel zu der Gewichtsfunktion g₂ von G₂ ist, d.h. für jeden Knoten v bzw. für jede Kante e von G₂ giltg₁ (v) = g₂ (v)bzw g₁ (e) = g₂ (e).

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