Knoten (Graphentheorie)

Die Menge der Knoten (oder Ecken^[1]) ist in der Graphentheorie ein Bestandteil jedes Graphen. Sie wird ergänzt durch die Menge der Kanten, die Verbindungen zwischen den Knoten repräsentieren.

Mathematische Definition

Ist $G=(V,E)$ ein gerichteter oder ein ungerichteter Graph, so nennt man ein Element $x\in V$ einen Knoten von $G$ . Graphen bestehen neben der Knotenmenge $V(G)$ noch aus einer dazugehörigen Kantenmenge $E(G)$ (englisch edge), die beschreibt, wie die einzelnen Knoten des Graphen durch Kanten verbunden sind.^[2]

Anwendung

Die Graphentheorie kann auf alle Netzwerke angewandt werden. Die Knoten und Kanten haben in jedem Netzwerk spezifische Bezeichnungen.^[3]

Netzwerk	Knoten	Kanten
Straßennetze	Verkehrsknoten: Straßenkreuzung, Anschlussstelle	Verkehrswege: Autobahnen, Straßen, Straßenbrücken, Straßentunnel
Schienennetze	Bahnhöfe: Güterbahnhöfe, Personenbahnhöfe	Schienen, Weichen, Eisenbahnbrücken, Eisenbahntunnel
Wasserstraßennetze	Häfen: Binnenhäfen, Seehäfen	Gewässer: Flüsse, Kanäle, Meere
Mobilfunknetze	Funkstellen, Mobilfunkgeräte, Handy, Smartphones	Mobilfunkfrequenzen
Stromnetze	Einspeisung, Ausspeisung, Umspannwerke	Freileitungsmasten, Stromleitungen
Rechnernetze	Server, Switches, Rechner, Internet-Knoten	Endgeräte, Personal Computer, Wiedergabegeräte
Soziale Netzwerke^[4]	Personen, Tiere, Organisationen	Beziehungen, Interaktionen

Auch Verkehrsnetze wie Flugstraßennetze oder andere Funknetze wie das Amateurfunknetz oder der Seefunk sowie Infrastruktur-Netzwerke besitzen eine Netztopologie, die mit der Graphentheorie erklärt werden kann.

Im Transportwesen beispielsweise sind der Versandort, etwaige Umladeorte und der Empfangsort die Knoten und die diese Orte verbindenden Transportwege die Kanten.

Spezielle Knoten

Ein universaler Knoten ist ein Knoten, der zu allen anderen Knoten im Graphen adjazent ist.^[5]
Ein simplizialer Knoten ist ein Knoten, dessen Nachbarn eine Clique, also einen vollständigen Teilgraphen des Ausgangsgraphen bilden.^[6]
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.^[7]

Einzelnachweise

↑ Sven Oliver Krumke, Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 2. Auflage. Vieweg-Teubner, 2009, ISBN 978-3-8348-0629-1, S. 7.
↑ Bela Bollobas: Modern Graph Theory. 1st ed. 1998. Corr. 2nd printing 2002. Springer-Verlag, 2013, ISBN 978-0-387-98488-9, S. 1.
↑ Manfred Broy, Informatik: Eine grundlegende Einführung, Band 1, 1998, S. 398
↑ Eric D. Kolaczyk: Statistical Analysis of Network Data. doi:10.1007/978-0-387-88146-1 (springer.com [abgerufen am 7. Oktober 2024]).
↑ 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.
↑ Sven Oliver Krumke/Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 2. Auflage. Vieweg-Teubner, 2009, ISBN 978-3-8348-0629-1, S. 61.
↑ Martin Aigner: Diskrete Mathematik. 6., korrigierte Auflage. Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8, S. 109.

[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] Manfred Broy, Informatik: Eine grundlegende Einführung, Band 1, 1998, S. 398

[4] Eric D. Kolaczyk: Statistical Analysis of Network Data. doi:10.1007/978-0-387-88146-1 (springer.com [abgerufen am 7. Oktober 2024]).

[5] 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.

[6] Sven Oliver Krumke/Hartmut Noltemeier: Graphentheoretische Konzepte und Algorithmen. 2. Auflage. Vieweg-Teubner, 2009, ISBN 978-3-8348-0629-1, S. 61.

[7] Martin Aigner: Diskrete Mathematik. 6., korrigierte Auflage. Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8, S. 109.

[1]