Knotenebenen

Knotenebenen sind ein Konzept aus der Informatik und Graphentheorie, das die horizontale Struktur eines Graphen oder Netzwerks beschreibt. Sie ordnen Knoten zu Ebenen nach einer gemeinsamen Eigenschaft, üblicherweise nach ihrer Tiefe oder Distanz zu einem bestimmten Wurzelknoten. Die Ebene eines Knotens kann durch eine Funktion L(v) bestimmt werden, die ganzzahlige Werte annimmt, wobei L(v)=0 oft die Ausgangsebene markiert und höhere Werte tiefer gelegene Ebenen kennzeichnen.

In der Praxis dienen Knotenebenen dazu, Hierarchien sichtbar zu machen und die Darstellung oder Analyse zu erleichtern. In hierarchischen Graphlayout-Algorithmen wird häufig gefordert, dass Kanten nur zwischen benachbarten Ebenen verbinden, um die Lesbarkeit zu verbessern und Kreuzungen zu reduzieren. Ebenen finden sich außerdem in der Tiefen- oder Distanzstruktur von Graphen, in BFS-Durchläufen, in Netzplänen sowie in der Struktur mehrschichtiger Netzwerke.

Beispiele: In Bäumen liegt die Wurzel in Ebene 0, ihre Kinder in Ebene 1 usw. In einem Graphen, dessen Startknoten S gewählt ist, entsprechen Knoten mit L(v)=k der k-Schicht des BFS-Laufs. In neuronalen Netzwerken entsprechen die Ebenen den Schichten, in denen jeweils eine Gruppe von Neuronen liegt, auch wenn der Terminus dort gewöhnlich Schicht heißt.

Alternativbezeichnungen umfassen Level, Layer oder Schicht; der Gebrauch hängt stark vom Kontext ab. See also: Graph, BFS, Hierarchischer Graphlayout, Layered Network, Neural Network.