Characterizations of Matroids

amittelbach
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 1. Feb 2007 20:07

Characterizations of Matroids

Beitrag von amittelbach »

Hallo,

ich habe ein Problem beim Verständnis von (M3'') (Folie 324). Soweit ich die Definition von Basen richtig verstanden habe, würde ich behaupten, Basen müssen unabhängige Mengen sein. Jedoch gilt nicht für jedes \(X \subseteq E\), dass X unabhängig ist. Müsste die Forderung dann nicht vielmehr heißen \(X \in \mathcal{F}\)?

Grüße
Arno

Benutzeravatar
Matthias Müller-Hannemann
Dozentin/Dozent
Beiträge: 59
Registriert: 13. Okt 2005 17:09

Beitrag von Matthias Müller-Hannemann »

Hallo,

Basen sind in der Tat die nicht-erweiterbaren unabhängigen Mengen. Ferner haben Sie völlig recht damit, dass \( X \subseteq E\) durchaus abhängig sein kann.

(M3'') fordert nun, dass für jede Menge \( X \subseteq E\) gilt, dass die in X enthaltenen Basen die gleiche Kardinalität besitzen.

Das ist also eine stärkere Forderung, als anzunehmen, dass alle Basen der Grundmenge E gleiche Kardinalität besitzen sollen.

Die Äquivalenz zu den anderen Axiomen (M3) bzw. (M3'') zeigt, dass die Formulierung (M3'') sinnvoll ist.

Mit besten Grüßen,
Matthias Müller-Hannemann
Dr. Matthias Müller-Hannemann
muellerh AT algo.informatik.tu-darmstadt.de

TU Darmstadt
Department of Computer Science
Algorithmics Group
Hochschulstr. 10
64289 Darmstadt

phone: +49-6151-16-3358
http://www.algo.informatik.tu-darmstadt.de/

Benutzeravatar
Omen
BASIC-Programmierer
BASIC-Programmierer
Beiträge: 116
Registriert: 6. Nov 2004 21:04

Beitrag von Omen »

Im Skript seite315 steht folgendes:

The elements of F are called independent,
the elements of 2E \ F dependent.
Maximal independent sets (= no superset is independent) are
called bases.

Bedeutet maximal, dass ein basis alle Eelemnte aus F enthalten muss?? Wenn ja was bedeutet dann, dass wir mehrere Basen haben?

Und in der Musterlösung der Aufgabe 29 hab ich ein Teil nicht verstanden.
Wir haben X ⊆ E in 2 Teile X1 und X2 zerlegt, wobei X1 = {e ∈ X | e = (s, v)} und X2 = X \ X1.
und jetzt wollen wir zeigen, dass X1 und X2 die gleiche Kardinalität haben.
Was danach kam in der Mulö. hab ich nicht gantz verstanden vielleicht kann man das mit anderen Worten besser erklären oder anhand eines
Beispiel veranschaulichen . :roll:

Danke im vorraus

Benutzeravatar
Matthias Müller-Hannemann
Dozentin/Dozent
Beiträge: 59
Registriert: 13. Okt 2005 17:09

Beitrag von Matthias Müller-Hannemann »

Omen hat geschrieben:Im Skript seite315 steht folgendes:

The elements of F are called independent,
the elements of 2E \ F dependent.
Maximal independent sets (= no superset is independent) are
called bases.

Bedeutet maximal, dass ein basis alle Eelemnte aus F enthalten muss?? Wenn ja was bedeutet dann, dass wir mehrere Basen haben?
Nein!
Eine unabhängige Menge F heißt maximal unabhängig, wenn ich kein Element e der Grundmenge hinzufügen kann, so dass die Menge F erweitert um e immer noch unabhängig ist.

Eine Teilmenge X der Grundmenge E kann sehr viele Basen haben (im graphischen Matroid ist jeder Spannbaum eine Basis) und die Basen können unterschiedliche Kardinalität haben (siehe Kardinalitätsmatching, Aufgabe 30).
Omen hat geschrieben: Und in der Musterlösung der Aufgabe 29 hab ich ein Teil nicht verstanden.
Wir haben X ⊆ E in 2 Teile X1 und X2 zerlegt, wobei X1 = {e ∈ X | e = (s, v)} und X2 = X \ X1.
und jetzt wollen wir zeigen, dass X1 und X2 die gleiche Kardinalität haben.
Was danach kam in der Mulö. hab ich nicht gantz verstanden vielleicht kann man das mit anderen Worten besser erklären oder anhand eines
Beispiel veranschaulichen .
Nein, wir wollen nicht zeigen, dass X1 und X2 gleiche Kardinalität haben (denn das gilt im Allgemeinen sicherlich nicht).

