|
|
Formelsammlung Mathe |
Inhalt
-
Grundlagen der Mathematik
-
Diskrete Mathematik- Kombinatorik- Graphentheorie- Typen von Graphen
Teilgraphen und Minoren Vollständiger Graph Bipartiter Graph- Wälder- Bäume Spannbaum Binärbaum- Planarer Graph Nachbarschaft und Grad Wege, Pfade, Zyklen und 
Kreise Isomorphie von Graphen Operationen auf Graphen Zusammenhang- Durchlaufbarkeit von Graphen- Färbung Paarungen in Graphen- Schnitte Knotenüberdeckungen, Cliquen und stabile Mengen- Zahlentheorie- Algebra- Lineare Algebra- Geometrie- Analysis- Differentialgleichungen- Funktionalanalysis- Differentialgeometrie- Topologie- Numerik- Stochastik- Unsortiertes- Anbieterkennzeichnung
Bäume in der Graphentheorie
Ein Baum ist in der Graphentheorie ein spezieller Graph, mit dem sich eine Monohierarchie modellieren lässt. Je nachdem, ob die Kanten des Baums eine ausgezeichnete Richtung besitzen, lassen sich graphentheoretische Bäume unterteilen in ungerichtete Bäume und gewurzelte Bäume, und für gewurzelte Bäume in Out-Trees, bei denen die Kanten von der Wurzel ausgehen, und In-Trees, bei denen Kanten in Richtung Wurzel zeigen.
In der Informatik werden Bäume häufig als Datenstruktur eingesetzt. In diesem Fall werden sie aber anders repräsentiert als allgemeine Graphen. Durch Entfernen einer Kante zerfällt ein Baum in zwei Teilbäume und bildet damit einen so genannten Wald.
Spezielle Bäume
Es existiert eine Vielzahl von Begriffen, die Bäume näher spezifizieren. So gibt es zum Beispiel
- Binärbäume,
- Binomialbäume,
- balancierte Bäume und
- vollständige Binärbäume.
Bäume als Datenstruktur
Gewurzelte Bäume, insbesondere Out-Trees, werden häufig als Datenstruktur verwendet. Bei beschränkter Ordnung können diese so implementiert werden, dass jeder Knoten einen festen Satz an Variablen oder ein Array für die Referenzen auf seine Kinder enthält. Häufig besitzen die Knoten auch eine Referenz auf ihren Elternknoten (back pointer). Ein Baum unbeschränkter Ordnung kann implementiert werden, indem man statt Arrays dynamische Listen verwendet. In Programmiersprachen ohne dynamische Listen hat sich auch ein Verfahren bewährt, bei dem ein allgemeiner Baum durch einen Binärbaum implementiert wird:
| Allgemeiner Baum, der durch einen Binärbaum repräsentiert wird |
Siehe auch
- graphentheoretische Wälder
- Baumweite
- Baumzerlegung
Es gibt keinen Königsweg zur Mathematik.
Euklid
Copyright- und Lizenzinformationen zu dieser Seite
Amazon.de empfiehlt:
Graphentheorie: Eine anwendungsorientierte Einführung
Peter Tittmann
Reinhard Diestel
Diskrete Strukturen 1. Kombinatorik, Graphentheorie, Algebra
Angelika Steger
Graphen für Einsteiger: Rund um das Haus vom Nikolaus
Manfred Nitzsche
Volker Turau
Diskrete Mathematik: Eine Entdeckungsreise
Jiri Matousek
Bücher zum Thema Graphentheorie auf
•
bol.de
•
buch.de
•
buecher.de
•
libri.de