www.matheraum.de
Das Matheforum.
Das Matheforum des MatheRaum.

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · 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

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
Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieMatroide
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Graphentheorie" - Matroide
Matroide < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Matroide: Tipp/Hilfe
Status: (Frage) beantwortet Status 
Datum: 18:28 So 12.01.2014
Autor: rsprsp

Aufgabe
Ich will nur wissen ob ich es richtig verstehe:

Ich soll zeigen ob es ein Matroid oder keins ist und habe dazu Mengenpaare:

S= [mm] \IN [/mm]
U= {leere Menge, {1},{2},{3},{1,2},{2,3}}

Damit ist es kein Matroid, denn nicht alle Elemente der Potenzmenge der Menge der [mm] \IN [/mm] in der U- Menge drin sind.

Verstehe ich das richtig?

        
Bezug
Matroide: Antwort
Status: (Antwort) fertig Status 
Datum: 18:34 So 12.01.2014
Autor: schachuzipus

Hallo,

> Ich will nur wissen ob ich es richtig verstehe:

>

> Ich soll zeigen ob es ein Matroid oder keins ist und habe
> dazu Mengenpaare:

>

> S= [mm]\IN[/mm]
> U= {leere Menge, {1},{2},{3},{1,2},{2,3}}
> Damit ist es kein Matroid, denn nicht alle Elemente der
> Potenzmenge der Menge der [mm]\IN[/mm] in der U- Menge drin sind.

>

> Verstehe ich das richtig?

Ich denke nicht.

[mm]\mathcal U[/mm] ist doch lediglich eine Teilmenge von [mm]\mathcal P(\IN)[/mm], und die Elemente aus dem hier gegebenen [mm]\mathcal U[/mm] sind allesamt Teilmengen von [mm]\IN[/mm]

Es ist nirgends gesagt, dass [mm]\mathcal U[/mm] alle Teilmengen von [mm]\IN[/mm] enthalten muss.

Wie kommst du darauf?

Prüfe, ob die vier Eigenschaften eines Matroids erfüllt sind ...

Gruß

schachuzipus

Bezug
                
Bezug
Matroide: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:39 So 12.01.2014
Autor: rsprsp

Ich habe die vier Eigenschaften bei Wikipedia gefunden:
http://de.wikipedia.org/wiki/Matroid

Das erste ist aufjeden Fall erfuellt.

Koenntest du mir bei den andern vier helfen? Ich verstehe sie kaum. :/

Bezug
                        
Bezug
Matroide: Antwort
Status: (Antwort) fertig Status 
Datum: 18:45 So 12.01.2014
Autor: schachuzipus

Hallo,

wo ist denn das Problem?

Schreibe die Eigenschaften mal auf und gehe sie durch ...

Als Tipp:

Schaue mal genau auf die Eigenschaft:

[mm] $\forall A,B\in\Mathcal U:|B|<|A|\Rightarrow\exists x\in A\setminus B:B\cup\{x\}\in\mathcal [/mm] U$

Ist die erfüllt oder kannst du 2 Mengen [mm] $A,B\in \mathcal [/mm] U$ angeben, die diese Bedingung verletzen?!

Gruß

schachuzipus

Bezug
                                
Bezug
Matroide: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 18:51 So 12.01.2014
Autor: rsprsp

Heisst es, dass die Mengen der Menge U "transitiv" sein sollen?

also wenn A={1,2} und B={2,3} dann muss es auch eine Menge C={1,3} geben?

Liege ich richtig ?

Bezug
                                        
Bezug
Matroide: Antwort
Status: (Antwort) fertig Status 
Datum: 19:03 So 12.01.2014
Autor: schachuzipus

Hallo,

> Heisst es, dass die Mengen der Menge U "transitiv" sein
> sollen?

Wie man das nennt, weiß ich nicht ...

>

> also wenn A={1,2} und B={2,3} dann muss es auch eine Menge
> C={1,3} geben?

Nein, [mm]A[/mm] und [mm]B[/mm] erfüllen die Voraussetzung [mm]|B|<|A|[/mm] nicht: [mm]2\not < 2[/mm]

>

> Liege ich richtig ?

