Lösung für ein Mengen-Problem < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:49 Di 20.09.2005 | | Autor: | DrJohn |
Im Zuge anderer Überlegungen bin ich auf folgendes Problem gestoßen:
Gegeben: eine endliche, nicht-leere Menge [mm] X [/mm] und verschiedene, nicht-leere Teilmengen [mm] X_i, \emptyset \subset X_i \subseteq X, 1 \leq i \leq n [/mm]. "Verschieden" meint [mm] X_i = X_j \Longrightarrow i = j[/mm].
Gesucht: "Repräsentanten" [mm] x_i \in X_i, 1 \leq i \leq n [/mm], die paarweise verschieden sind, formal muss also gelten, dass [mm] card(\{ x_1, \ldots, x_n\}) = n [/mm] ist, wobei [mm] card(M) [/mm] die Anzahl der Elemente der Menge [mm] M [/mm] bezeichne.
Beispiel: Sei [mm] X = \{1,2,3\} [/mm], [mm] X_1 = \{1,3\} [/mm], [mm] X_2 = \{2,3\} [/mm], [mm] X_3 = \{1,2\} [/mm]. Eine mögliche Lösung ist [mm] x_1 = 1, x_2=3, x_3 = 2 [/mm], unter Hinzunahme von [mm] X_4 = \{1\} [/mm] ist keine Lösung mehr möglich.
Dieses Problem ist in meinen Augen so elementar, dass es unter irgendeinem Namen irgendwo mal aufgetaucht sein muss. Deshalb bin ich schon für Literaturhinweise oder einen Namen für dieses Problem sehr dankbar. Vielleicht ist es ja mit einem Problem der Graphentheorie (o.ä.) verwandt...
Eigentlich interessiere ich mich nicht für Lösungen des Problems, sondern eher für ein Kriterium, wann es eine Lösung gibt.
Über jegliche Hilfe würde ich mich freuen,
Johannes
P.S.: Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:25 Di 20.09.2005 | | Autor: | DrJohn |
Mittlerweile glaube ich, dass das "Problem" doch relativ speziell ist. Folgendes ist mir noch eingefallen:
Es ist ja klar, dass keine Lösung existieren kann, falls [mm] (\star) \; n > card(\bigcup_{i=1}^{n} X_i) [/mm].
Ansonsten gibt es aber nicht immer eine Lösung:
[mm] X = \{1,2,3,4\} [/mm], [mm] X_1 = \{1,2\} [/mm], [mm] X_2 = \{1\} [/mm], [mm] X_3 = \{2\}, X_4 = \{3,4\} [/mm] hat keine Lösung.
Wenn man sich aber die Mengen [mm] X_1 [/mm] bis [mm] X_3 [/mm] ansieht, stellt man fest, dass hier wieder mehr Mengen als Elemente vorhanden sind, die obige Bedingung [mm] (\star) [/mm] ist also sozusagen "lokal" erfüllt. Das kann man dann noch formal aufschreiben, da aber dieses Problem wahrscheinlich eh' niemanden sonst interessiert, betrachte ich die Frage als beantwortet, ihr müsst also nicht mehr posten...
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:03 Mi 21.09.2005 | | Autor: | Toellner |
Hallo DrJohn,
mich interessieren solche Art Fragen sehr! Leider habe ich i.A. keine Zeit. Wenn Du aber die 6 bis 12 Tage Geduld hast, mit der Du den Zeitrahmen für die Antwort zu Deinem Problem gepostet hast, werde ich Dir was dazu schreiben...
Grüße Richard
|
|
|
| |
|
Hallo DrJohn,
Ich habe das Problem absichtlich ohne Hinweis auf n = card(X) formuliert, weil es gar nichts mit der Endlichkeit von X zu tun hat. Du brauchst dann lediglich das Auswahlaxiom nicht.
Meiner Meinung nach siehts also so aus:
Eine Teilmenge [mm] Y=\{X_i / i \in J\}[/mm] der Potenzmenge P(X) heiße minimale Überdeckung von X, wenn [mm]X = \bigcup Y = \bigcup_{i \in J} X_i [/mm] und kein [mm] X_i [/mm] fehlen darf, also [mm]\bigcup_{i \in J-\{k\}} X_i \subset X[/mm] für alle [mm]k \in J[/mm].
Dabei sei J im Folgenden eine wohlgeordnete Indexmenge (d.h.: alle ihre Teilmengen haben ein Minimum, das gilt insbesondere für Teilmengen von [mm] \IN).
[/mm]
Minimalität kann man für einen gegebene Überdeckung Y von X rekursiv überprüfen bzw. aus einer Überdeckung eine minimale machen:
Ist eine Überdeckung [mm] Y_K=\{X_i / i \in K\}[/mm] minimal bezüglich [mm] \bigcup Y_K [/mm] mit K [mm] \subset [/mm] J, dann ist [mm] Y_L [/mm] mit [mm]L = K \cup \{l\}[/mm] minimal bezüglich [mm] \bigcup Y_L [/mm] , falls [mm] X_l [/mm] ein Element aus X- [mm] \bigcup Y_K [/mm] enthält. Ein solches [mm] X_l [/mm] muss es geben, falls nicht schon [mm] \bigcup Y_K [/mm] = X gilt: man nehme dazu das zum Index-Minimum l von J-K gehörige.
Jetzt ist klar, dass es zu einer minimalen Überdeckung Y von X eine Auswahlfunktion f gibt mit [mm]f(i) \in X_i[/mm] und [mm]f(i) = f(j) \Rightarrow i = j[/mm] für alle i,j [mm] \in [/mm] J:
man definiere f rekursiv:
Zu [mm] f_K [/mm] mit der Auswahleigenschaft auf [mm]\bigcup_{i \in K} X_i [/mm] gibt es [mm] f_{K \cup \{l\}}[/mm] mit [mm]f_{K \cup \{l\}} (l) \in X-\bigcup_{i \in K }X_i[/mm] falls nicht schon K = J ist.
Es ist klar, dass Y maximal card(X) Elemente haben kann.
D.h.: im endlichen Fall ist die Auswahlfunktion ein Element von
[mm] \produkt_{i=1}^{n}(X_{i}-\bigcup_{j < i} X_j)[/mm]
Hoffentlich hilfts dir weiter,
Gruß Richard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 17:37 Di 04.10.2005 | | Autor: | DrJohn |
Hallo Richard,
vielen Dank für Deine ausführliche Antwort, habe sie gerade eben entdeckt, da ich das Problem schon fast wieder vergessen hatte - die Querverbindung, weshalb ich darauf gestoßen war, hat sich als nicht nützlich herausgestellt. Werde mir die Lösung mal genau ansehn, schein mir so ganz allgemein geschrieben vielleicht doch ein interessantes Problem zu sein, in meinem Fall war es dann doch ziemlich uninteressant und trivial.
Grüße,
Johannes
|
|
|
|
