Teilgraphen und Minoren

Bei der Untersuchung von Graphen<nowiki></nowiki>eigenschaften schließt man häufiger von lokalen auf globale Eigenschaften von Graphen und umgekehrt. Um derartige Vorgänge besser beschreiben zu können, definiert man geeignete Relationen zwischen Graphen und lokalen Gebieten innerhalb dieser Graphen. Besonders wichtig sind dabei Teilgraphenbeziehungen. Die Begriffe Teilgraph und Untergraph sind Spezialfälle der entsprechenden allgemeineren Begriffe Teil-Struktur und Unter-Struktur aus der Modelltheorie. Eine Unter-Struktur ist anschaulich gesehen ein Ausschnitt aus einer Struktur, bei der alle Beziehungen zwischen den Elementen (bzw. Knoten) erhalten bleiben. Beispiel siehe unten: G2, G3 sind Untergraphen von G, aber G1 ist kein Untergraph, sondern nur ein Teilgraph von G. In Teil-Strukturen können also zusätzlich noch Beziehungen zwischen den Elementen wegfallen. Jede Unter-Struktur ist eine Teil-Struktur aber nicht umgekehrt. Im folgenden werden beide Begriffe für Graphen näher definiert.

Anschaulich bedeutet es folgendes: Um aus einem Graphen G einen Teilgraph T zu erzeugen wählt man beliebige Knoten aus G und fügt sie T hinzu. Einen Teilgraph erhält man, indem man einige Kanten von T´s Knoten auch zu T hinzufügt. Einen Untergraphen erhält man, indem man alle Kanten zwischen T´s Knoten zu T hinzufügt.

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