1889 veröffentlichte der englische Mathematiker Arthur Cayley einen Aufsatz mit dem Titel »A Theorem on Trees«. Darin ging es allerdings nicht um die mathematische Betrachtung von Wäldern – na ja, eigentlich beschäftigt sich der Text schon ausschließlich mit der mathematischen Betrachtung von Bäumen. Nur dass »Bäume« hier nichts mit dem zu tun haben, was in einem Wald wächst, sondern mit Graphentheorie. In Cayleys Artikel geht es um folgende Formel:

Um sie zu verstehen, müssen wir zuerst klären, was in der Mathematik als »Baum« bezeichnet wird: So nennt man einen »zusammenhängenden Graphen ohne Schleifen«, was ohne weitere Erläuterungen aber vermutlich wenig hilfreich ist. Ein Graph ist vereinfacht gesagt eine Struktur, die nicht nur eine Menge an Objekten, sondern auch die Verbindungen zwischen ihnen darstellt. Ein anschauliches Beispiel dafür ist die Darstellung des U-Bahn-Netzes einer Stadt. Die Stationen entsprechen dann den Knoten eines Graphen und die Strecken dazwischen den Kanten. Bei einem zusammenhängenden Graphen sind die Knoten durch eine entsprechende Abfolge von Kanten verbunden. Im Beispiel des U-Bahn-Netzes bedeutet das: Man kann von jeder Station zu allen anderen fahren, und es gibt keinen Bereich, der vom Rest isoliert ist. Eine Schleife ist in diesem Zusammenhang ein geschlossener Kantenzug, bei dem Start- und Endknoten (und nur diese beiden) identisch sind.

Mit einem Baum hat man es also genau dann zu tun, wenn man eine Menge an Knoten hat, die alle durch Kanten verbunden sind, es jedoch keinen geschlossenen Pfad zwischen diesen Knoten gibt. Die Formel von Cayley gibt an, wie viele verschieden bezeichnete Bäume (also Graphen, bei denen die Knoten nummeriert sind) für n Knoten existieren. n muss dabei logischerweise mindestens gleich 2 sein, und in diesem Fall gibt es genau einen Baum – nämlich den, in dem die beiden Knoten durch eine Kante verbunden sind. Für n = 3 kann man drei bezeichnete Bäume finden, bei vier Knoten sind es 16, und so weiter.

Wo Bäume sind, muss es Wälder geben. Das gilt auch in der Mathematik. Ein Graph ohne Schleife wird »Wald« genannt und die zusammenhängenden Komponenten dieses Waldes sind dann jeweils Bäume. In diesem Teil der Mathematik gibt es außerdem noch »Wurzeln« und »Blätter«, es gibt »Raupenbäume«, »spannende Bäume« und einen Haufen mehr Begriffe, die besser in einen Naturführer zu passen scheinen als in ein Mathematiklehrbuch. Aber gerade, wenn es um so etwas Abstraktes wie Graphentheorie geht, lohnt es sich, die Dinge zumindest ein wenig anschaulich zu benennen.

Ein abstrakter Bereich voller Anwendungen

Dass es auf jeden Fall sinnvoll ist, sich mit mathematischen Bäumen zu beschäftigen, ist leicht zu sehen. Wenn man es zum Beispiel mit Datenstrukturen und ihrer Sortierung zu tun hat, mit Entscheidungsabfolgen oder diversen abstrakten und konkreten Netzwerken, dann kommt man bei der Analyse ohne Graphen, Bäume und Wälder nicht weit. Der Erste, der die Cayley-Formel gefunden hat, war übrigens der deutsche Mathematiker Karl Wilhelm Borchardt. Doch Arthur Cayley hat sie im Kontext der von ihm mitbegründeten Graphentheorie formuliert und deswegen wird sie heute nach ihm benannt.

Falls jemand Lust bekommen hat, ebenfalls etwas zu diesem Gebiet beizutragen: Bis jetzt wurde noch keine geschlossene Formel gefunden, mit der man die Anzahl der nicht bezeichneten Bäume in Abhängigkeit ihrer Knoten berechnen kann. Vielleicht sollte man darüber mal bei einem Spaziergang durch einen echten Wald mit echten Bäumen nachdenken.