Hauptmenü öffnen

Kante (Graphentheorie)

Verbindung von Knoten durch Graphen

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.

Inhaltsverzeichnis

Kantenarten und ihre NotationBearbeiten

Ungerichtete KantenBearbeiten

Kanten in einem 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   als auch durch die Kante   verbunden sind.

Gerichtete KantenBearbeiten

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   wird der Knoten   Startknoten und der Knoten   Endknoten der Kante genannt. Eine gerichtete Kante wird auch „Bogen“ oder „Pfeil“ genannt. Zwei Kanten  ,   mit   und   heißen „gegenläufig“ oder „antiparallel“.

Besondere KantenBearbeiten

  • 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: HyperkanteBearbeiten

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

LiteraturBearbeiten

  • Dénes Kőnig: Theorie der endlichen und unendlichen Graphen. Akademische Verlagsgesellschaft, Leipzig 1936.