Bäume
Ist ein ungerichteter Graph sowohl zusammenhängend als auch zykelfrei, so wird er Baum genannt. Der Name stammt daher, dass so ein Graph nur aus Verzweigungen bestehen kann, die dann insgesamt wie ein Baum aussehen. Die Knoten eines Baums, die nur einen Nachbarknoten haben, werden als Blätter bezeichnet.
Bäume sind im Bereich der diskreten Mathematik sehr praktisch . Beispielsweise erlauben sie eine Art vollständige Induktion für Graphen, bei der sukzessive Blätter entfernt werden. Hier werden sie im nächsten Abschnitt jedoch dafür genutzt, geordnete Listen effizient zu durchsuchen.
Sollen die obigen Begriffe zusammenhängend und zykelfrei für gerichtete Graphen definieren, muss meist darauf geachtet werden, was damit modelliert wird. Im einfachsten Fall funktioniert das wie folgt: Zu jedem gerichteten Graphen gibt es einen zugehörigen ungerichteten Graphen, der dadurch entsteht, dass die Orientierung der Kanten “vergessen” wird. Und dann wird die entsprechende Eigenschaft über diesen ungerichteten Graphen definiert. Also z. B.:
Wenn diese Eigenschaften direkt für gerichtete Graphen definiert werden, entstehen meist stärkere Eigenschaften. Wenn also z. B. definiert wird, dass ein gerichteter Graph keinen Zykel aus gerichteten Kanten haben soll, um als kreisfrei zu gelten, so wäre der Graph unten kreisfrei. Dies gilt aber nicht nach obiger Definition, bei der die Kantenorientierung ignoriert wird.
Eine andere Art sich dem Thema Bäume zu nähern, ist über sogenannte Spannbäume. Dies sind Teilgraphen eines gegebenen zusammenhängend Graphen, die
- Bäume sind und
- jeden Knoten des ursprünglichen Graphen enthalten.
Damit beschreiben sie ein Grundgerüst des gegebenen Graphen. Sie finden in der Praxis z. B. darin Anwendung, wenn Telefonnetze so wenig wie möglich Verbindungen haben sollen (da diese extra Bau- und Instandhaltungskosten bedeuten), aber trotzdem alle Anschlüsse miteinander verbunden sein sollen.
Dieser Ansatz wird nun in Szene 2: Graphen mit Zyklen und Bäumen verfolgt.
Weiterführende Informationen zur Einführung von Graphen finden Sie in (Aigner, 2015).