Nein. Aber mein Tipp war auch kein guter, dachte zuerst, diese Eigenschaft sei verletzt, aber sie ist es nicht ...

Prüfen wir doch mal:

ZB. [mm]B=\{1\}[/mm] und [mm]A=\{2,3\}[/mm]

Dann gib es ein [mm]x\in A\setminus B=A[/mm], sodass [mm]B\cup\{x\}\in\mathcal U[/mm] liegt.

Nämlich [mm]x=2[/mm], denn [mm]B\cup\{2\}=\{1\}\cup\{2\}=\{1,2\}\in\mathcal U[/mm]

Prüfe so alle weiteren Möglichkeiten für die Mengen [mm]A[/mm] und [mm]B[/mm] - soviele sind das ja nun nicht ...

Gruß

schachuzipus

Bezug
                                                
Bezug
Matroide: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:19 So 12.01.2014
Autor: rsprsp

Es gibt noch

B={3} und A={1,2} somit ist x=2 und die Menge {2,3} [mm] \in [/mm] U

Es sind alle 3 Eigenschaften erfuellt und es ist ein Matroid.

Jetzt die Eigenschaften:
1. Die leere Menge muss [mm] \in [/mm] U sein.
2. Die Elemente der naechst groesseren Menge muessen in der naechst kleineren Menge enthalten sein z.B. U={{},{1},{2},{1,2}} somit ist {} {1} und {2} [mm] \in [/mm] {1,2} enthalten und Matroid.
3. Ober erklaert mit Bsp.

Habe ich die drei verstanden? Wenn ja mache ich gleich meine Aufgaben und schicke sie hier zur Kontrolle :)



Bezug
                                                        
Bezug
Matroide: Antwort
Status: (Antwort) fertig Status 
Datum: 19:26 So 12.01.2014
Autor: schachuzipus

Hallo nochmal,

> Es gibt noch

>

> B={3} und A={1,2} somit

kannst du [mm] $x=2\in A\setminus [/mm] B$ wählen, so dass ...

> ist x=2 und die Menge {2,3} [mm]\in[/mm] U

Genau!


Fehlen noch die anderen Möglichkeiten.

Du hast doch 3 Mengen mit je einem Element und 2 mit je 2 Elementen, daraus musst du alle nötigen Kombinationen prüfen ...

>

> Es sind alle 3 Eigenschaften erfuellt und es ist ein
> Matroid.

>

> Jetzt die Eigenschaften:
> 1. Die leere Menge muss [mm]\in[/mm] U sein.
> 2. Die Elemente der naechst groesseren Menge muessen in
> der naechst kleineren Menge enthalten sein z.B.
> U={{},{1},{2},{1,2}} somit ist {} {1} und {2} [mm]\in[/mm] {1,2}
> enthalten und Matroid.

Das verstehe ich nicht ...


> 3. Ober erklaert mit Bsp.

Reicht nicht aus!

>

> Habe ich die drei verstanden? Wenn ja mache ich gleich
> meine Aufgaben und schicke sie hier zur Kontrolle :)

>
>

Ich habe 4 Eigenschaften auf Wikipedia gefunden. Davon sind 2 trivialerweise erfüllt, die anderen beiden (und davon insbesondere 3.) erfordern etwas Rechenaufwand (aber sehr überschaubar)

Schreibe du vllt. mal alle Eigenschaften auf, damit jeder, der mitliest, auch weiß, worum es hier geht ...

Dient ja auch der Selbstkontrolle

Gruß

schachuzipus

Bezug
                                                                
Bezug
Matroide: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:37 So 12.01.2014
Autor: rsprsp

Ich habe in der 3 Eigenschaft nur das Kombiniert was nicht gepasst hat, den rest habe ich mir schon gedacht.


In meinem Mathe-Skript stehen 3 Eigenschaften:

1. {} [mm] \in [/mm] U
d.h. die leere Menge ist in U enthalten.

2. Gilt A [mm] \in [/mm] U und B [mm] \subseteq [/mm] A, dann muss auch B [mm] \in [/mm] U.
d.h. in meinen Augen, dass wenn es z.B {1,2} gibt muessen alle Teilmengen der Menge {1,2} in U enthalten sein also {},{1},{2}.

