www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Englisch
  Status Grammatik
  Status Lektüre
  Status Korrekturlesen
  Status Übersetzung
  Status Sonstiges (Englisch)

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Uni-Sonstiges" - Lösung für ein Mengen-Problem
Lösung für ein Mengen-Problem < Sonstiges < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Lösung für ein Mengen-Problem: Frage
Status: (Frage) beantwortet Status 
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.

        
Bezug
Lösung für ein Mengen-Problem: Antwort
Status: (Mitteilung) Reaktion unnötig Status 
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...

Bezug
                
Bezug
Lösung für ein Mengen-Problem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
        
Bezug
Lösung für ein Mengen-Problem: Antwort
Status: (Antwort) fertig Status 
Datum: 15:36 Di 27.09.2005
Autor: Toellner

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

Bezug
                
Bezug
Lösung für ein Mengen-Problem: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Uni-Sonstiges"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.englischraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]