Bipartite Graphen
Wir betrachten nun Graphen, die sich durch eine Zerlegung ihrer Ecken in zwei Teile übersichtlich darstellen lassen:
Definition (bipartit)
Ein Graph G = (E, K) heißt bipartit, falls Teilmengen E1 und E2 von E existieren mit
(a) | E1 ∩ E2 = ∅, |
(b) | E1 ∪ E2 = E, |
(c) | Jede Kante von G verbindet eine Ecke in E1 mit einer Ecke in E2. |
Wir sagen dann auch, dass G bipartit durch die Zerlegung oder Bipartition E1, E2 der Eckenmenge E ist.
Anschaulich formuliert ist ein Graph G bipartit, wenn es eine Färbung seiner Eckenmenge E mit zwei Farben gibt derart, dass jede Kante zwei verschiedenfarbige Ecken miteinander verbindet. Ist ein Graph bipartit durch E1 und E2, so erhalten wir eine sehr übersichtliche Darstellung des Graphen als Ecken-Kanten-Diagramm, indem wir die Ecken aus E1 links (alternativ: unten) und die Ecken aus E2 rechts (alternativ: oben) linear anordnen.
Beispiel
Sei G = (E, K) mit E = { 1, …, 9 } und
K = { 12, 13, 17, 24, 29, 35, 39, 47, 48, 58, 67, 68, 89 }.
Dass G bipartit ist, ist aus dieser graphischen Darstellung nicht unmittelbar ersichtlich. Dies ändert sich, wenn wir die Zerlegung
E1 = { 1, 4, 5, 6, 9 }, E2 = { 2, 3, 7, 8 }
von E betrachten und den Graphen neu darstellen:
Es gibt keine Kanten innerhalb von E1 und keine Kanten innerhalb von E2. Der Graph ist bipartit durch E1 und E2.
Wir werden später einen Algorithmus kennenlernen, der feststellt, ob ein Graph bipartit ist und im Fall der Existenz eine Bipartition berechnet.
In Analogie zu den vollständigen Graphen definieren wir:
Definition (vollständig bipartit)
Ein Graph G = (E, K) heißt vollständig bipartit, falls es eine bipartite Zerlegung E1 und E2 von E gibt derart, dass jede Ecke von E1 mit jeder Ecke von E2 verbunden ist.
Die kanonischen Beispiele für diesen Graphentyp sind:
Definition (die Graphen Kn, m)
Seien n, m ≥ 1. Dann ist der kanonische vollständige bipartite Graph Kn, m definiert durch
| Ecken von Kn, m: | 1, …, n + m |
| Kanten von Kn, m: | ij mit 1 ≤ i ≤ n, n + 1 ≤ j ≤ n + m |
Jeder vollständig bipartite Graph ist nach Definition bipartit. Wird zu einem vollständig bipartiten Graphen eine neue Kante hinzugefügt, so ist der entstehende Graph nicht mehr bipartit. Ist G dagegen bipartit, aber nicht vollständig bipartit, so kann eine geeignete neue Kante zu G hinzugefügt werden, ohne eine Bipartition von G zu zerstören. In diesem Sinne sind vollständig bipartite Graphen maximal unter den bipartiten Graphen.
Für alle n, m ≥ 1 ist der Graph Kn, m vollständig bipartit mit der Zerlegung
E1 = { 1, …, n } und E2 = { n + 1, …, n + m }.
Standard-Visualisierungen von K3, 2 und K8, 4
Zwei weitere Darstellungen des K8, 4
Die Graphen Kn, m und Km, n unterscheiden sich nicht wesentlich voneinander. In der Standard-Visualisierung gehen sie durch Spiegelung an der Mittelachse und Neunummerierung der Ecken ineinander über. Wir untersuchen die strukturelle Gleichheit zweier Graphen im nächsten Kapitel in allgemeiner Form.
Der Begriff eines bipartiten Graphen lässt sich in natürlicher Weise verallgemeinern: Ein Graph G = (E, K) heißt tripartit, wenn es eine Zerlegung E1, E2, E3 seiner Eckenmenge E gibt derart, dass jede Kante Ecken in unterschiedlichen Teilen der Zerlegung verbindet. Allgemeiner sind k-partite Graphen für alle k ≥ 2 definiert, wobei k die Anzahl der Mengen der Zerlegung bezeichnet (sodass also bipartit = 2-partit, tripartit = 3-partit). Analog zu den Graphen Kn, m sind die vollständig tripartiten Graphen Kn, m, k definiert und allgemeiner die vollständig k-partiten Graphen Kn1, …, nk. Wir begnügen uns an dieser Stelle mit einem visuellen Eindruck:
Die vollständigen tripartiten Graphen K3, 3, 3 und K4, 3, 2