3. Gillt A,B [mm] \in [/mm] U und |A|+1=|B| dann muss ein x [mm] \in B\A [/mm] exisitieren mit A [mm] \cup [/mm] {x} [mm] \in [/mm] U.
d.h Wenn z.B. die Menge {1,2} das Element {3} [mm] \in [/mm] U  nicht enthaelt muss die Menge U ein Element {1,3} bzw {3,1} oder {2,3} bzw {3,2} enthalten.

So habe ich das verstanden.

Bezug
                                                                        
Bezug
Matroide: Antwort
Status: (Antwort) fertig Status 
Datum: 19:45 So 12.01.2014
Autor: schachuzipus

Hallo nochmal,

> Ich habe in der 3 Eigenschaft nur das Kombiniert was nicht
> gepasst hat, den rest habe ich mir schon gedacht.

>
>

> In meinem Mathe-Skript stehen 3 Eigenschaften:

>

> 1. {} [mm]\in[/mm] U
> d.h. die leere Menge ist in U enthalten.

>

> 2. Gilt A [mm]\in[/mm] U und B [mm]\subseteq[/mm] A, dann muss auch B [mm]\in[/mm] U. [ok]
> d.h. in meinen Augen, dass wenn es z.B {1,2} gibt muessen
> alle Teilmengen der Menge {1,2} in U enthalten sein also
> {},{1},{2}.

Genau! Und das müsstest du für alle möglichen Kombinationen zeigen

>

> 3. Gillt A,B [mm]\in[/mm] U und |A|+1=|B| dann muss ein x [mm]\in B\A[/mm]
> exisitieren mit A [mm]\cup[/mm] {x} [mm]\in[/mm] U.

Ok, wiki fasst das etwas allg. mit $|A|<|B|$ (bzw. mit vertauschten Rollen)

> d.h Wenn z.B. die Menge {1,2} das Element {3} [mm]\in[/mm] U nicht
> enthaelt muss die Menge U ein Element {1,3} bzw {3,1} oder
> {2,3} bzw {3,2} enthalten.

Jo!

>

> So habe ich das verstanden.

Das ist doch gut, du musst nur für jeden Punkt (also für 2. und 3.) alle Möglichkeiten durchgehen.

Bei wiki war noch ein Punkt 4., der besagt, dass alle Mengen aus [mm] $\mathcal [/mm] U$ endlich sein sollen ...

Gruß

schachuzipus

Bezug
                                                                                
Bezug
Matroide: Frage (überfällig)
Status: (Frage) überfällig Status 
Datum: 19:53 So 12.01.2014
Autor: rsprsp

Hier sind meine Aufgaben:
http://www.gute-mathe-fragen.de/?qa=blob&qa_blobid=17786349518831091084

Ich habe alle 3 int 5 Minuten geloest obwohl ich vor einer Stunde kein Wort verstanden habe was die von mir wollen.

a) ist ein Metroid, denn alle Eigenschaften erfuellt sind
b) U= { w,z,1,y,x,(w,z),(w,x),(w,1),(x,y),(x,1),(y,1),(z,1),(w,x,1),(x,y,1)} hab Mengenzeichen zwischen den einzelnen immer weggelassen

Somit ist die 3 Eigenschaft nicht erfuellt, denn:
B={z} und A={x,y} => {z,x},{z,y},{x,z},{y,z} => keins davon ist [mm] \in [/mm] U

c)  ist ein Metroid, denn alle Eigenschaften erfuellt sind.

Mit d) komme ich gar nicht klat :(

Bezug
                                                                                        
Bezug
Matroide: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 20:20 Di 14.01.2014
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
        
Bezug
Matroide: Antwort
Status: (Antwort) fertig Status 
Datum: 18:38 So 12.01.2014
Autor: leduart

Hallo
U muss nicht alle elemente von P(S) enthalten, sonst wäre es ja selbst P(E)
lies die Def von matroid nach und zige oder widerlege die 4 Bedingungen. keine davon ist U=P(E)
Gruss leduart

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


^ Seitenanfang ^
www.matheforum.net
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]