imported>Uwe Lück: Zerlegung → Partition (Mengenlehre) + Klärung des Zusammenhangs

2018-08-04T17:26:31Z

Zerlegung → Partition (Mengenlehre) + Klärung des Zusammenhangs

Neue Seite

Das '''Mengenzerlegungsproblem''' (oft mit ''set-partitioning-Problem'' notiert) ist ein [[Entscheidbar|Entscheidungsproblem]] der [[Kombinatorik]].

Es fragt, ob zu einer [[Menge (Mathematik)|Menge]] <math>U</math> und <math>n</math> ([[nichtleer]]en) [[Teilmenge]]n <math>S_j</math> von <math>U</math> und einer [[natürliche Zahl|natürlichen Zahl]] <math>k \le n</math> eine Vereinigung von <math>k</math> disjunkten Teilmengen <math>S_j</math> existiert, die der Menge <math>U</math> entspricht. (Für durch <math>1\leq j\leq n</math> indizierte <math>S_j</math> gibt es dann eine <math>k</math>-elementige Menge <math>K</math> von Zahlen <math>i</math> mit <math>1\leq i\leq n</math>, so dass <math>\{\,S_j\mid j\in K\,\}</math> eine [[Partition (Mengenlehre)|Zerlegung]] von <math>U</math> ist.)

Als Optimierungsproblem formuliert, wird eine Zerlegung mit möglichst kleiner Anzahl der Teilmengen <math>S_j</math> gesucht oder, falls den Teilmengen <math>S_j</math> Kosten <math>c_j</math> zugeordnet sind, eine Zerlegung mit geringsten Kosten.

==Siehe auch==

* [[Problem der exakten Überdeckung]]
* [[Mengenüberdeckungsproblem]]
* [[Mengenpackungsproblem]]

[[Kategorie:Komplexitätstheorie]]
[[Kategorie:Kombinatorische Optimierung]]

Mengenzerlegungsproblem - Versionsgeschichte

imported>Uwe Lück: Zerlegung → Partition (Mengenlehre) + Klärung des Zusammenhangs