Kante (Graphentheorie)

aus Wikipedia, der freien Enzyklopädie
(Weitergeleitet von Gerichtete Kante)
Darstellung der Knoten, Kanten und Maschen

Kanten sind in der Graphentheorie derjenige Teil eines Graphen, der die Verbindung zwischen mindestens zwei Knoten herstellt.

Mathematische Definition

Ist Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle Q = (V,E)} ein ungerichteter Graph, so nennt man ein Element Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle [x,y] \in E} (mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x,y \in V} ) die Kante von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle G} ; Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x,y} heißen Endknoten.[1]

Eine Kante gibt an, ob zwei Knoten miteinander in Beziehung stehen, bzw. ob sie in der bildlichen Darstellung des Graphen verbunden sind. In einem gerichteten Graphen ist eine Kante ein geordnetes Paar von Knoten, in einem ungerichteten Graphen ist eine Kante eine Menge zweier Knoten. Zwei Knoten, die durch eine Kante verbunden sind, heißen benachbart oder adjazent.

Anwendung

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

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

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.

Kantenarten und ihre Notation

Ungerichtete Kanten

Kanten in einem ungerichteten Graphen bezeichnet man als „ungerichtete Kanten“. Eine ungerichtete Kante ist demnach eine Menge von zwei Knoten. Mitunter wird der Begriff auch auf gerichtete Graphen ausgeweitet, um auszudrücken, dass zwei Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle b} sowohl durch die Kante Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \left(a,b \right)} als auch durch die Kante Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \left(b,a\right)} verbunden sind.

Gerichtete Kanten

Kanten in einem gerichteten Graphen bezeichnet man als „gerichtete Kanten“. Sie besitzt also im Gegensatz zu einer ungerichteten Kante eine Orientierung. Für eine Kante Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e=\left( a,b \right)} wird der Knoten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle a} Startknoten und der Knoten Endknoten der Kante genannt. Eine gerichtete Kante wird auch „Bogen“ oder „Pfeil“ genannt. Zwei Kanten Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e_1} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e_2} mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e_1 = \left( a, b \right)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle e_2 = \left( b, a \right)} heißen „gegenläufig“ oder „antiparallel“.

Besondere Kanten

  • Schleife: Verbindet einen Knoten mit sich selbst.
  • Mehrfachkante/Multikante: Zwischen zwei Knoten verlaufen in einem Multigraphen mehrere gleichartige Kanten. Die einzelnen Kanten werden als „parallele Kanten“ bezeichnet.
  • Mehrfachschleife: Eine gerichtete Mehrfachkante in einem Multigraphen, die zugleich Schleife ist.

Verallgemeinerung: Hyperkante

In Hypergraphen kann eine Kante als so genannte Hyperkante auch mehr als zwei Knoten verbinden.

Literatur

  • Dénes Kőnig: Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft, Leipzig 1936.

Einzelnachweise

  1. ↑ Hans-Jochen Schneider, Lexikon Informatik und Datenverarbeitung, 1998, S. 448
  2. ↑ Manfred Broy, Informatik: Eine grundlegende Einführung, Band 1, 1998, S. 398
Abgerufen von „https://de.wikiup.org/index.php?title=Kante_(Graphentheorie)&oldid=226219907#Gerichtete_Kanten“