Matroide < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
Hallo Zusammen,
| Aufgabe | Zeigen Sie, daß mit [mm] $\left(S, \mathcal{I}\right)$ [/mm] auch [mm] $\left(S, \mathcal{I}'\right)$ [/mm] ein Matroid ist, wobei
[mm] $\mathcal{I}' [/mm] := [mm] \left\{A'\,|\,A' \subseteq S \wedge S-A' \texttt{ enthält eine maximal unabhängige Menge aus }\mathcal{I}\right\}$. [/mm] |
Ich habe hier zwei Probleme. Zum Einen verstehe ich die Definition von [mm] $\mathcal{I}'$ [/mm] nicht (Insbesondere die zweite Mengenbedingung); Zum Anderen habe ich eine schwammige Vorstellung davon, was maximale Unabhängigkeit bedeutet. Diese ist ja so definiert:
Es sei $M = [mm] \left(S, \mathcal{I}\right)$ [/mm] ein Matroid. Ein Element $x [mm] \in [/mm] S-A$ heißt genau dann Erweiterung von $A [mm] \in \mathcal{I}$, [/mm] wenn $A [mm] \cup \left\{x\right\} \in \mathcal{I}$. [/mm] $A [mm] \in \mathcal{I}$ [/mm] heißt genau dann maximal, wenn A keine Erweiterung besitzt.
Irgendwie ist es klar, daß [mm] $A\!$ [/mm] bei jedem "Erweiterungsversuch" das "neue" Element einfach "schlucken" würde, weil es ja schon in [mm] $A\!$ [/mm] ist. Aber es wäre trotzdem schön, wenn mir jemand ein Beispiel von einem Matroid angeben könnte, wo man das beobachten kann.
Vielen Dank!
Viele Grüße
Karl
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:32 Do 23.06.2005 | | Autor: | DaMenge |
Hallo nochmal Karl,
also ich werde mal versuchen dir ein bischen das Konzept von Matroiden zu erklären und dabei gleich ein einfaches Beispiel geben, nach dem du gefragt hast:
also ich nenne mal alles um, damit ich nicht ständig im Mathe-Modus schreiben muss: Wir haben also unsere endliche Menge E und unsere Menge F von unabhängigen Teilmengen aus E.
Wann ist nun eine Teilmenge von E unabhängig?
Nun ja, durch F definieren wir, wann sie unabhängig ist - es müssen nur die beiden ersten Axiome gelten (also E endlich und jede Teilemenge einer Menge in F ist auch wieder in F) - also insbesondere müssen wir uns nichts besonderes unter "unabhängig" vorstellen, wie es in der LA üblich war.
Kommen wir zu einem Beispiel aus der Graphentheorie: zeichne dir ein vollständiges Dreieck und benenne die Seiten a, b und c
dann definieren wir: E={a,b,c} also die Kantenmenge des Graphen
und F= Teilmengen von E, die kreisfrei sind, also :
F={ {},{a},{b},{c},{a,b},{a,c},{b,c} }
man sieht auch leicht, dass (E,F) ein Matroid ist.
so, was bedeutet nun maximal unabhängig?
wie du schon sagtest: wenn man zu A aus F noch etwas aus E dazu nehmen will, was noch nicht darin ist, dann soll es zusammen nicht mehr in F sein.
oder hier: wenn du zu zwei Seiten des Dreiecks noch eine hinzufügen willst, hast du immer einen Kreis, also ist es dann nicht mehr in F.
das heißt: hier haben alle maximal unabhängigen Mengen die Kardinalität 2
[in jedem Matroid gilt, dass die maximal unabhängigen Mengen die gleiche Kardinalität haben, dies ist sogar äquivalent zur dritten geforderten Eigenschaft]
Kommen wir nun zu deiner etwas komisch aussehenden Definition von F':
$ F' := [mm] \left\{A'\,|\,A' \subseteq E \wedge E-A' \text{ enthält eine maximal unabhängige Menge aus } F \right\} [/mm] $
also wir suchen Teilmengen von E, deren Komplement in E immernoch eine maximale Menge aus F enthalten.
also an unserem Beispiel wären das gerade: F'={{},{a},{b},{c}}
denn für jede Kante gilt: ihr Komplement (also die anderen zwei Kanten) ist maximal in F.
So, warum ist nun (E,F') auch ein Matroid ? Weil:
-E ist immernoch endlich
-wenn man nur eine Teilmenge von A' betrachten ist das Komplement höchstens größer geworden, also liegt immernoch das maximale Element von F drinne wie bei A'
-als dritte Eigenschaft könnte man hier leicht mit der Äquivalenz der Kardinalitäten der maximalen Elemente von F' argumentieren - ich weiß nur nicht, ob ihr das schon hattet.
Solltest du dieses letzte schon kennen, sollte der allgemeine Fall (also nicht beschränkt auf dieses Beispiel) dir kaum noch Probleme bereiten.
Frage ruhig zur Not nach
viele Grüße
DaMenge
|
|
|
| |
|
Hallo DaMenge,
> -wenn man nur eine Teilmenge von A' betrachten ist das
> Komplement höchstens größer geworden, also liegt immernoch
> das maximale Element von F drinne wie bei A'
>
> -als dritte Eigenschaft könnte man hier leicht mit der
> Äquivalenz der Kardinalitäten der maximalen Elemente von F'
> argumentieren - ich weiß nur nicht, ob ihr das schon
> hattet.
Ich habe jetzt versucht die Aufgabe nachzuvollziehen und dabei folgendes Bild gemacht:
[Dateianhang nicht öffentlich]
Hier sieht man, daß die Mengen im roten Kastchen (zusammen mit der Trägermenge) ein Matroid bilden. Man sieht auch, daß diese Menge jeweils ein Element weniger haben, als ihre maximal unabhängigen "Gegen"-Mengen. Aber wie soll ich jetzt hier weiterargumentieren?
Vielen Dank!
Viele Grüße
Karl
Dateianhänge:
Anhang Nr. 1 (Typ: gif) [nicht öffentlich]
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:37 So 26.06.2005 | | Autor: | DaMenge |
Hey Karl,
du musst wesentlich mehr schreiben, wenn ich nicht bloss raten soll, was du tust.
Also ich denke, du versuchst ebenso F als Kreisfreie Teilmengen der Kantenmenge deines Graphen zu beschreiben, richtig?
und? wie groß sind alle maximalen Elemente von F?
(wie sieht überhaupt F aus ?)
jetzt hast du irgendwie versucht F' zu bestimmen - was bedeuten die "n" bzw. "j" dahinter?
eigentlich musst du jetzt testen, ob das Komplemet eine maximale Kreisfreie Teilmenge aus F enthält, Bsp: {a} ist in F', denn das Komplement ist {b,c,d,e} und darin ist {c,d,e}, was maximal kreisfrei in F ist !!
(die leere Menge ist sowieso immer in F bzw F' ...)
Jedoch ist deine grüne Menge richtig die maximalen Elemente von F' und sie sind alle gleich-groß !
Jetzt kommt die Königsfrage :
Weißt du dass folgende Äquivalenz gilt:
M=(E,F) ist ein Matroid
$ [mm] \gdw [/mm] $
es gelten :
1) E ist endlich
2) für jedes f aus F gilt dass auch jede Teilmenge aus f in F ist
3) $ [mm] \forall [/mm] C,D [mm] \in [/mm] F: [mm] \left| C \right| [/mm] < [mm] \left| D \right| \Rightarrow \exists [/mm] b [mm] \in [/mm] D - C:C + [mm] \left\{ b \right\} \in [/mm] F $
$ [mm] \gdw [/mm] $
es gelten :
1) E ist endlich
2) für jedes f aus F gilt dass auch jede Teilmenge aus f in F ist
3) alle maximalen Elemente aus F sind gleich groß
wenn du dieses letzte wüsstest, dann sollte deine Argumentation ungefähr so laufen : alle maximalen Elemente m aus F haben größe n, dann sind (E ohne m) die maximalen Element des Komplements (Warum maximal?!?) mit größe (|E|-n), also insbesondere auch gleich groß.
frage ruhig nach bzw. erkläre mir genauer, wo deiner Probleme sind.
viele Grüße
DaMenge
|
|
|
| |
|
Hallo DaMenge,
> Hey Karl,
>
> du musst wesentlich mehr schreiben, wenn ich nicht bloss
> raten soll, was du tust.
Ich hätte wohl wirklich mehr zu meinem Beispiel schreiben sollen; Das hole ich jetzt nach:
Ich habe versucht die Definition von [mm] $\left(S, \mathcal{I}'\right)$ [/mm] in der Aufgabenstellung nachzuvollziehen. Dazu habe ich mir einen Graphen gemalt und habe mir dann die Potenzmenge aller Kanten dieses Graphen notiert. Danach habe ich die Matroiden-Definition auf die Potenzmenge losgelassen und alle Teilmengen aus der Potenzmenge entfernt, die Zyklen im Graph verursachten. So entstand mein Matroid [mm] $\left(S, \mathcal{I}\right)$. [/mm] Die 3 Bedingungen sind dann nämlich erfüllt. [mm] $S\!$ [/mm] ist endlich, [mm] $\mathcal{I}$ [/mm] enthält nur zyklenfreie Mengen, die Mengen sind in diesem Sinne also unabhängig und wegen der Zyklenfreiheit sind es ihre Teilmengen erst recht. Die dritte Bedingung ist dann auch erfüllt.
Dann habe ich die Definition aus der Aufgabe auf diesen Matroiden angewendet. Alle Teilmengen, deren Komplemente zyklenfreie Teilmengen des Graphen sind, kommen in Frage. Nachdem ich diese aussortiert hatte (mit dunklem [mm] $j\!$ [/mm] (für ja) markiert), wendete ich die eigentliche Definition an und übrigblieben nur die grünen Mengen in der Box, weil ihre Komplementmengen maximal unabhängige Teilmengen des Graphen sind:
> (wie sieht überhaupt F aus ?)
[mm] $\mathcal{I}' [/mm] := [mm] \left\{\left\{a,b\right\},\left\{a,d\right\},\left\{a,e\right\}\right\}$.
[/mm]
> und? wie groß sind alle maximalen Elemente von F?
Ich denke, ich habe die Definition doch noch nicht verstanden. Wenn ich jetzt z.B. [mm] $\left\{a,b\right\}$ [/mm] nehme und noch [mm] $d\!$ [/mm] hinzufüge, erhalte ich trotzdem einen zyklenfreien
Untergraphen. Das widerspricht aber der Maximalität.
> eigentlich musst du jetzt testen, ob das Komplemet eine
> maximale Kreisfreie Teilmenge aus F enthält, Bsp: {a} ist
> in F', denn das Komplement ist {b,c,d,e} und darin ist
> {c,d,e}, was maximal kreisfrei in F ist !!
> (die leere Menge ist sowieso immer in F bzw F' ...)
>
> Jedoch ist deine grüne Menge richtig die maximalen Elemente
> von F' und sie sind alle gleich-groß !
Ist die grüne Menge wirklich richtig? Irgendwie habe ich mich (oben) gerade überzeugt einen Fehler gemacht zu haben.
> frage ruhig nach bzw. erkläre mir genauer, wo deiner
> Probleme sind.
Danke! Aber ich fürchte, ich habe Probleme mit dieser Definition. Die Elemente, die ich nachher für [mm] $\mathcal{I}'$ [/mm] rauskriege sind ja nicht maximal... . Wie kann man das korrigieren?
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 10:47 Mo 27.06.2005 | | Autor: | DaMenge |
Hi Karl,
ich bin erst am frühen Abend wieder hier, deshalb mal den dringenden Tip, dass du dir mein gegebenes Beispiel in der ersten Antwort anschaust - dort habe ich auch F und F' angegeben - versuche dies mal nachzu vollziehen, denn deine F und F' sind nicht vollständig.
(nach 2) müssen auch alle Teilmengen in F sein usw...)
bis später
DaMenge
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:03 Mo 27.06.2005 | | Autor: | DaMenge |
Hallo Karl,
ich hoffe, du hast dir zwischenzeitlich nochmal mein erstes Beispiel mit dem Dreieck angesehen - daran erkennt man, was I und I' ist...
> So
> entstand mein Matroid [mm]\left(S, \mathcal{I}\right)[/mm]. Die 3
> Bedingungen sind dann nämlich erfüllt. S ist endlich,
> [mm]\mathcal{I}[/mm] enthält nur Zyklenfreie Mengen, die Mengen sind
> in diesem Sinne also unabhängig und wegen der
> Zyklenfreiheit sind es ihre Teilmengen erst recht. Die
> dritte Bedingung ist dann auch erfüllt.
Und wie sieht nun I aus? Das hast du bisher noch nicht beschrieben - ist vielleicht auch eine lange Schreibarbeit, abe nur als Hinweis: wenn {c,b,d} in I ist, dann ist auch {},{c}{b}{d}{c,b}{c,d} und {b,d} darin...
{c,b,d} ist aber maximal in F (wie noch ein paar andere)
> So, und dann habe ich die Definition aus der Aufgabe auf
> diesen Matroiden angewendet. Alle Teilmengen deren
> Komplemente erstmal zyklenfreie Teilmengen des Graphen sind
> kommen erstmal in Frage.
Das verstehe ich nicht.
I' ist doch so definiert, wenn i in I' ist, dann ist im Komplement von i ein maximales Element aus I enthalten, beispiel:
{e} ist in I' , denn das Komplement ist {a,b,c,d} - das ist NICHT kreisfrei, aber das maximale Element {b,c,d} liegt im Komplement und nur darum geht es.
andererseits ist zum Beispiel auch {a,e} in I' , denn das Komplement ist {b,c,d} und das ist max. in I.
wieso ist nun {a,e} maximal in I' ?
Was würde sein, wenn ein i aus I' geben würde mit |i|=3 ?
(du weißt, dass jedes maximale Element in I auch Kardinalität 3 hat)
> [mm]\mathcal{I}' := \left\{\left\{a,b\right\},\left\{a,d\right\},\left\{a,e\right\}\right\}[/mm].
Du vergisst auch hier die Teilmengen
> > Jedoch ist deine grüne Menge richtig die maximalen Elemente
> > von F' und sie sind alle gleich-groß !
>
> Ist die grüne Menge wirklich richtig? Irgendwie habe ich
> mich (oben) gerade überzeugt einen Fehler gemacht zu haben.
> :(
Die grüne Menge ist, wie ich gerade festgestellt habe nur eine Teilmenge der maximalen Elemente von I' , also fehlen zum einen noch die anderen maximalen Elemente und zum anderen fehlen noch jede Teilmenge !!!
Wie du schon siehst verwende ich ständig, dass in einem Matroid alle maximalen Elemente des Unabhängigkeitssystem gleiche Größe haben, deshalb stelle ich nochmals die frage, ob dir das klar ist . (Siehe die Äquivalenz der König-Frage)...
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 19:57 Mo 27.06.2005 | | Autor: | Karl_Pech |
Hallo DaMenge,
Zunächst vielen Dank für deine Hilfe! Ich habe mir deine Antwort soeben durchgelesen und werde mir in der nächsten Zeit etwas dazu überlegen. Im Moment arbeite ich an einigen anderen Sachen, so daß ich das Thema 'Matroide' erstmal ruhen lassen muß. Tut mir Leid, daß ich jetzt nicht auf deine Antwort reagieren kann.
Viele Grüße
Karl
|
|
|
|