Vielmehr müssen wir zwei beliebige Basen B1 und B2 in X betrachten und zeigen, dass diese gleiche Kardinalität haben. Dazu überlegen wir uns, dass sowohl B1 als auch B2 genau min{2, |X1|} Kanten aus X1 enthalten. Ferner enthalten B1 und B2 gleich viele Elemente aus X2, weil der Graph (V,X2) ein graphisches Matroid bildet (für Matroide wissen wir, dass alle Basen gleiche Kardinalität haben).

Beste Grüße,
Matthias Müller-Hannemann
Dr. Matthias Müller-Hannemann
muellerh AT algo.informatik.tu-darmstadt.de

TU Darmstadt
Department of Computer Science
Algorithmics Group
Hochschulstr. 10
64289 Darmstadt

phone: +49-6151-16-3358
http://www.algo.informatik.tu-darmstadt.de/

amittelbach
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 1. Feb 2007 20:07

Beitrag von amittelbach »

Eine unabhängige Menge F heißt maximal unabhängig, wenn ich kein Element e der Grundmenge hinzufügen kann, so dass die Menge F erweitert um e immer noch unabhängig ist.
Nehmen wir einmal an, wir haben eine Menge E:={a,b,c}. Sehe ich das nun richtig, dass die folgenden Mengen unabhängig sind, aber keine Basis?
F1:={leer,a}
F2:={leer,a,b}
F3:={leer,a,b,{a,b}}

und die folgende eine Basis:
F4:={leer,a,b,c}

Was ist aber nun hiermit?
F5:={leer,a,b,c,{a,b}}
Diese Menge ist mit Sicherheit unabhängig und ich würde behaupten ich kann kein Element aus E hinzufügen, da F5 vereinigt E = F5. Ist dies nun eine Basis? Denn dann wäre ja jede Menge der From {leer,a,b,c,...} eine Basis.

Benutzeravatar
SM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 167
Registriert: 10. Okt 2005 18:11
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von SM »

Wenn F5 unabhängig ist, kann F4 keine Basis sein.

Siehe Folie 315. Maximale unabhängige Mengen sind dann Basen. Und eine Menge ist maximal unabhängig, wenn es keine unabhängige Übermenge gibt.

Da F4 aber Teilmenge von F5 ist, ist entweder F5 abhängig oder F4 keine Basis.
~ Per aspera ad astra. ~

amittelbach
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 1. Feb 2007 20:07

Beitrag von amittelbach »

aber es heißt doch, siehe Zitat von Herr Müller-Hannemann, dass maximal unabhängige Mengen (Basen) dadurch charakterisiert werden, dass ich kein Element der Grundmenge (E) hinzufügen kann, ohne dass diese abhängig werden.

In meinem Beispiel war E:={a,b,c}. Das heißt der Menge F4:={leer,a,b,c} kann ich kein Element der Grundmenge mehr hinzufügen, da diese schon alle Elemente der Grundmenge enthält. Aussagen über das hinzufügen von Elementen der Potenzmenge \(2^E\) werden hierbei gar nicht gemacht. Daraus schließe ich, dass ich einer Basis sehr wohl noch Elemente der Potenzmenge hinzufügen kann ohne die Basisbedingung zu verletzen, es sei denn diese Elemente sind Element der Grundmenge.

Da {a,b} nun nur Element der Potenzmenge ist und nicht direkt Element der Grundmenge würde ich behaupten, dass ich F4 {a,b} hinzufügen darf und immer noch eine Basis habe (da wie gesagt, keine Elemente der Grundmenge mehr hinzugefügt werden können).

Benutzeravatar
SM
Endlosschleifenbastler
Endlosschleifenbastler
Beiträge: 167
Registriert: 10. Okt 2005 18:11
Wohnort: Darmstadt
Kontaktdaten:

Beitrag von SM »

Die Elemente in schön-F sind keine Potenzmengen von E sondern nur Teilmengen von E (weil schön-F eine Teilmenge der Potenzmenge von E ist).

Und eben diese Elemente von schön-F, sprich: die Teilmengen von E, sind das X und Y im Script - und nur diese sind auch Basen.

Folglich kannst Du zu X (das sind hier Deine F1-F4) keine Elemente der Potenzmenge von E hinzufügen.

Alle Angaben ohne Gewähr. ;)
~ Per aspera ad astra. ~

amittelbach
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 1. Feb 2007 20:07

Beitrag von amittelbach »

Moment, so langsam glaube ich widerspreche ich mir selber.

