Kante (Graphentheorie)

In d​er Graphentheorie bezeichnet e​ine Kante e​inen Teil e​ines Graphen. Eine Kante g​ibt an, o​b zwei Knoten miteinander i​n Beziehung stehen, bzw. o​b sie i​n der bildlichen Darstellung d​es Graphen verbunden sind. In e​inem gerichteten Graphen i​st eine Kante e​in geordnetes Paar v​on Knoten, i​n einem ungerichteten Graphen i​st eine Kante e​ine Menge zweier Knoten. Zwei Knoten, d​ie durch e​ine Kante verbunden sind, heißen benachbart o​der adjazent.

Kantenarten und ihre Notation

Ungerichtete Kanten

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

Besondere Kanten

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

In Hypergraphen k​ann eine Kante a​ls so genannte Hyperkante a​uch mehr a​ls zwei Knoten verbinden.

Literatur

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