Matroide < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | 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?
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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. :/
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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 ?
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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 :)
|
|
|
| |
|
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
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | 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.
|
|
|
| |
|
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]](/images/smileys/ok.gif "[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
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | 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 :(
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 20:20 Di 14.01.2014 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | 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
|
|
|
|
