Ein Graph wird dann als bipartit bezeichnet, wenn die enthaltenen Knoten in zwei Teilmengen aufteilbar sind, deren Knoten untereinander keine verbindenden Kanten aufweisen.
Du lernst in diesem Abschnitt was man unter bipartiten Graphen versteht, warum sie wichtig sind und welche weiteren Typen von Graphen es gibt.
Synonym: paarer Graph
Inhalt dieser Lektion
Warum sind bipartite Graphen wichtig?
Mit Hilfe von bipartiten Graphen lassen sich die Beziehungen der Elemente zweier Teilmengen A und B zueinander beschreiben. Mit Hilfe bipartiter Graphen können vor allem Zuordnungsprobleme bestens untersucht werden. Außerdem ist die Berechnung vieler Eigenschaften bei bipartiten Graphen mit einem geringeren Aufwand verbunden.
Was versteht man unter bipartiten Graphen?
Bipartite Graphen haben die Eigenschaft, dass sich ihre Knoten in zwei disjunkte Teilmengen (A und B) unterteilen lassen. Das bedeutet, dass unter den Knoten einer jeweiligen Teilmenge keine Kanten existieren, die die Knoten innerhalb einer Teilmenge miteinander verbinden.
Was versteht man unter bipartiten Graphen?
Bipartite Graphen haben die Eigenschaft, dass sich ihre Knoten in zwei disjunkte Teilmengen (A und B) unterteilen lassen. Das bedeutet, dass unter den Knoten einer jeweiligen Teilmenge keine Kanten existieren, die die Knoten innerhalb einer Teilmenge miteinander verbinden.
Die Teilmengen A und B der Elemente des Graphen heißen Partitionsklassen. Die Menge {A,B} wird als Bipartition des Graphen G bezeichnet.
Ist die Anzahl der Kanten im Graphen maximal, ist also jeder Knoten aus der Teilmenge A mit jedem Knoten B verbunden, so spricht man von einem vollständig bipartitem Graph. Dieser wird mit Kn,m bezeichnet. m und n bezeichnen dabei die jeweilige Anzahl der Knoten aus den Mengen A und B.
Eigenschaften bipartiter Graphen
Einen bipartiten Graph erkennt man anhand folgender Eigenschaften:
- Bei den Teilmengen A und B handelt es sich um stabile Mengen. Sie sind nicht adjazent zueinander.
- Bipartite Graphen haben ein maximales bzw. perfektes Matching.
- 2-färbbare Graphen sind bipartit, d.h. den jeweiligen Partitionsklassen können eindeutige Farben zugewiesen werden.
- Die Knotenüberdeckungszahl bipartiter Graphen ist gleich der Paarungszahl.
Weitere Typen von Graphen
Neben den bipartiten Graphen gibt es auch noch andere Typbezeichnungen für Graphen, die sich nach den jeweiligen Eigenschaften richten.
Hierzu gehören:
- Sterngraphen
- Vollständige Graphen
- Digraphen
Sterngraphen
Als Sterngraph bezeichnet man einen Graphen, wenn eine der Teilmengen gleich 1 ist. Sterngraphen, die über n Kanten verfügen werden mit Sn oder auch K1,n bezeichnet.
Ein Sterngraph mit der Bezeichnung K1,4 könnte also folgendermaßen aussehen:
Vollständige Graphen
Vollständige Graphen haben die Eigenschaft, dass jeder Knoten n mit jedem anderen Knoten durch eine Kante verbunden ist.
Die Anzahl der Kanten in einem vollständigen Graph kann mit Hilfe der Dreieckszahl berechnet werden:
![\[ \Delta_{n-1} = \frac{n*(n-1)}{2} \]](https://www.bwl-lexikon.de/app/ql-cache/quicklatex.com-c36fc91d9a4324ca03c21d81ea383185_l3.png "Rendered by QuickLaTeX.com")
Eingesetzt in die Formel bedeutet das:
![\[ \Delta_{5-1} = \frac{5*(5-1)}{2} = 10 \]](https://www.bwl-lexikon.de/app/ql-cache/quicklatex.com-d7f9ced1b8e5a11639e440f12900e178_l3.png "Rendered by QuickLaTeX.com")
In unserem vollständigen Graph K5 existieren also 10 Kanten.
Digraphen
Ein einfacher gerichteter Graph mit einer endlichen Menge an Knoten wird als Digraph bezeichnet. Er zeichnet sich dadurch aus, dass keine parallelen Pfeile und keine Schlingen existieren.
