Kante (Graphentheorie)

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

Inhaltsverzeichnis

1 Kantenarten und ihre Notation

1.1 ungerichtete Kante
1.2 gerichtete Kante

2 Besondere Kanten

3 Verallgemeinerung: Hyperkante

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.
Notation: $e = {a, b}$
Darstellung: eine einfache Linie zwischen den Knoten a und b

Bild:K2_(Graph).png

gerichtete Kante

Definition: Eine gerichtete Kante e verbindet zwei Knoten a und b, so dass man von nur von a nach b, aber nicht von b nach a gelangt.
Notation: $e = \left( a, b \right)$
Darstellung: ein Pfeil vom Knoten a zum Knoten b

Bild:Gerichtete_Kante.png

Besondere Kanten

Schleife: Eine Schleife verbindet eine Knoten mit sich selbst.
Mehrfachkante: Verlaufen in einem Multigraphen zwischen zwei Knoten mehrere gleichartige Kanten, so spricht man von einer Mehrfachkante.

Verallgemeinerung: Hyperkante

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

Kategorie:Graphentheorie