Kante (Graphentheorie)

Kante (Graphentheorie)

Eine Kante (manchmal auch Bogen genannt) 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.

Inhaltsverzeichnis

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 = {a,b}

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.
Notation 
e =	\left( a, b \right)

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.

Verallgemeinerung: Hyperkante

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


Wikimedia Foundation.

Игры ⚽ Поможем решить контрольную работу

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Kante — (im 17. Jahrh. in der Bedeutung „Rand, Ecke“ aus dem Niederdt., von gallisch latinisiert canthus „eiserner Radreifen, Radfelge“) steht für: eine Strecke, welche die Ecken eines geometrischen Körpers beziehungsweise eines Polygons verbindet. in… …   Deutsch Wikipedia

  • Abstand (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Adjazenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Benachbart (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Gerichtete Kante — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Inzidenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Schlinge (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Tiefe (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Ungerichtete Kante — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

  • Valenz (Graphentheorie) — Dieses Stichwortverzeichnis enthält kurze Definitionen und Erklärungen zu den wichtigsten graphentheoretischen Begriffen. A Abstand Siehe: Distanz. Achromatische Zahl Die achromatische Zahl ψ(G) eines Graphen G ist die größte Zahl k, für die G… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”