www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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.vorhilfe.de