Matching und Matroid < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | | Sei G ein Graph und [mm] \mathcal{F} [/mm] die Familie aller Mengen [mm] $X\subseteq [/mm] V(G)$, für die ein Matching maximaler Kardinalität in G existiert, das keinen Knoten in X überdeckt. Zeige, dass [mm] (V(G),\mathcal{F}) [/mm] ein Matroid ist. Was ist das duale Matroid? |
Hallo liebe Leute!
Für obige Aufgabe gibt es vier Punkte, deswegen schätze ich, dass es in meiner Lösungsidee einen Fehler gibt. Das wäre sonst zu einfach... 
Dass obiges ein Unabhängigkeitssystem ist, ist ja klar. Die letzte Eigenschaft, damit es ein Matroid ist, wollte ich damit zeigen, dass alle Basen gleiche Kardinalität haben. Nun ist die Frage, was denn hier eine Basis ist. Und zwar bin ich der Meingung, dass alle Elemente von [mm] \mathcal{F} [/mm] eine Basis sind. Denn die Matchings sind doch kardinalitätsmaximal, also kann ich dort kein Element rausnehmen und zu X packen. Falls ihr versteht, was ich meine.
Naja, und da die Matchings ja kardinalitätsmaximal sein sollen, haben sie doch alle die gleiche Kardinalität, und demnach haben auch alle Elemente von [mm] \mathcal{F} [/mm] die gleiche Kardinalität. Und da sie alle Basen sind, haben eben alle Basen gleiche Kardinalität!
Ist das so richtig oder wo liegt der Denkfehler?
Viele liebe Grüße
Pippilotta
|
|
| |
|
Hallo!
Wieso antwortet denn nie jemand auf meine Fragen? So schwierig kann das doch nicht sein, mir zu sagen, ob das Obige richtig ist!? Bitte versucht es doch nochmal - bis heute abend könnte mir das noch helfen.
Viele liebe Grüße
Pippilotta
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 12:19 Mo 25.06.2007 | | Autor: | dormant |
Hi!
Es ist mir aufgefallen, das meine Antwort nicht richtig ist. Es ist nämlich so, dass nicht alle Mengen im Matriod die selbe Kardinalität haben. Das kommt dann vor, wenn |V|=n und |max Matching|<=n-1. Dann entspricht [mm] |\emptyset|=0 [/mm] und die maximale Menge der Knoten, die vom max Matching nicht überdeckt wird, deren Kard dann größer Null ist, ein und demselben max Matching:
1 2 3
._. .
Hier kann man als X einerseits [mm] \emptyset [/mm] nehmen, andererseits 3. 1-2 bleibt das max Matching.
Das Ding ist, dass wenn eine Menge [mm] V\A [/mm] ein max Matching enthält, dann sehr wohl auch [mm] V\backslash A\cup\{x\} [/mm] für ein [mm] x\in B\backslash [/mm] A und B, A [mm] \in \mathcal{F} [/mm] und |B|>|A|. Damit hat man auch die gewünschte Eigenschaft.
Gruß,
dormant
ORIGINALTEXT:
Hi!
> Dass obiges ein Unabhängigkeitssystem ist, ist ja klar. Die
> letzte Eigenschaft, damit es ein Matroid ist, wollte ich
> damit zeigen, dass alle Basen gleiche Kardinalität haben.
Welche ist laut dir diese letzte Eigenschaft? Ich denk mal das ist doch
iii) A, B [mm] \in \mathcal{F} [/mm] und |A|<|B|, dann [mm] \exists x\in B\backslash [/mm] A mit [mm] A\cup\{x\}\in\mathcal{F} [/mm] , oder?
> Nun ist die Frage, was denn hier eine Basis ist. Und zwar
> bin ich der Meingung, dass alle Elemente von [mm]\mathcal{F}[/mm]
> eine Basis sind. Denn die Matchings sind doch
> kardinalitätsmaximal, also kann ich dort kein Element
> rausnehmen und zu X packen. Falls ihr versteht, was ich
> meine.
> Naja, und da die Matchings ja kardinalitätsmaximal sein
> sollen, haben sie doch alle die gleiche Kardinalität, und
> demnach haben auch alle Elemente von [mm]\mathcal{F}[/mm] die
> gleiche Kardinalität. Und da sie alle Basen sind, haben
> eben alle Basen gleiche Kardinalität!
>
> Ist das so richtig oder wo liegt der Denkfehler?
Hier beweist du, dass alle Mengen des Matriods gleicher Kardinalität sind, was auch die Eigenschaft iii) erschlägt. Völlig in Ordnung. Ob es Basen sind, oder nicht, ist erst ein Mal nicht so wichtig - man muss erst wissen, dass es um ein Matroid geht, bevor man irgendetwas Basis nennt. Ansonsten - alles i. O., so schwer ist es wirklich nicht.
Gruß,
dormant
|
|
|
| |
|
Hallihallo dormant!
Hat also doch was geholfen, dass ich nochmal lieb drum gebeten habe. 
> Es ist mir aufgefallen, das meine Antwort nicht richtig
> ist. Es ist nämlich so, dass nicht alle Mengen im Matriod
> die selbe Kardinalität haben. Das kommt dann vor, wenn
> |V|=n und |max Matching|<=n-1. Dann entspricht
> [mm]|\emptyset|=0[/mm] und die maximale Menge der Knoten, die vom
> max Matching nicht überdeckt wird, deren Kard dann größer
> Null ist, ein und demselben max Matching:
>
> 1 2 3
> ._. .
>
> Hier kann man als X einerseits [mm]\emptyset[/mm] nehmen,
> andererseits 3. 1-2 bleibt das max Matching.
Ja, da hast du Recht. Aber das Problem liegt doch dann einzig und allein daran, oder? Also alle anderen Mengen (also alle abgesehen von der leeren Menge), die in [mm] \mathcal{F} [/mm] liegen, haben die gleiche Kardinalität, oder?
> Das Ding ist, dass wenn eine Menge [mm]V\A[/mm] ein max Matching
> enthält, dann sehr wohl auch [mm]V\backslash A\cup\{x\}[/mm] für ein
> [mm]x\in B\backslash[/mm] A und B, A [mm]\in \mathcal{F}[/mm] und |B|>|A|.
> Damit hat man auch die gewünschte Eigenschaft.
Da bin ich gerade irgendwie anderer Meinung. Wenn - wie ich gerade behauptet habe - alle Mengen in [mm] \mathcal{F} [/mm] außer der leeren Menge die gleiche Kardinalität haben, dann kann der Fall |B|>|A| doch nur für [mm] A=\emptyset [/mm] eintreten. Oder nicht? Und dann wäre [mm] $V\backslash A\cup\{x\}=V\cup\{x\}$, [/mm] und das liegt offensichtlich nicht in [mm] \mathcal{F}!?
[/mm]
Und dann soll ich auch noch die Frage beantworten, was das duale Matroid ist - dafür bräuchte ich ja dann doch noch die Basen. Sind das dann alle Elemente, abgesehen von der leeren Menge?
Muss jetzt leider schnell weg - bin aber später nochmal hier.
Viele Grüße und schon mal danke für die Antwort
Pippilotta
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 17:36 Mo 25.06.2007 | | Autor: | dormant |
Hi!
> Ja, da hast du Recht. Aber das Problem liegt doch dann
> einzig und allein daran, oder? Also alle anderen Mengen
> (also alle abgesehen von der leeren Menge), die in
> [mm]\mathcal{F}[/mm] liegen, haben die gleiche Kardinalität, oder?
Nein: ._. . .
> Da bin ich gerade irgendwie anderer Meinung. Wenn - wie ich
> gerade behauptet habe - alle Mengen in [mm]\mathcal{F}[/mm] außer
> der leeren Menge die gleiche Kardinalität haben, dann kann
> der Fall |B|>|A| doch nur für [mm]A=\emptyset[/mm] eintreten. Oder
> nicht? Und dann wäre [mm]V\backslash A\cup\{x\}=V\cup\{x\}[/mm], und
> das liegt offensichtlich nicht in [mm]\mathcal{F}!?[/mm]
In diesem Fall wäre V+x=V, da x schon in V liegt. D.h. V enthätlt ein max Matching, und [mm] \emptyset\in\mathcal{F}= [/mm] das Komplement von V. Du neigst dazu die Knotenmenge, die von einem max Matching überdeckt wird, für Elemente des Matroids zu halten. Das Komplement dieser Mengen ist im Matroid.
> Und dann soll ich auch noch die Frage beantworten, was das
> duale Matroid ist - dafür bräuchte ich ja dann doch noch
> die Basen. Sind das dann alle Elemente, abgesehen von der
> leeren Menge?
Nein. Dazu musst du dich aber davon überzeugen, dass es auch mehrere Knoten geben kann, die von einem max Matching nicht überdeckt werden.
Zum dualen Matroid habe ich das herausgefunden (der Begriff ist mir nämlich neu): Consider a matroid M = (S, I). The dual matroid is M∗ = (S, I∗) where I∗:= {I ⊆ S : [mm] S\backslash [/mm] I is a spanning set for M }. That is, the complement of a basis of M , as well as all subsets of this, is independent in M∗. The bases of M∗ are the complements of the bases of M. It is straightforward to check that this is a matroid.
Das sind also in deinem Fall die Mengen aus dem primalen Matroid, die maximale Kardinalität haben, also Basen sind.
Gruß,
dormant
|
|
|
| |
|
Hallo nochmal!
Vielen Dank, aber leider verstehe ich das immer noch nicht so ganz...
> > Ja, da hast du Recht. Aber das Problem liegt doch dann
> > einzig und allein daran, oder? Also alle anderen Mengen
> > (also alle abgesehen von der leeren Menge), die in
> > [mm]\mathcal{F}[/mm] liegen, haben die gleiche Kardinalität, oder?
>
> Nein: ._. . .
Ok - aber wenn der Graph zusammenhängend ist, schon, oder? Und allgemein, machen dann alle isolierten Knoten das Problem!?
Dann verstehe ich aber immer noch nicht, warum das hier gilt, was du geschrieben hattest:
> > Das Ding ist, dass wenn eine Menge [mm] V\A [/mm] ein max Matching enthält, dann sehr wohl auch [mm] V\backslash A\cup\{x\} [/mm] für ein [mm] x\in B\backslash [/mm] A und B, A [mm] \in \mathcal{F} [/mm] und |B|>|A|. Damit hat man auch die gewünschte Eigenschaft.
Hab' das mal an einem Beispiel ausprobiert, und bin der Meinung, dass ich ein Gegenbeispiel gefunden habe. Aber vielleicht kannst du einfach mal begründen, warum das gelten soll?
> > Und dann soll ich auch noch die Frage beantworten, was das
> > duale Matroid ist - dafür bräuchte ich ja dann doch noch
> > die Basen. Sind das dann alle Elemente, abgesehen von der
> > leeren Menge?
>
> Nein. Dazu musst du dich aber davon überzeugen, dass es
> auch mehrere Knoten geben kann, die von einem max Matching
> nicht überdeckt werden.
Aber von jeder Zusammenhangskomponente immer nur einer, oder?
> Zum dualen Matroid habe ich das herausgefunden (der Begriff
> ist mir nämlich neu): Consider a matroid M = (S, I). The
Unsere Definition war: [mm] \mathcal{F}^{\star}=\{F\subset E: there is a basis B of (E,\mathcal{F}) such that F\cap B=\emptyset\}.
[/mm]
Übrigens kann man sehr wohl von Basis sprechen, auch wenn man kein Matroid sondern nur ein Unabhängigkeitssystem hat: maximal unabhängige Mengen heißen nämlich Basis. Jedenfalls bei uns.
> Das sind also in deinem Fall die Mengen aus dem primalen
> Matroid, die maximale Kardinalität haben, also Basen sind.
Sorry, aber was ist ein primales Matroid? Das hab ich noch nie gehört.
Viele Grüße nochmal
Pippilotta
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 20:03 Mo 25.06.2007 | | Autor: | dormant |
Hi!
Du willst es wirklich genau wissen... Stell dir vor der Graph sieht so aus:
. .
._ [mm] \backslash [/mm] ./_.
./ [mm] \backslash [/mm] .
(Hoffentlich verstehst du, was ich meine - wie ein Stern - ein Knoten in der Mitte und Strahlen zu 6 Knoten, die paarweise nicht adjezent sind).
Es gibt 6 max Matchings, jedes ist der Kardinalität 2 (bzgl. Knoten) und das jeweilige Komplement der Kardinalität 5 (auch bzgl. Knoten), was die Basen sind.
Angenommen der in der Mitte ist 0, oben links ist 1 und die Knoten werden von da im Uhrzeigersinn bis 6 durchnummeriert. Sei jetzt A={1,2}, B={1,2,3,4}. Dann ist [mm] B\backslash [/mm] A={3,4}, was auch in [mm] \mathcal{F} [/mm] ist. Überzeugt?
Eure Definition ist zu dieser, die ich gefunden hab äquivalent.
Ein primales Matroid ist einfach ein Ausdruck, den ich erfunden hab, um den dem dualen Matroid zugrundeliegenden Matroid zu bezeichnen, das ursprüngliche Matroid also. Wie primales und duales Programm (was schon richtige Begriffe sind) :)
Gruß,
dormant
|
|
|
| |
|
Hallo schon wieder!
Hoffe, du hast noch ein bisschen Geduld mit mir - ich will es in der Tat ganz genau wissen.
> . .
> ._ [mm]\backslash[/mm] ./_.
> ./ [mm]\backslash[/mm] .
>
> (Hoffentlich verstehst du, was ich meine - wie ein Stern -
> ein Knoten in der Mitte und Strahlen zu 6 Knoten, die
> paarweise nicht adjezent sind).
Ja, den Graph verstehe ich.
> Es gibt 6 max Matchings, jedes ist der Kardinalität 2
> (bzgl. Knoten) und das jeweilige Komplement der
> Kardinalität 5 (auch bzgl. Knoten), was die Basen sind.
>
> Angenommen der in der Mitte ist 0, oben links ist 1 und die
> Knoten werden von da im Uhrzeigersinn bis 6
> durchnummeriert. Sei jetzt A={1,2}, B={1,2,3,4}. Dann ist
> [mm]B\backslash[/mm] A={3,4}, was auch in [mm]\mathcal{F}[/mm] ist.
> Überzeugt?
Nein - denn ich will doch gar nicht zeigen, dass [mm] $B\backslash A\in\mathcal{F}$ [/mm] ist, sondern dass es ein [mm] $x\in B\backslash [/mm] A$ gibt, so dass [mm] $A\cup\{x\}\in\mathcal{F}$. [/mm] Aber ich sehe gerade meinen Fehler bei meinem angeblichen Gegenbeispiel von vorhin, ich dachte nämlich, dass es für alle solche x gelten muss...
Hab' mir jetzt überlegt, dass für ein festes kardinalitätsmaximales Matching M doch auf jeden Fall die Potenzmenge von [mm] $(V(G)\backslash [/mm] M)$ in [mm] $\mathcal{F}$ [/mm] liegt, oder? Und dann ist auch die letzte zu zeigende Eigenschaft klar. Aber wenn ich jetzt in obigem Beispiel als Menge B nehmen: [mm] B=\{1,2,3,4,5\}, [/mm] und als Menge A: [mm] A=\{6\}, [/mm] dann bleibt als Matching für B ja nur [mm] \{0,6\} [/mm] übrig (also das ist dann das kardinalitätsmaximale, das begründet, warum [mm] $B\in\mathcal{F}$ [/mm] gilt), für A muss ich aber ein anderes nehmen. Warum ist denn dann allgemein klar, dass ich ein beliebiges Element aus B zu A hinzutun kann, und immer noch in [mm] $\mathcal{F}$ [/mm] bleibe? Für das konkrete Beispiel hier ist das klar. Aber ein Beispiel reicht wohl kaum als Beweis und ich glaube schon, dass ich das noch irgendwie zeigen müsste... Hättest du da vielleicht einen Ansatz?
> Eure Definition ist zu dieser, die ich gefunden hab
> äquivalent.
Ja, das dachte ich mir schon.
> Ein primales Matroid ist einfach ein Ausdruck, den ich
> erfunden hab, um den dem dualen Matroid zugrundeliegenden
> Matroid zu bezeichnen, das ursprüngliche Matroid also. Wie
> primales und duales Programm (was schon richtige Begriffe
> sind) :)
Ach so.
Aber kann es sein, dass du dich vertan hast, als du geschrieben hast:
> Das sind also in deinem Fall die Mengen aus dem primalen Matroid, die maximale Kardinalität haben, also Basen sind.
Nach meiner Definition gehören ja zu [mm] $\mathcal{F}^{\star}$ [/mm] genau die Mengen, deren Schnitt mit einer Basis leer ist. Meiner Meinung nach wären das dann gerade alle Knoten eines maximalen Matchings, denn die Knoten, die im Matching liegen, liegen ja nicht im Matroid. Und Basen sind doch gerade die Komplemente der Matchings, oder?
Hoffe ich bin nicht gerade zu blöd...
Wäre super, wenn du nochmal antworten könntest. Aber wenn nicht, wäre es auch schön, wenn du mir das schreiben könntest, dann brauche ich nicht auf eine Antwort zu warten.
Viele lustige Grüße aus der Villa Kunterbunt
wünscht
Pippilotta
|
|
|
| |
|
Hallo nochmal!
> Nein - denn ich will doch gar nicht zeigen, dass
> [mm]B\backslash A\in\mathcal{F}[/mm] ist, sondern dass es ein [mm]x\in B\backslash A[/mm]
> gibt, so dass [mm]A\cup\{x\}\in\mathcal{F}[/mm]. Aber ich sehe
> gerade meinen Fehler bei meinem angeblichen Gegenbeispiel
> von vorhin, ich dachte nämlich, dass es für alle solche x
> gelten muss...
>
> Hab' mir jetzt überlegt, dass für ein festes
> kardinalitätsmaximales Matching M doch auf jeden Fall die
> Potenzmenge von [mm](V(G)\backslash M)[/mm] in [mm]\mathcal{F}[/mm] liegt,
> oder? Und dann ist auch die letzte zu zeigende Eigenschaft
> klar. Aber wenn ich jetzt in obigem Beispiel als Menge B
> nehmen: [mm]B=\{1,2,3,4,5\},[/mm] und als Menge A: [mm]A=\{6\},[/mm] dann
> bleibt als Matching für B ja nur [mm]\{0,6\}[/mm] übrig (also das
> ist dann das kardinalitätsmaximale, das begründet, warum
> [mm]B\in\mathcal{F}[/mm] gilt), für A muss ich aber ein anderes
> nehmen. Warum ist denn dann allgemein klar, dass ich ein
> beliebiges Element aus B zu A hinzutun kann, und immer noch
> in [mm]\mathcal{F}[/mm] bleibe? Für das konkrete Beispiel hier ist
> das klar. Aber ein Beispiel reicht wohl kaum als Beweis und
> ich glaube schon, dass ich das noch irgendwie zeigen
> müsste... Hättest du da vielleicht einen Ansatz?
Kann man das vielleicht so machen:
Es gilt: [mm] $|Y|<|X|\le|V(G)|-\nu(G)$ [/mm] (mit [mm] \nu(G)= [/mm] "maximale Matchingzahl"), also [mm] $|Y|+\nu(G)<|V(G)|$. [/mm] Da jeder Knoten entweder im maximalen Matching oder einem Element von [mm] $\mathcal{F}$ [/mm] ist, muss es also aus Kardinalitätsgründen ein Element geben, so dass die dritte Eigenschaft erfüllt wird. Sonst bliebe ein Knoten übrig.
Bin mir aber nicht sicher, ob das nicht vielleicht totaler Blödsinn ist...
Viele lustige Grüße nochmal
wünscht
Pippilotta
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:26 Mo 25.06.2007 | | Autor: | opossum |
Hallo,
> Kann man das vielleicht so machen:
>
> Es gilt: [mm]|Y|<|X|\le|V(G)|-\nu(G)[/mm] (mit [mm]\nu(G)=[/mm] "maximale
> Matchingzahl"), also [mm]|Y|+\nu(G)<|V(G)|[/mm]. Da jeder Knoten
> entweder im maximalen Matching oder einem Element von
> [mm]\mathcal{F}[/mm] ist, muss es also aus Kardinalitätsgründen ein
> Element geben, so dass die dritte Eigenschaft erfüllt wird.
> Sonst bliebe ein Knoten übrig.
Nein, das geht so nicht, aus Kardinalitätsgründen muss es so ein Element geben, aber dass das Elemnet aus X ist wie für die Matroideigenschaft verlangt ist damit nicht sichergestellt.
Viele Grüße
>
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 01:20 Di 26.06.2007 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
![[willkommenmr]](/images/smileys/willkommenmr.png "[willkommenmr]")
![[keineahnung]](/images/smileys/keineahnung.gif "[keineahnung]"){kind=small}
. Daher kann ich z.B. keine Antwort geben, auch wenn ich es gerne würde, sorry.
![[kleeblatt]](/images/smileys/kleeblatt.gif "[kleeblatt]"){kind=small}
