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 Graphe 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 \left(a,b\right) als auch durch die Kante \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 e=\left(a,b\right) wird der Knoten a Startknoten und der Knoten b Endknoten der Kante genannt. Eine gerichtete Kante wird auch Bogen oder Pfeil genannt. Zwei Kanten e_{1}, e_{2} mit e_{1}=\left(a,b\right) und e_{2}=\left(b,a\right) heißen gegenläufig oder antiparallel.

Besondere Kanten

Verallgemeinerung: Hyperkante

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

Trenner
Basierend auf einem Artikel in: externer Link Wikipedia.de
Seitenende
Seite zurück
©  biancahoegel.de
Datum der letzten Änderung: Jena, den: 05.02. 2019