Disjunkte Mengen: Definition, Beispiele und Anwendungen in Mathematik und Informatik

In der Mengenlehre sind zwei Mengen disjunkt, wenn sie keine gemeinsamen Elemente haben (ihr Durchschnitt ist die leere Menge, ∅).

Beispiele

• {1, 2, 3} und {4, 5, 6} sind disjunkt.
• {a, b} und {b, c} sind nicht disjunkt (sie teilen das Element b).

Anwendungen

• Graphentheorie: Zusammenhangskomponenten bilden eine Partition der Vertexmenge in disjunkte Mengen.
• Datenstrukturen: Disjunkt-Set (Union-Find)-Struktur verfolgt Äquivalenzklassen für Kruskals Algorithmus, Zusammenhangskomponenten, Bildsegmentierung.
• Wahrscheinlichkeit: gegenseitig ausschließende Ereignisse entsprechen disjunkten Mengen.
• Geometrie: Nicht sich schneidende Linien, Kurven oder Regionen.

Das Konzept erstreckt sich auf Familien von Mengen: Eine Sammlung ist paarweise disjunkt, wenn jedes Paar disjunkt ist.