Kante (Graphentheorie)

Verbindung von Knoten durch Graphen
Dies ist eine alte Version dieser Seite, zuletzt bearbeitet am 17. August 2005 um 11:00 Uhr durch Stefan Birkner (Diskussion | Beiträge) (Kantenarten und ihre Notation: gekürzt). Sie kann sich erheblich von der aktuellen Version unterscheiden.

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.

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
 
Darstellung
eine einfache Linie zwischen den Knoten a und b

Datei: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. Sie besitzt also im Gegensatz zu einer ungerichteten Kante eine Orientierung.
Notation
 
Darstellung
ein Pfeil vom Knoten a zum Knoten b

Datei: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.



Weitere Informationen findet man im Artikel Typen von Graphen in der Graphentheorie.