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.
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.
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.
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.
Bipartite Graphen haben verschiedene Eigenschaften:
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?
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:
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.
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.