Knoten (Graphentheorie)

Als Knoten oder Ecke bezeichnet man in der Graphentheorie ein Element der Knotenmenge eines Graphen. Ist $G$ der Graph, wird seine Knotenmenge für gewöhnlich mit $V(G)$ (englisch vertex) bezeichnet. Graphen bestehen neben der Knotenmenge noch aus einer dazugehörigen Kantenmenge $E(G)$ (englisch edge), die beschreibt, wie die einzelnen Knoten des Graphen durch Kanten verbunden sind.

Spezielle Knoten

• Ein universaler Knoten ist ein Knoten, der zu allen anderen Knoten im Graphen adjazent ist.
• Ein simplizialer Knoten ist ein Knoten, dessen Nachbarn eine Clique, also einen vollständigen Teilgraphen des Ausgangsgraphen bilden.
• Ein isolierter Knoten ist in einem ungerichteten Graph ein Knoten ohne Nachbarn, also ein Knoten vom Grad null. In einem gerichteten Graph besitzt ein isolierter Knoten keine Vorgänger und Nachfolger und hat damit Eingangs- und Ausgangsgrad null.