Teilbäume

Teilbäume bezeichnet in der Graphentheorie Teilgraphen eines Baums, die zusammenhängend und azyklisch sind. Formal sei T ein Baum mit der Knotmenge V und der Kantenmenge E. Ein Teilbaum U des Baums T besteht aus einer Teilmenge von Knoten U ⊆ V und allen Kanten aus E, die zwei Knoten in U verbinden. Der Teilbaum ist genau dann ein Baum, wenn dieser Teilgraph zusammenhängend ist.

Im Kontext von gerooteten Bäumen wird der Begriff häufig als der Wurzelteilbaum verstanden: Es handelt sich dabei um den Knoten v und alle seine Nachkommen in der gerichteten Baumstruktur, einschließlich v selbst. Je nach Darstellung bedeutet dies entweder der gesamte Unterbaum unterhalb von v oder der durch orientierte Kanten erreichbare Teilbaum mit Wurzel v.

Eigenschaften: Jeder Teilbaum eines Baums ist ein Baum. Die Größe eines Teilbaums reicht von einem einzelnen Knoten bis zur Gesamtstruktur des ursprünglichen Baums. Die Enumeration und Charakterisierung von Teilbäumen ist Gegenstand combinatorischer Studien und hängt von der betrachteten Baumstruktur ab.

Algorithmen und Anwendungen: Teilbäume werden durch Traversierungen wie Tiefensuche oder Breitensuche identifiziert und manipuliert. In der Praxis kommen dynamische Programmierung auf Bäumen zum Einsatz, um über Teilbäume zu zählen, Summen zu bilden oder Optimierungen vorzunehmen (zum Beispiel Summe der Gewichte, maximale Pfadlängen, Anzahl von Teilbäumen). Anwendungen finden sich in der Informatik, Bioinformatik, Linguistik und Datenstrukturen, etwa beim Strukturvergleich, Parsing oder beim Aufbau hierarchischer Indizes.

Siehe auch: Baum, Wurzelbaum, Teilgraph, Isomorphie.