Graphentheorie

Die Graphentheorie bildet die Grundlage für viele Matchingprobleme, wie zum Beispiel das sehr bekannte Heiratsproblem.

Mit ihrer Hilfe lassen sich die zu Grunde liegenden Probleme und deren Beziehungen graphisch darstellen. Nachdem Lexikon der Mathematik (https://www.spektrum.de/lexikon/mathematik/graphentheorie/3591) definiert die Graphentheorie einen Graphen G, als das Paar aus den Mengen der Knoten V und der Kanten E, die der Graph enthält :

G = (V, E)

Dabei wird eine Kante durch das Paar von zwei Knoten, die sie verbindet, definiert:

E = (v1, v2), für alle v_1,v_2 in der Menge V

Graphisch wird ein Knoten meist als Punkt oder Kreis und eine Kante, als Linie, die zwei Knoten verbindet, repräsentiert.
Eine Kante besitzt zusätzlich noch folgende Eigenschaften:

• gerichtet/ungerichtet: Ist eine Kante E=(v_1,v_2) gerichtet besitzt sie einen Startknoten v1 und einen Endknoten v2
• gewichtet/ungewichtet: Ist eine Kante gewichtet ist ihr ein Kantengewicht zugeordnet. Dadurch lässt sich unter anderem die Stärke einer Verbindung darstellen

Die Orientierung einer Kante wird graphisch als Pfeilspitze dargestellt und das Kantengewicht wird an die Kante geschrieben.