Quellknoten

Quellknoten ist in der Graphentheorie ein Knoten in einem gerichteten Graphen, der keine eingehenden Kanten besitzt (In-Grad 0). Er dient häufig als Startpunkt für Traversierungen oder als Quelle in Fluss- und Verteilungsmodellen. Es kann mehrere Quellknoten geben, insbesondere in Graphen, die aus mehreren unverbundenen Teilstrukturen bestehen.

Eigenschaften: Ein Quellknoten kann ausgehende Kanten haben, mit denen er andere Knoten erreicht. In topologischen Sortieralgorithmen erscheinen Quellknoten zu Beginn, weil keine anderen Knoten in sie hineinragen. In Flussnetzen wird der Quellknoten oft als Ursprung des Flusses betrachtet; Gegenstück dazu ist der Senke bzw. Zielknoten, der den Fluss aufnimmt.

Anwendungen: Quellknoten treten in vielen Kontexten auf, etwa bei der Analyse von Datenfluss, Abhängigkeitsgraphen in Build-Systemen oder Verteilungsnetzen. In DAGs (gerichteten azyklischen Graphen) dienen Quellknoten als Startpunkte für die Bestimmung einer Abfolge von Berechnungen oder Aufgaben, da von ihnen aus keine Vorgänger existieren.

Beispiel: Betrachten Sie einen Graphen mit den Knoten A, B, C und D und den Kanten A->B, A->C, D->B. Die Knoten A und D haben keinen eingehenden Kanten, somit sind sie Quellknoten. Knoten B und C haben eingehende Kanten, C könnte je nach weiteren Kanten auch ein Quellknoten sein oder nicht.

Verwandte Begriffe: Senke (Zielknoten), Graph, Topologie, Netze und Flussnetzwerke.