Knotenmenge

Knotenmenge ist ein Begriff aus der Graphentheorie und bezeichnet die Menge aller Knoten (Vertices) eines Graphen. In der gebräuchlichen Notation wird ein Graph G oft als G = (V, E) geschrieben, wobei V die Knotenmenge und E die Kantenmenge angibt. Die Knotenmenge wird häufig mit V(G) bezeichnet oder einfach als V geschrieben. Sie kann endlich oder unendlich sein; die Kardinalität von V heißt Ordnung des Graphen und wird als |V| angegeben.

Die Knotenmenge ist eines der Grunddatenpaare eines Graphen. Die Kanten verbinden Paare von Knoten oder, im Fall gerichteter Graphen, orientierte Kanten zwischen Quell- und Zielknoten. Aus der Knotenmenge ergeben sich weitere Konzepte wie der Grad eines Knotens, beschrieben als die Anzahl der Kanten, die ihn berühren (bei gerichteten Graphen unterscheiden sich eingehender und ausgehender Grad).

Subgraphen und Induktion: Aus einer Teilmenge U der Knotenmenge V erhält man den induzierten Untergraphen G[U], dessen Knotenmenge U ist und der Kantenmenge diejenigen Kanten aus E enthält, deren Endpunkte vollständig in U liegen. Solche Konstruktionen dienen zur Analyse von Strukturen innerhalb des Graphen.

Anwendungen: In der Netzwerkanalyse repräsentiert die Knotenmenge die untersuchten Entitäten wie Personen, Router, Städte usw.; Kanten stehen für Beziehungen oder Verbindungen zwischen ihnen. Die Knotenmenge bildet damit die Grundstruktur, auf der weitere graphentheoretische oder algorithmische Operationen aufbauen.

Varianten: In gerichteten Graphen, mehrstufigen Graphen oder Hypergraphen bleibt das zentrale Konzept der Knotenmenge erhalten, wird aber entsprechend angepasst (z. B. separate Betrachtung von eingehenden/ausgehenden Kanten).