matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

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
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieBeweis Matroid
Foren für weitere Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
Forum "Graphentheorie" - Beweis Matroid
Beweis Matroid < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Beweis Matroid: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:22 Mo 16.11.2015
Autor: JohnDoe123

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.

        
Bezug
Beweis Matroid: Antwort
Status: (Antwort) fertig Status 
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.


Bezug
                
Bezug
Beweis Matroid: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 20:50 Di 17.11.2015
Autor: JohnDoe123


> > 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]


Bezug
                        
Bezug
Beweis Matroid: Antwort
Status: (Antwort) fertig Status 
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

>  
>  


Bezug
                                
Bezug
Beweis Matroid: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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!


Bezug
                                        
Bezug
Beweis Matroid: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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!
>  


Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


Alle Foren
Status vor 19h 41m 5. angela.h.b.
SIntRech/Partielle Integration/Substitu
Status vor 21h 24m 5. Takota
UAnaRn/Satz Implizite Funktion System
Status vor 1d 10h 48m 2. HJKweseleit
UFina/Effektiver Zinssatz
Status vor 1d 20h 18m 3. Dom_89
DiffGlGew/Lösung der DGL bestimmen
Status vor 1d 22h 18m 2. Gonozal_IX
UWTheo/Konstruktion von ZV
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]