Wann ist ein Graph nicht bipartit?

Ein Graph ist nicht bipartit, wenn er einen Kreis ungerader Länge enthält. Dann lässt sich keine Aufteilung der Knoten in zwei disjunkte Mengen so wählen, dass jede Kante nur zwischen den beiden Mengen verläuft. Zum Beispiel ist ein Dreieck (Kreis mit 3 Kanten) nicht bipartit.

Wie findet man bei einem bipartiten Graphen die beiden Partitionsklassen?

Die Partitionsklassen eines bipartiten Graphen findet man, indem man einen Startknoten in legt und danach alle Nachbarn in einordnet und so entlang der Kanten abwechselnd weitergeht (2-Färbung). Wenn ein Knoten dabei zwei verschiedene Zuordnungen erzwingen würde, passt die Aufteilung nicht. Zum Beispiel wird bei 1–2–3: und .

Was ist der Unterschied zwischen einem vollständigen Graphen und einem vollständig bipartiten Graphen?

Ein vollständiger Graph hat zwischen jedem Paar verschiedener Knoten eine Kante, also auch innerhalb jeder beliebigen Knotengruppe. Ein vollständig bipartiter Graph teilt die Knoten zuerst in zwei Mengen und hat dann alle Kanten nur zwischen diesen beiden Mengen, aber keine innerhalb einer Menge. Beispiel: verbindet alle 4 Knoten paarweise, nicht.

Was bedeutet „schlicht“ bei einem Digraphen?

Schlicht bedeutet bei einem Digraphen, dass der gerichtete Graph keine Schlingen (Pfeile von einem Knoten zu sich selbst) und keine parallelen Pfeile zwischen denselben zwei Knoten in derselben Richtung hat. Erlaubt sind normale gerichtete Kanten, und auch und dürfen gleichzeitig vorkommen.

Video

Bipartiter Graph

Wichtige Inhalte in diesem Video

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 Videozur Stelle im Video springen

(00:16)

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.

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.

Studyflix vernetzt: Hier ein Video aus einem anderen Bereich

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

im Videozur Stelle im Video springen

(01:51)

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

im Videozur Stelle im Video springen

(02:43)

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.

Bipartiter Graph — häufigste Fragen

(ausklappen)

Wann ist ein Graph nicht bipartit?

Ein Graph ist nicht bipartit, wenn er einen Kreis ungerader Länge enthält. Dann lässt sich keine Aufteilung der Knoten in zwei disjunkte Mengen so wählen, dass jede Kante nur zwischen den beiden Mengen verläuft. Zum Beispiel ist ein Dreieck (Kreis mit 3 Kanten) nicht bipartit.
Wie findet man bei einem bipartiten Graphen die beiden Partitionsklassen?

Die Partitionsklassen eines bipartiten Graphen findet man, indem man einen Startknoten in legt und danach alle Nachbarn in einordnet und so entlang der Kanten abwechselnd weitergeht (2-Färbung). Wenn ein Knoten dabei zwei verschiedene Zuordnungen erzwingen würde, passt die Aufteilung nicht. Zum Beispiel wird bei 1–2–3: $A = \{1,3\}$ und $B = \{2\}$ .
Was ist der Unterschied zwischen einem vollständigen Graphen und einem vollständig bipartiten Graphen?

Ein vollständiger Graph hat zwischen jedem Paar verschiedener Knoten eine Kante, also auch innerhalb jeder beliebigen Knotengruppe. Ein vollständig bipartiter Graph $K_{m,n}$ teilt die Knoten zuerst in zwei Mengen und hat dann alle Kanten nur zwischen diesen beiden Mengen, aber keine innerhalb einer Menge. Beispiel: verbindet alle 4 Knoten paarweise, $K_{3,2}$ nicht.
Was bedeutet „schlicht“ bei einem Digraphen?

Schlicht bedeutet bei einem Digraphen, dass der gerichtete Graph keine Schlingen (Pfeile von einem Knoten zu sich selbst) und keine parallelen Pfeile zwischen denselben zwei Knoten in derselben Richtung hat. Erlaubt sind normale gerichtete Kanten, und auch $A \to B$ und $B \to A$ dürfen gleichzeitig vorkommen.

Graphen verstehen

Ein bipartiter Graph ist ein wichtiger Typ aus der Graphentheorie und gehört zu den Grundideen von Graphen. Wer sich mit Graphen beschäftigt, vergleicht verschiedene Graph-Typen und achtet auf Knoten, Kanten und ihre Anordnung. So erkennst du, worin sich einfache, vollständige und gerichtete Graphen unterscheiden und wie ihre Struktur aufgebaut ist. Im Informatikbereich findest du passende Videos zu diesem und verwandten Themen.

zur Videoseite: Bipartiter Graph