Kante (Graphentheorie) - LinkFang.de





Kante (Graphentheorie)


In der Graphentheorie bezeichnet eine Kante einen Teil eines Graphen. 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.

Kantenarten und ihre Notation

Ungerichtete Kanten

Kanten in einen 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 a und b sowohl durch die Kante [math]\left(a,b \right)[/math] als auch durch die Kante [math]\left( b,a \right)[/math] 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 [math]e=\left( a,b \right)[/math] wird der Knoten [math]a[/math] Startknoten und der Knoten [math]b[/math] Endknoten der Kante genannt. Eine gerichtete Kante wird auch Bogen oder Pfeil genannt. Zwei Kanten [math]e_1[/math], [math]e_2[/math] mit [math]e_1 = \left( a, b \right)[/math] und [math]e_2 = \left( b, a \right)[/math] 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.


Kategorien: Grundbegriff (Graphentheorie)

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Kante (Graphentheorie) (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.