1-Baum

Ein 1-Baum ist ein zusammenhängender Graph mit genau einem Kreis. Der Graph besitzt also n Knoten und n Kanten (ein gewöhnlicher Baum hat n Knoten und n-1 Kanten).

1 Baum mit ausgezeichneten Knoten

Der nachfolgende 1-Baum demonstriert, dass auch alle Knoten ausgezeichnet sein können. In diesem Fall haben sie alle den Knotengrad 2:

1 Baum alles ausgezeichnete Knoten

Einen minimalen 1-Baum eines Graphen lässt sich leicht mit dem Kruskal-Algorithmus konstruieren. Dafür wendet man den Kruskal-Algorithmus auf den gegebenen Graphen ohne den Knoten a an, sodass daraus ein minimaler spannender Baum entsteht. Erweitert man nun diesen Baum um den weggelassenen Knoten a und fügt die beiden am niedrigsten bewerteten Kanten (zu a) hinzu, dann hat man einen minimalen 1-Baum erzeugt.