Kante (Graphentheorie)

Graph mit verschiedenen Arten von Kanten (rot)

Eine Kante ist in der Graphentheorie ein Teil eines Graphen, der zwei Knoten (vernetzte Punkte) miteinander verbindet. Die Art der Kanten (gerichtet oder ungerichtet) ist ein wichtiges Merkmal zur Klassifizierung von Graphen.

Kantenarten und ihre Notation

Ungerichtete Kante

Definition 

Eine ungerichtete Kante e verbindet zwei Knoten a und b, so dass man von jedem der beiden Knoten zum jeweils anderen gelangen kann. Die ungerichtete Kante besitzt also keine Orientierung.

Notation 

$e = \lbrace a, b \rbrace$

Gerichtete Kante

Definition 

Eine gerichtete Kante $e$ verbindet zwei Knoten $a$ und $b$, so dass man nur von $a$ nach $b$, aber nicht von $b$ nach $a$ gelangt. Sie besitzt also im Gegensatz zu einer ungerichteten Kante eine Orientierung.

Der Knoten $a$ wird Startknoten, der Knoten $b$ Endknoten der Kante genannt. Eine gerichtete Kante wird auch Bogen oder Pfeil genannt.

Notation 

$e = \left( a, b \right)$

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

Schleife 

Eine Schleife verbindet einen Knoten mit sich selbst.

Mehrfachkante 

Verlaufen in einem Multigraphen zwischen zwei Knoten mehrere gleichartige Kanten, so spricht man von einer Mehrfachkante (oder Multikante). Die einzelnen Kanten werden als parallele Kanten bezeichnet.

Mehrfachschleife

Eine gerichtete Mehrfachkante in einem Multigraphen, die zugleich Schleife ist, nennt man auch Mehrfachschleife.

Verallgemeinerung: Hyperkante

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