Knoten (Graphentheorie)

Ein Knoten o​der Ecke[1] i​st ein Begriff a​us der Graphentheorie.

Definition

Ein Knoten oder eine Ecke ist ein Element der Knotenmenge eines Graphen. Ist der Graph, wird seine Knotenmenge für gewöhnlich mit (englisch vertex) bezeichnet. Graphen bestehen neben der Knotenmenge noch aus einer dazugehörigen Kantenmenge (englisch edge), die beschreibt, wie die einzelnen Knoten des Graphen durch Kanten verbunden sind.[2]

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

Einzelnachweise
  1. Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 2. Auflage. Vieweg-Teubner, 2009, ISBN 978-3-8348-0629-1, S. 7.
  2. Bela Bollobas: Modern Graph Theory. 1st ed. 1998. Corr. 2nd printing 2002. Springer-Verlag, 2013, ISBN 978-0-387-98488-9, S. 1.
  3. Celina M. H. Figueiredo: Total Colouring. In: Lowell W. Beineke, Martin Charles Golumbic, Robin J. Wilson (Hrsg.): Topics in Algorithmic Graph Theory. 1. Auflage. Cambridge University Press, 2021, ISBN 1-108-49260-6.
  4. Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 2. Auflage. Vieweg-Teubner, 2009, ISBN 978-3-8348-0629-1, S. 61.
  5. Martin Aigner: Diskrete Mathematik. 6., korrigierte Auflage. Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8, S. 109.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.