Kategorie

A B C D E
F G H I J
K L M N O
P Q R S T
U V W X Y
Z 0      

bipartiter graph

ba bb bc bd be bf bg bh bi bj bk bl bm
bn bo bp bq br bs bt bu bv bw bx by bz

Bipartiter Graph

Table of contents
1 Definition
 2 Folgerungen
3 Eigenschaften
4 Siehe auch

Definition


K3,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 innerhalb einer Teilmenge keine Kantenn gibt.

Formal

Ein Graph heißt bipartit, falls aus zwei disjunkten Teilmengen A und B besteht mit und für alle Kanten mit gilt.

Ein Graph heißt vollständig bipartit falls und , 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 2-Färbung des Graphen. Umgekehrt sind alle 2-färbbaren Graphen bipartit.

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

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

Eigenschaften

  • Die Paarungszahl entspricht der Knotenüberdeckungszahl.
  • Mit dem Algorithmus von Hopcroft und Karp lässt sich in O(?nm) eine größte Paarung finden und darüber auch die Stabilitätszahl bestimmen.
  • Der chromatische Index entspricht seinem Maximalgrad. Eine gültige Kantenfärbung lässt sich in O(nm) bestimmen.
  • Ein regulärer bipartiter Graph besitzt ein perfektes Matching.

Siehe auch

k-partiter Graph,Typen von Graphen in der Graphentheorie

Impressum

Datenschutzerklärung