Studium, Ausbildung und Beruf

web uni-protokolle.de
 powered by
NachrichtenLexikonProtokolleBücherForenSamstag, 15. August 2020 

Bipartiter Graph


Dieser Artikel von Wikipedia ist u.U. veraltet. Die neue Version gibt es hier.

Inhaltsverzeichnis

Definition


K 3 3 : bipartiter Graph mit
3 Knoten pro Teilmenge

Ein Graph heißt in der Graphentheorie bipartit (auch paar ) falls sich seine Knoten in zwei disjunkte Teilmengen aufteilen lassen ( Bipartition ) so dass es zwischen den Knoten einer Teilmenge keine Kanten gibt.

Formal

Ein Graph <math>K_{m n}:=G(E K)</math> heißt bipartit falls <math>E=A+B</math> aus zwei disjunkten Teilmengen A und B besteht mit <math>|A|=m \ |B|=n</math> und alle Kanten <math>ab \in K</math> mit <math>a A \ b \in B</math> gilt.

Ein Graph <math>K_{m n}</math> heißt vollständig bipartit falls <math>|E|=m+n \ |K|=m \cdot n</math> <math>E := \{ab\ |\ \forall\ a \in b \in B\}</math> d.h. alle Kanten zwischen A und B sind vorhanden.

Folgerungen

Die Teilmengen A und B sind stabile Mengen und die Bipartition impliziert eine mögliche Färbung des Graphen. Umgekehrt sind alle 2-färbbaren bipartit.

Für bipartite Graphen lassen sich viele Grapheigenschaften effektiv berechnen die für allgemeine Graphen effizient bzw. nicht in polynomieller Zeit bestimmt können.

Mit einem einfachen Algorithmus der auf Tiefensuche basiert lässt sich in Linerarer Zeit ob ein Graph bipartit ist und eine Partition bzw. 2-Färbung ermitteln.

Eigenschaften


Siehe auch

k-partiter Graph Typen von Graphen in der Graphentheorie



Bücher zum Thema Bipartiter Graph

Dieser Artikel von Wikipedia unterliegt der GNU FDL.

ImpressumLesezeichen setzenSeite versendenSeite drucken

HTML-Code zum Verweis auf diese Seite:
<a href="http://www.uni-protokolle.de/Lexikon/Bipartiter_Graph.html">Bipartiter Graph </a>