Es werden die wichtigesten Grundbegriffe erläutert, die in der Graphentheorie häufig eine Anwendung finden

 

Grundlagen

Ein Graph $ G $ besteht aus einer Menge von Ecken und Kanten, die jeweils als $ E $ und $ V $ beschrieben werden. Der Graph ist paar und wird als $ G = (V, E) $ definiert. Dabei ist $ E $ eine Menge von zweielementigen Teilmengen von $ V $. Ecken die mit einer Kante verbunden sind werden als Nachbarn bezeichnet.

Nachbarn

Mathematisch können die Mengen aller Nachbarn einer Ecke $ v $ durch $ N(v) $ beschrieben werden.

 

Grad

Der Grad gibt $ d(v) $ einer Ecke ist mit $ d(v) = |N(v)| $ beschrieben und beschreibt die Anzahl der Nachbarn.

 In jedem Graph gilt:

\[ \sum _ { v \in V } d ( v ) = 2 \cdot | E | \]

In jedem Graph ist die Anzahl der Ecken ungeraden Grades gerade.

 

Isoliert

Hat eine Ecke den Grad null beziehungsweise besitzt keine Nachbarn wird sie als isoliert bezeichnet.

Vollständige Graphen

Ist jede zweielementige Teilmenge von V eine Kante, so nennt man $ G = (V, E) $ einen vollständigen Graphen \cite{Matching:Graphentheorie}.

 

Weg

Wird eine Folge von Ecken bezeichnet, die mit Kanten verbunden sind. Ein Pfad ist ein Weg, indem keine Ecken doppelt vorkommen.

 

Zyklus

Ein Zyklus ist ein Weg der bei der als Start- und Eckpunkt die selbe Ecke besitzt.

 

Kreis

Ist ein Zyklus bei dem alle Ecken aus v1 und vn verschieden sind

 


Quellen:

[1] Logo von https://pixabay.com/de/klassenzimmer-mathematik-tafel-1209820/

Suche

Kategorien

Wir nutzen Cookies auf unserer Website. Einige von ihnen sind essenziell für den Betrieb der Seite, während andere uns helfen, diese Website und die Nutzererfahrung zu verbessern (Tracking Cookies). Sie können selbst entscheiden, ob Sie die Cookies zulassen möchten. Bitte beachten Sie, dass bei einer Ablehnung womöglich nicht mehr alle Funktionalitäten der Seite zur Verfügung stehen.