Die Menge F des Unabhängigkeitssystems (E,F) besteht aus Elementen der Potenzmenge von E. Dementsprechend kann ein Element \(x \in F\) in meinem
Beispiel mit E:={a,b,c} nie {leer,a,b,{a,b}} sein, da weder die Menge {leer,a,...} noch die Menge {...,{a,b}} Element der Potenzmenge sind. Da x nicht in F sein kann, somit nicht unabhängig ist, ist es erst recht keine Basis.

Das würde bedeueten die einzige Basis über der Grundmenge E:={a,b,c} und F:=Potenzmenge von E wäre die Menge {a,b,c}.

Dieser kann ich keine Elemente der Menge E hinzufügen, da schon alle drinnen sind und auch sonst nichts hinzufügen, da sie sonst nicht mehr Element aus F wäre und somit abhängig (bzw. irgendwas komisches, da es noch nicht mal Element der Potenzmenge wäre).

Ich bin so langsam verwirrt, aber ich hoffe das stimmt jetzt.

amittelbach
Mausschubser
Mausschubser
Beiträge: 49
Registriert: 1. Feb 2007 20:07

Beitrag von amittelbach »

Die Elemente in schön-F sind keine Potenzmengen von E sondern nur Teilmengen von E (weil schön-F eine Teilmenge der Potenzmenge von E ist).
Danke .. ich glaube das wars, was ich mit meinem etwas längerem Geschriebenen habe ausdrücken wollen.

mjp
Neuling
Neuling
Beiträge: 7
Registriert: 16. Apr 2006 11:34

Beitrag von mjp »

Matthias Müller-Hannemann hat geschrieben: Basen sind in der Tat die nicht-erweiterbaren unabhängigen Mengen. Ferner haben Sie völlig recht damit, dass \( X \subseteq E\) durchaus abhängig sein kann.

(M3'') fordert nun, dass für jede Menge \( X \subseteq E\) gilt, dass die in X enthaltenen Basen die gleiche Kardinalität besitzen.

Das ist also eine stärkere Forderung, als anzunehmen, dass alle Basen der Grundmenge E gleiche Kardinalität besitzen sollen.
amittelbach hat geschrieben:Müsste die Forderung dann nicht vielmehr heißen \(X \in \mathcal{F}\)
Meinten Sie, daß \(X \in \mathcal{F}\) also restriktiver sei als \(X \subseteq E\) ?

Basen müssen ja per Definition maximal und unabhängig sein. Wieso führt der oben zitierte Vorschlag von amittelbbach \(X \in \mathcal{F}\) nicht zum gleichen Ergebnis?


Laut meinem Verständnis wäre es equivalent, da keine mögliche Basis außerhalb von \( \mathcal{F}\) vorkommen kann.

Benutzeravatar
Matthias Müller-Hannemann
Dozentin/Dozent
Beiträge: 59
Registriert: 13. Okt 2005 17:09

Beitrag von Matthias Müller-Hannemann »

mjp hat geschrieben:
Matthias Müller-Hannemann hat geschrieben: Basen sind in der Tat die nicht-erweiterbaren unabhängigen Mengen. Ferner haben Sie völlig recht damit, dass \( X \subseteq E\) durchaus abhängig sein kann.

(M3'') fordert nun, dass für jede Menge \( X \subseteq E\) gilt, dass die in X enthaltenen Basen die gleiche Kardinalität besitzen.

Das ist also eine stärkere Forderung, als anzunehmen, dass alle Basen der Grundmenge E gleiche Kardinalität besitzen sollen.
amittelbach hat geschrieben:Müsste die Forderung dann nicht vielmehr heißen \(X \in \mathcal{F}\)
Meinten Sie, daß \(X \in \mathcal{F}\) also restriktiver sei als \(X \subseteq E\) ?

Basen müssen ja per Definition maximal und unabhängig sein. Wieso führt der oben zitierte Vorschlag von amittelbbach \(X \in \mathcal{F}\) nicht zum gleichen Ergebnis?


Laut meinem Verständnis wäre es equivalent, da keine mögliche Basis außerhalb von \( \mathcal{F}\) vorkommen kann.
Wenn \(X \in \mathcal{F}\) ist, dann ist stets X selbst die eindeutige Basis in X. In der vorgeschlagenen Formulierung wäre das Axiom stets erfüllt. Es ist also weder Äquivalent zu (M3''), noch ist der Vorschlag sinnvoll.

Beste Grüße,
Matthias Müller-Hannemann
Dr. Matthias Müller-Hannemann
muellerh AT algo.informatik.tu-darmstadt.de

TU Darmstadt
Department of Computer Science
Algorithmics Group
Hochschulstr. 10
64289 Darmstadt

phone: +49-6151-16-3358
http://www.algo.informatik.tu-darmstadt.de/

Antworten

Zurück zu „Archiv“