Zweiteiliger Graph

Definition - Was bedeutet Bipartite Graph?

Ein zweigeteilter Graph ist ein Graph, in dem ein Satz von Graphscheitelpunkten in zwei unabhängige Sätze unterteilt werden kann und keine zwei Graphscheitelpunkte innerhalb desselben Satzes benachbart sind. Mit anderen Worten, zweigeteilte Graphen können als gleich zwei färbbaren Graphen betrachtet werden. Bipartite Graphen werden hauptsächlich zur Modellierung von Beziehungen verwendet, insbesondere zwischen zwei vollständigen Objektklassen.

Ein zweigeteilter Graph wird auch als Bigraph bezeichnet.

Technische.me erklärt Bipartite Graph

Ein zweigliedriger Graph hat zwei Sätze von Eckpunkten, zum Beispiel A und B, mit der Möglichkeit, dass die Verbindung beim Zeichnen einer Kante in der Lage sein sollte, eine Verbindung zwischen einem beliebigen Scheitelpunkt in A und einem beliebigen Scheitelpunkt in B herzustellen. Wenn der Graph keinen enthält ungerader Zyklus (die Anzahl der Eckpunkte im Diagramm ist ungerade), dann ist sein Spektrum symmetrisch. Die chromatische Zahl, dh die Mindestanzahl von Farben, die zum Färben der Scheitelpunkte ohne benachbarte Scheitelpunkte mit denselben Farben erforderlich sind, muss im Fall eines zweigeteilten Diagramms kleiner oder gleich zwei sein. Alle Arten von azyklischen Graphen (Graphen ohne Graphzyklen) sind Beispiele für zweigeteilte Graphen. Ein zyklischer Graph wird als zweiteilig betrachtet, wenn alle beteiligten Zyklen eine gerade Länge haben. Nach dem Linienfarbsatz von Koning sind alle zweigeteilten Graphen Graphen der Klasse 1.

Bipartite Graphen werden in der modernen Codierungstheorie häufig verwendet, abgesehen von der Modellierung von Beziehungen.