Bipartiter Graph

Du willst mehr über verschiedene Eigenschaften von Graphen wissen? Wir erklären dir hier alles rund um bipartite, vollständige Graphen und Digraphen.

Gerichtete und ungerichtete Graphen, Kantengewicht und Knotengrad sind für dich keine Fremdwörter mehr? Perfekt! Du kennst also bereits einige Grundbegriffe der Graphentheorie . Dann wird es jetzt Zeit verschiedene Typen von Graphen näher zu betrachten. Ein Begriff der Graphentheorie sind bipartite Graphen.

Inhaltsübersicht

Bipartiter Graph
im Text
Vollständiger Graph
im Text
Digraph
im Text

Bipartiter Graph

Legen wir direkt los!

Ein Graph G wird genau dann als bipartit oder auch paar bezeichnet, wenn sich seine Knoten in zwei disjunkte Teilmengen A und B aufteilen lassen. Zwischen den Knoten innerhalb einer Teilmenge dürfen dabei keine Kanten bestehen.

Definition von bipartiten Graphen anhand eines Beispiels

Du kannst ganz einfach überprüfen ob dein Graph bipartit ist, indem du folgenden Grundsatz beachtest: Ein Graph ist bipartit, wenn er einen Kreis mit einer geraden Anzahl an Kanten enthält. In unserem Beispiel findest du genau einen Kreis. Dieser besteht aus einer geraden Anzahl an Kanten. Somit ist unser Graph bipartit.

Die Mengen A und B werden als Partitionsklassen bezeichnet, die Menge {A, B} als Bipartition des Graphen G.

Von einem vollständig bipartiten Graphen spricht man, wenn die Anzahl der Kanten maximal ist. Sprich jeder Knoten aus A muss mit jedem Knoten aus B verbunden sein. Unser Beispiel ist also nicht vollständig bipartit. Es fehlt die Kante von 4 nach 5. Fügen wir uns diese doch einfach einmal ein.

Formale Schreibweise eines vollständig bipartiten Graphen

Schon haben wir einen vollständig bipartiten Graphen der auch mit K_n,m bezeichnet wird.

Bipartiter Graph: maximale Anzahl an Kanten — Vollständig bipartiter Graph

Dabei sind m und n die Anzahl der Knoten von Menge A bzw. von Menge B. Menge A besteht bei uns aus 3, Menge B aus 2 Knoten. Sprich hier haben wir den vollständig bipartiten Graphen K_3,2_.

Sterngraphen

Von einem Sterngraphen spricht man, wenn entweder die Anzahl der Knoten der Menge A oder die Anzahl der Knoten der Menge B gleich 1 sind. Wenn also m = 1 oder n = 1. Der vollständige bipartite Graph K_1,6 wäre somit ein Sterngraph.

Sterngraphen mit n Kanten werden auch mit S_n bzw. K_{1, n} bezeichnet.

Eigenschaften bipartiter Graphen

Bipartite Graphen haben verschiedene Eigenschaften:

Ein Graph mit mindestens zwei Ecken ist bipartit, wenn er keinen Kreis mit ungerader Anzahl an Kanten enthält.
Ein vollständiger Graph hat genau m + n Ecken und m*n Kanten.
Die Mengen A und B eines bipartiten Graphen sind sogenannte stabile Mengen. Das sind Teilmengen eines Graphen die nicht adjazent zueinander sind.
Jeder bipartite Graph hat ein maximales oder auch perfektes Matching.
Die Paarungszahl ist gleich der Knotenüberdeckungszahl.
Ein Graph ist bipartit wenn er keinen Kreis von ungerader Länge
Ob ein Graph bipartit ist lässt sich durch einen einfachen Algorithmus, der auf Teifensuche basiert, bestimmen. Ebenso lässt sich die gültige Partition 2-Färbung ermitteln.
Alle 2-färbbaren Graphen sind bipartit und jeder bipartite Graph ist 2-knotenfärbbar. Das heißt, dass jeder Partitionsklassen eine Farbe zugewiesen wird.

Vollständiger Graph

Weiter geht es mit dem vollständigen Graph. In einem vollständigen Graph K_n ist jeder Knoten n mit jedem anderen Knoten durch eine Kante verbunden.

Eigenschaften vollständiger Graphen

Die Anzahl der Kanten entspricht der Dreieckszahl:

$\triangle_{n-1} =\binom{n}{2}=\frac{n(n-1)}{2}$

Klingt kompliziert? Ist es aber gar nicht! Schauen wir uns das ganze an einem Beispiel an:

Dreieckszahl berechnen — Vollständiger Graph und Berechnung der Dreieckszahl

Wir haben einen ungerichteten, vollständigen Graphen mit den vier Knoten A, B, C und D. Jeder Knoten ist mit jedem der anderen Knoten verbunden.

Setzen wir nun die Anzahl der Knoten in unsere Formel ein erhalten wir:

$\triangle_{4-1} =\binom{4}{2}=\frac{4(4-1)}{2} = 6$

Also eigentlich ganz einfach, oder?

Formale Schreibweise für vollständige Graphen

Formal scheibt man für vollständige Graphen:

K_n := G( E, K) .

E bezeichnet die Knoten, K die Kanten.

Die Anzahl der Kanten berechnet man wie oben beschrieben über die Dreieckszahl:

$K = \binom{E}{2}$

Digraph

Dann können wir ja direkt weiter machen und uns Digraphen anschauen. Als Digraph wird ein schlichter, gerichteter Graph mit endlicher Knotenmenge bezeichnet.

Schlichter Graph? Sagt dir nichts? Kein Problem! Ein schlichter Graph hat keine parallelen Pfeile und keine Schlingen.

Dieser Graph ist somit kein Digraph.

Entfernst du jedoch den parallelen Pfeil von A nach B und die Schlinge zu Knoten D erhältst du einen Digraphen.

Sehr gut, jetzt weist du eine ganze Menge über bipartite, vollständige und Digraphen! Damit sollte es gar kein Problem für dich sein noch tiefer in die Graphentheorie einzutauchen.

Operations Research

Optimierungsverfahren

Operations Research

Graphentheorie

Bipartiter Graph

Bipartiter Graph

Definition von bipartiten Graphen anhand eines Beispiels