Beweis Matroid < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Es sei (S, [mm] I_{k}) [/mm] ein Mengensystem, wobei S eine endliche Menge und [mm] I_{k} [/mm] die Menge aller Teilmengen von S mit [mm] \le [/mm] k Elementen ist. Zeigen Sie, dass (S, [mm] I_{k}) [/mm] ein Matroid ist. |
Ich habe diese Frage auch in folgenden Foren auf anderen Internetseiten gestellt:
Hallo Zusammen,
ich hoffe die Lösung ist richtig, wär nett wenn ihr mir Feedback geben könntet :)
Vor.: Es sei (S, [mm] I_{k}) [/mm] ein Mengensystem, wobei S eine endliche Menge und [mm] I_{k} [/mm] die Menge aller Teilmengen von S mit [mm] \le [/mm] k Elementen ist.
Beh.: (S, [mm] I_{k}) [/mm] ist ein Matroid.
Bew.:
(z.Z. A,B [mm] \subseteq I_{k}\wedge|B|<|A|\Rightarrow (\exists [/mm] X [mm] \subseteq A\backslash [/mm] B): B [mm] \cup [/mm] X [mm] \subseteq I_{k})
[/mm]
Seien A,B [mm] \subseteq I_{k} [/mm] und |B|<|A|. Dann existiert eine Teilmenge X [mm] \subseteq [/mm] A, die nicht in B ist.
Da |B|<|A| und A,B [mm] \subseteq I_{k} [/mm] folgt [mm] |B|
Vielen Dank und Lieben Grüß!
PS: Ich hoffe das ist im Forum Graphentheorie richtig aufgehoben.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 05:06 Di 17.11.2015 | | Autor: | fred97 |
> Es sei (S, [mm]I_{k})[/mm] ein Mengensystem, wobei S eine endliche
> Menge und [mm]I_{k}[/mm] die Menge aller Teilmengen von S mit [mm]\le[/mm] k
> Elementen ist. Zeigen Sie, dass (S, [mm]I_{k})[/mm] ein Matroid
> ist.
> Ich habe diese Frage auch in folgenden Foren auf anderen
> Internetseiten gestellt:
>
>
> Hallo Zusammen,
>
> ich hoffe die Lösung ist richtig, wär nett wenn ihr mir
> Feedback geben könntet :)
Ich nehms vorweg: Du hast es ziemlich versaut.
>
>
> Vor.: Es sei (S, [mm]I_{k})[/mm] ein Mengensystem, wobei S eine
> endliche Menge und [mm]I_{k}[/mm] die Menge aller Teilmengen von S
> mit [mm]\le[/mm] k Elementen ist.
>
> Beh.: (S, [mm]I_{k})[/mm] ist ein Matroid.
>
> Bew.:
> (z.Z. A,B [mm]\subseteq I_{k}\wedge|B|<|A|\Rightarrow (\exists[/mm]
> X [mm]\subseteq A\backslash[/mm] B): B [mm]\cup[/mm] X [mm]\subseteq I_{k})[/mm]
1. Das lautet korrekt so:
A,B [mm]\in I_{k}\wedge|B|<|A|\Rightarrow (\exists[/mm] X [mm]\subseteq A\backslash[/mm] B): B [mm]\cup[/mm] X [mm]\in I_{k})[/mm]
[mm] I_k [/mm] ist eine Teilmenge der Potenzmenge von S !!!
2. Für ein Matroid sind noch weitere Eigenschaften zu zeigen:
(i) [mm] \emptyset \in I_k,
[/mm]
(ii) aus A [mm] \in I_k [/mm] und B [mm] \subseteq [/mm] A folgt B [mm] \in I_k.
[/mm]
>
> Seien A,B [mm]\subseteq I_{k}[/mm] und |B|<|A|. Dann existiert eine
> Teilmenge X [mm]\subseteq[/mm] A, die nicht in B ist.
Das ist richtig. Es wird aber mehr verlangt, nämlich $X [mm] \subseteq [/mm] A [mm] \setminus [/mm] B$. Kannst Du solch ein X angeben ?
>
> Da |B|<|A| und A,B [mm]\subseteq I_{k}[/mm] folgt [mm]|B|
Das ist völliger Quark ! Es sind A,B [mm] \in I_k. [/mm]
[mm] |B|
> (also
> [mm]B\not=I_{k}).[/mm] Also gilt [mm]B\cup[/mm] X [mm]\subseteq I_{k}.[/mm]
??? Schüttelkopf , Kopfschüttel ! Ich kann Dir nicht folgen, weil es nichts zum folgen gibt
FRED
>
> Vielen Dank und Lieben Grüß!
>
> PS: Ich hoffe das ist im Forum Graphentheorie richtig
> aufgehoben.
|
|
|
| |
|
> > Es sei (S, [mm]I_{k})[/mm] ein Mengensystem, wobei S eine endliche
> > Menge und [mm]I_{k}[/mm] die Menge aller Teilmengen von S mit [mm]\le[/mm] k
> > Elementen ist. Zeigen Sie, dass (S, [mm]I_{k})[/mm] ein Matroid
> > ist.
> > Ich habe diese Frage auch in folgenden Foren auf
> anderen
> > Internetseiten gestellt:
> >
> >
> > Hallo Zusammen,
> >
> > ich hoffe die Lösung ist richtig, wär nett wenn ihr mir
> > Feedback geben könntet :)
>
> Ich nehms vorweg: Du hast es ziemlich versaut.
Ich glaube ich habe auch noch nicht ganz verstanden was das ganze überhaupt soll :(
>
>
> >
> >
> > Vor.: Es sei (S, [mm]I_{k})[/mm] ein Mengensystem, wobei S eine
> > endliche Menge und [mm]I_{k}[/mm] die Menge aller Teilmengen von S
> > mit [mm]\le[/mm] k Elementen ist.
> >
> > Beh.: (S, [mm]I_{k})[/mm] ist ein Matroid.
> >
> > Bew.:
> > (z.Z. A,B [mm]\subseteq I_{k}\wedge|B|<|A|\Rightarrow (\exists[/mm]
> > X [mm]\subseteq A\backslash[/mm] B): B [mm]\cup[/mm] X [mm]\subseteq I_{k})[/mm]
>
> 1. Das lautet korrekt so:
>
> A,B [mm]\in I_{k}\wedge|B|<|A|\Rightarrow (\exists[/mm] X [mm]\subseteq A\backslash[/mm]
> B): B [mm]\cup[/mm] X [mm]\in I_{k})[/mm]
Oh ja da hast du recht, ich hatte gedacht A, B sind in der Ursprungsformel nur Elemente und keine Mengen, und wollte das irgendwie für Mengen umschreiben. Das mit Teilmenge und enthalten-sein verwirrt mich gerade total.
>
> [mm]I_k[/mm] ist eine Teilmenge der Potenzmenge von S !!!
>
> 2. Für ein Matroid sind noch weitere Eigenschaften zu
> zeigen:
>
> (i) [mm]\emptyset \in I_k,[/mm]
>
> (ii) aus A [mm]\in I_k[/mm] und B [mm]\subseteq[/mm] A folgt B [mm]\in I_k.[/mm]
>
>
> >
> > Seien A,B [mm]\subseteq I_{k}[/mm] und |B|<|A|. Dann existiert eine
> > Teilmenge X [mm]\subseteq[/mm] A, die nicht in B ist.
>
> Das ist richtig. Es wird aber mehr verlangt, nämlich [mm]X \subseteq A \setminus B[/mm].
> Kannst Du solch ein X angeben ?
>
>
> >
> > Da |B|<|A| und A,B [mm]\subseteq I_{k}[/mm] folgt [mm]|B|
>
> Das ist völliger Quark ! Es sind A,B [mm]\in I_k.[/mm]
>
> [mm]|B|
> [mm]I_k[/mm] eine Menge von Mengen.
>
>
>
>
> > (also
> > [mm]B\not=I_{k}).[/mm] Also gilt [mm]B\cup[/mm] X [mm]\subseteq I_{k}.[/mm]
>
> ??? Schüttelkopf , Kopfschüttel ! Ich kann Dir nicht
> folgen, weil es nichts zum folgen gibt
>
> FRED
> >
> > Vielen Dank und Lieben Grüß!
> >
> > PS: Ich hoffe das ist im Forum Graphentheorie richtig
> > aufgehoben.
>
Ich versuchs noch einmal xD
Vor.: Es sei (S, [mm]I_{k})[/mm] ein Mengensystem, wobei S eine endliche Menge und [mm]I_{k}[/mm] die Menge aller Teilmengen von S mit [mm]\le[/mm] k Elementen ist.
Beh.: (S, [mm]I_{k})[/mm] ist ein Matroid.
Bew. (z.Z:
(i) [mm]\emptyset \in I_k,[/mm] (warum muss das gezeigt werden?)
(ii) A [mm]\in I_k[/mm] [mm] \wedge [/mm] B [mm]\subseteq[/mm] A [mm] \Rightarrow [/mm] B [mm]\in I_k.[/mm]
(iii) A,B [mm]\in I_{k}\wedge|B|<|A|\Rightarrow (\exists[/mm] X [mm]\subseteq A\backslash[/mm] B): B [mm]\cup[/mm] X [mm]\in I_{k})[/mm])
(zu i) [mm] \emptyset [/mm] ist in [mm] I_k, [/mm] weil [mm] I_k [/mm] die Menge aller Teilmengen von S ist und [mm] \emptyset [/mm] Teilmenge jeder Menge ist.
(zu ii)Sei A [mm] \in I_k [/mm] und B [mm] \subseteq [/mm] A. A ist eine Menge von Teilmengen von S, und weil B eine Teilmenge davon ist, ist auch B [mm] \in [/mm] A.
(zu iii) Seien A, B [mm] \in I_k [/mm] und |B|<|A|. Dann gibt es also in A mindestens eine Teilmenge X, die nicht in B ist. Also
X [mm] \subseteq [/mm] (oder [mm] \in?) A\backslash [/mm] B.
Weil X [mm] \subseteq A\backslash [/mm] B und A [mm] \in I_k, [/mm] gilt auch X [mm] \in I_k. [/mm] Und da auch B [mm] \in I_k [/mm] ist, folgt B [mm] \cup [/mm] X [mm] \in I_k.
[/mm]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 07:48 Mi 18.11.2015 | | Autor: | fred97 |
> > > Es sei (S, [mm]I_{k})[/mm] ein Mengensystem, wobei S eine endliche
> > > Menge und [mm]I_{k}[/mm] die Menge aller Teilmengen von S mit [mm]\le[/mm] k
> > > Elementen ist. Zeigen Sie, dass (S, [mm]I_{k})[/mm] ein Matroid
> > > ist.
> > > Ich habe diese Frage auch in folgenden Foren auf
> > anderen
> > > Internetseiten gestellt:
> > >
> > >
> > > Hallo Zusammen,
> > >
> > > ich hoffe die Lösung ist richtig, wär nett wenn ihr mir
> > > Feedback geben könntet :)
> >
> > Ich nehms vorweg: Du hast es ziemlich versaut.
>
> Ich glaube ich habe auch noch nicht ganz verstanden was das
> ganze überhaupt soll :(
> >
> >
> > >
> > >
> > > Vor.: Es sei (S, [mm]I_{k})[/mm] ein Mengensystem, wobei S eine
> > > endliche Menge und [mm]I_{k}[/mm] die Menge aller Teilmengen von S
> > > mit [mm]\le[/mm] k Elementen ist.
> > >
> > > Beh.: (S, [mm]I_{k})[/mm] ist ein Matroid.
> > >
> > > Bew.:
> > > (z.Z. A,B [mm]\subseteq I_{k}\wedge|B|<|A|\Rightarrow (\exists[/mm]
> > > X [mm]\subseteq A\backslash[/mm] B): B [mm]\cup[/mm] X [mm]\subseteq I_{k})[/mm]
>
> >
> > 1. Das lautet korrekt so:
> >
> > A,B [mm]\in I_{k}\wedge|B|<|A|\Rightarrow (\exists[/mm] X [mm]\subseteq A\backslash[/mm]
> > B): B [mm]\cup[/mm] X [mm]\in I_{k})[/mm]
>
> Oh ja da hast du recht, ich hatte gedacht A, B sind in der
> Ursprungsformel nur Elemente und keine Mengen, und wollte
> das irgendwie für Mengen umschreiben. Das mit Teilmenge
> und enthalten-sein verwirrt mich gerade total.
> >
> > [mm]I_k[/mm] ist eine Teilmenge der Potenzmenge von S !!!
> >
> > 2. Für ein Matroid sind noch weitere Eigenschaften zu
> > zeigen:
> >
> > (i) [mm]\emptyset \in I_k,[/mm]
> >
> > (ii) aus A [mm]\in I_k[/mm] und B [mm]\subseteq[/mm] A folgt B [mm]\in I_k.[/mm]
> >
> >
> > >
> > > Seien A,B [mm]\subseteq I_{k}[/mm] und |B|<|A|. Dann existiert eine
> > > Teilmenge X [mm]\subseteq[/mm] A, die nicht in B ist.
> >
> > Das ist richtig. Es wird aber mehr verlangt, nämlich [mm]X \subseteq A \setminus B[/mm].
> > Kannst Du solch ein X angeben ?
> >
> >
> > >
> > > Da |B|<|A| und A,B [mm]\subseteq I_{k}[/mm] folgt [mm]|B|
> >
> > Das ist völliger Quark ! Es sind A,B [mm]\in I_k.[/mm]
> >
> > [mm]|B|
> > [mm]I_k[/mm] eine Menge von Mengen.
> >
> >
> >
> >
> > > (also
> > > [mm]B\not=I_{k}).[/mm] Also gilt [mm]B\cup[/mm] X [mm]\subseteq I_{k}.[/mm]
> >
> > ??? Schüttelkopf , Kopfschüttel ! Ich kann Dir nicht
> > folgen, weil es nichts zum folgen gibt
> >
> > FRED
> > >
> > > Vielen Dank und Lieben Grüß!
> > >
> > > PS: Ich hoffe das ist im Forum Graphentheorie richtig
> > > aufgehoben.
> >
>
> Ich versuchs noch einmal xD
>
> Vor.: Es sei (S, [mm]I_{k})[/mm] ein Mengensystem, wobei S eine
> endliche Menge und [mm]I_{k}[/mm] die Menge aller Teilmengen von S
> mit [mm]\le[/mm] k Elementen ist.
Sagen wir es ganz deutlich:
[mm] I_k [/mm] ist eine Menge, deren Elemente wieder Mengen sind. Und zwar enthält [mm] I_k [/mm] alle Teilmengen von S, welche höchstens k Elemente haben.
Ist das nun klar ?
>
> Beh.: (S, [mm]I_{k})[/mm] ist ein Matroid.
>
> Bew. (z.Z:
> (i) [mm]\emptyset \in I_k,[/mm] (warum muss das gezeigt werden?)
Das gehört mit zur Definition eines Matroids !
> (ii) A [mm]\in I_k[/mm] [mm]\wedge[/mm] B [mm]\subseteq[/mm] A [mm]\Rightarrow[/mm] B [mm]\in I_k.[/mm]
>
> (iii) A,B [mm]\in I_{k}\wedge|B|<|A|\Rightarrow (\exists[/mm] X
> [mm]\subseteq A\backslash[/mm] B): B [mm]\cup[/mm] X [mm]\in I_{k})[/mm])
>
> (zu i) [mm]\emptyset[/mm] ist in [mm]I_k,[/mm] weil [mm]I_k[/mm] die Menge aller
> Teilmengen von S ist und [mm]\emptyset[/mm] Teilmenge jeder Menge
> ist.
Nein, [mm] I_k [/mm] ist nicht die Menge aller Teilmengen von S, sondern nur die Menge aller Teilmengen von S die höchstens k Elemente haben !
Es ist [mm] \emptyset [/mm] eine Teilmenge von S, einverstanden ? O.K.
Hat [mm] \emptyset [/mm] mehr als k Elemente ? Natürlich nicht ! Somit: [mm] \emptyset \in I_k.
[/mm]
>
> (zu ii)Sei A [mm]\in I_k[/mm] und B [mm]\subseteq[/mm] A.
> A ist eine Menge
> von Teilmengen von S,
Nein ! A ist eine Teilmenge von S
> und weil B eine Teilmenge davon ist,
> ist auch B [mm]\in[/mm] A.
Unfug ! Es ist B [mm] \subseteq [/mm] A, nach Voraussetzung !!!!
Sei also A [mm] \in I_k [/mm] und B [mm] \subseteq [/mm] A. Zu zeigen ist: B [mm] \in I_k [/mm] .
Dazu musst Du zeigen:
1. B ist eine Teilmenge von S
und
2. B hat höchstens k Elemente.
>
> (zu iii) Seien A, B [mm]\in I_k[/mm] und |B|<|A|. Dann gibt es also
> in A mindestens eine Teilmenge X, die nicht in B ist. Also
> X [mm]\subseteq[/mm] (oder [mm]\in?) A\backslash[/mm] B.
X [mm] \subseteq [/mm] A [mm] \setminus [/mm] B.
Welches X leistet das ?????
> Weil X [mm]\subseteq A\backslash[/mm] B und A [mm]\in I_k,[/mm] gilt auch X
> [mm]\in I_k.[/mm] Und da auch B [mm]\in I_k[/mm] ist,
> folgt B [mm]\cup[/mm] X [mm]\in I_k.[/mm]
Ohne die Angabe, wie X aussieht kannst Du das nicht schließen !
Ich machs Dir mal vor:
seien also A, B [mm]\in I_k[/mm] und |B|<|A|.
Wegen |B|<|A| , ist B eine echte Teilmenge von A. Somit ex. ein a [mm] \in [/mm] A mit a [mm] \notin [/mm] B.
Setze [mm] X:=\{a\}. [/mm] Damit haben wir X [mm] \subseteq [/mm] A [mm] \setminus [/mm] B.
Jetzt ist noch zu zeigen: $X [mm] \cup [/mm] B [mm] \in I_k$
[/mm]
X und B sind Teilmenge von S, das sollte klar sein.
Verbleibt noch zu zeigen: $X [mm] \cup [/mm] B $ hat höchstens k Elemente.
A hat höchsten k Elemente, also folgt aus |B|<|A|:
B hat höchstens k-1 Elemente.
Da X genau ein Element enthält, enthält $X [mm] \cup [/mm] B $ höchstens 1+(k-1)=k Elemente.
Bingo !
FRED
>
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 16:53 Mi 18.11.2015 | | Autor: | JohnDoe123 |
Im nachhinein wirkt das alles soweit schlüssig, das man mit dem k argumentieren kann ist mir garnicht in den Sinn gekommen. Vielen Dank auf jedenfall für deine Mühe!
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 06:55 Do 19.11.2015 | | Autor: | fred97 |
> Im nachhinein wirkt das alles soweit schlüssig,
.... es ist schlüssig !
> das man
> mit dem k argumentieren kann ist mir garnicht in den Sinn
> gekommen.
Voraussetzungen in einer Aufgabe sind dazu da, dass man sie verwendet !!
Du kannst nicht nur mit diesem k argumentieren, Du musst !
Stell Dir mal vor, es wäre [mm] I_k [/mm] die Menge aller Teilmengen von S.
1. wozu dann der Index k ????
2. in diesem Fall ist [mm] (S,I_k) [/mm] auch ein Matroid. Aber das ist eine Trivialität. Warum ?
FRED
> Vielen Dank auf jedenfall für deine Mühe!
>
|
|
|
|
