Grundbegriffe der Graphentheorie 2
Inhaltsverzeichnis |
Maik Geier, Anna Bremensztul
Die Wiederholung
Die Graphentheorie ist ein Teilgebiet der Mathematik, das die Eigenschaften von Graphen und ihre Beziehungen zueinander untersucht.
Ein Graph besteht aus einer Menge von Punkten (Knoten,Ecken) zwischen denen Linien(Kanten, Bögen) verlaufen.
Bipartite Graphen
(2-Teiliger Graph)
Ein bipartiter oder paarer Graph ist ein mathematisches Modell für Beziehungen zwischen den Elementen zweier Mengen. Es eignet sich sehr gut zur Untersuchung von Zuordnungsproblemen. Des Weiteren lassen sich für bipartite Graphen viele Grapheneigenschaften mit deutlich weniger Aufwand berechnen als dies im allgemeinen Fall möglich ist.
Definitionen
Ein einfacher Graph G=(V,E) (V Menge der Knoten, E Menge der Kanten) heißt bipartit oder paar, falls sich seine Knoten in zwei disjunkte Teilmengen A und B aufteilen lassen, sodass zwischen den Knoten innerhalb beider Teilmengen keine Kanten verlaufen. Das heißt für eine Kante \{v,w\} \in E gilt entweder v \in A und w \in B oder v \in B und w \in A. Die Menge \{A,B\} bezeichnet man dann als Bipartition des Graphen G und die Mengen A,B als Partitionsklassen. Vereinfacht dargestellt, ist ein bipartiter Graph ein Graph, in dem zwei Gruppen von Knoten existieren, innerhalb derer keine Knoten miteinander verbunden sind.
Der Graph G heißt vollständig bipartit, falls eine Bipartition \{A,B\} existiert, sodass jeder Knoten aus A mit jedem Knoten aus B verbunden ist. Einen solchen Graphen bezeichnet man auch als K_{m,n}, wobei m und n jeweils die Anzahl der Knoten von A und B sind. Ein vollständig bipartiter Graph, bei dem m=1 oder n=1 ist, heißt Sterngraph.
Beispiel 1
In einem Dorf gibt es drei Häuser und drei Brunnen. Jedes der Häuser soll nun mit jedemder Brunnen durch einenWeg verbundenwerden. Modelliertman dieses Problem mithilfe eines Graphen.
Dieser Graph kommt auch als sogenannter GEW-Graph vor. Dieser Name basiert auf einer äquivalenten Realisierung des Problems mit drei mit drei Häusern und Werken für Gas, Elektrizität und Wasser.
Die Menge der 6 Knoten lässt sich in 2 Teilmengen einteilen: die Häuser und die Brunnen. Dazwischen werden Kanten gezeichnet, aber innerhalb der Teilmengen finden sich keine Kanten: Kein Haus soll etwa mit einem anderen verbundenwerden.