Operations Research

Bipartiter Graph

Inhaltsübersicht

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.

Bipartiter Graph

Legen wir direkt los!

Bipartiter Graph
Bipartiter oder paarer Graph

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.

Partitionsklassen
Bipartition des Graphen G

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 Kn,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 K3,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 K1,6 wäre somit ein Sterngraph.

Sterngraphen mit n Kanten werden auch mit Sn bzw. K1, 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 Kn 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.

Digraph
Digraph: Schlicht und gerichtet

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.

 


Andere Nutzer halten diese Inhalte aus dem Bereich „Operations Research“ für besonders klausurrelevant

Hallo, leider nutzt du einen AdBlocker.

Auf Studyflix bieten wir dir kostenlos hochwertige Bildung an. Dies können wir nur durch die Unterstützung unserer Werbepartner tun.

Schalte bitte deinen Adblocker für Studyflix aus oder füge uns zu deinen Ausnahmen hinzu. Das tut dir nicht weh und hilft uns weiter.

Danke!
Dein Studyflix-Team

Wenn du nicht weißt, wie du deinen Adblocker deaktivierst oder Studyflix zu den Ausnahmen hinzufügst, findest du hier eine kurze Anleitung. Bitte lade anschließend die Seite neu.