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.
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 Kn,m bezeichnet wird.
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.
Eigenschaften vollständiger Graphen
Die Anzahl der Kanten entspricht der Dreieckszahl:
Klingt kompliziert? Ist es aber gar nicht! Schauen wir uns das ganze an einem Beispiel an:
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:
Also eigentlich ganz einfach, oder?
Formale Schreibweise für vollständige Graphen
Formal scheibt man für vollständige Graphen:
.
E bezeichnet die Knoten, K die Kanten.
Die Anzahl der Kanten berechnet man wie oben beschrieben über die Dreieckszahl:
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.
