Alle maximalen unabhängigen Sätze des Matroids haben die gleiche Kardinalität

Question

Wie zu beweisen, dass alle maximalen unabhängigen Sätze des Matroid die gleiche Kardinalität haben.

einen Matroid Bereitgestellt wird eine 2-Tupel (M, J), wobei M eine endliche Menge ist, und J ist eine Familie von einigen der Teilmengen von M die folgenden Eigenschaften erfüllt:

1. Wenn A ist Teilmenge von B und B gehört zu J, dann gehört A zu J,
2. Wenn A, B zu J gehört, | A | < = | B |, und x gehört zu einem - B, dann existiert y zu B gehört, - A, so dass (BU {x}) - {y} zu J.

Die Mitglieder J gehört heißen unabhängige Sätze.

Answer 1

Angenommen, | A | < | B | und A ist nicht maximal unabhängig.

Betrachten Sie die folgende Venn-Diagramm

Offensichtlich B \ A (die nur blauen Teil) ist nicht leer, da die Kardinalität von B größer ist als die von A. Auch klar A \ B (der einzige orange Teil) nicht leer ist, da sonst A ⊂ B, und per definitionem A ist nicht maximal unabhängig.

daher durch den Austausch Eigenschaft gibt es einige x ∈ A \ B, y B ∈ \ A, so dass B ∪ {x} \ {y} ∈ J sowie. Nennen wir dieses Set C. Beachten Sie, dass, wenn wir würden zeichnen das Venn-Diagramm für Ein und C (jetzt der blaue Kreis ist C):

1. | B | = | C | (der blaue Kreis hat die gleiche Größe)

2. | (A \ {x}) \ C | < | A \ B | (der einzige orange Teil ist kleiner als zuvor)

Jetzt können wir das Argument A und C, und so weiter wiederholen. Beachten Sie jedoch, dass wir es nicht unbegrenzt wiederholen können, da angenommen wird, dass es sich um eine endliche Zahl handelt.Daher werden wir irgendwann zu dem Widerspruch kommen, dass die orange Menge vollständig in der blauen Menge enthalten ist, was wir vorher schon gesehen haben, ist unmöglich (das würde definitionsgemäß bedeuten, dass sie nicht maximal unabhängig ist).

Answer 2

Wir werden dies mit Proof by Contradiction tun. Nehmen wir an, dass alle maximalen unabhängigen Mengen eines Matroids nicht die gleiche Kardinalität haben. Daher müssen einige Mengen A und B so gesetzt werden, dass beide maximal unabhängig voneinander gesetzt sind. Ohne den Verlust der Allgemeinheit nehmen wir j A j < j B j, d. H. Die Kardinalität von A ist kleiner als die Kardinalität von B. Es seien jAj = P und jBj = Q, P < Q. Nun sei X 2 A-B und Y 2 B-A. X und Y existieren immer , da A maximal ist und von B verschieden ist. Unter Verwendung der zweiten Eigenschaft von Matroid können wir B1 = f B [X g - f y g machen, was auch eine unabhängige Menge und j B1 j = Q ist. Wir können weiterhin ein Element von X '2 A-Bi und ein Element von Y' 2 Bi-A auswählen und X 'einfügen und Y' entfernen, um einen neuen unabhängigen Satz mit der Kardinalität Q zu bilden, bis kein Element mehr vorhanden ist A-Bi. Da A-Bi = also A Bi. Aber Bi ist auch und unabhängig mit Kardinalität Q gesetzt. Jetzt können wir sagen, dass A nicht maximal ist, was ein Widerspruch ist und somit war unsere Annahme falsch. So j A j = j B j was bedeutet, dass es keine zwei maximal unabhängig sein kann mit verschiedenen Kardinalitäten gesetzt. So haben alle maximalen unabhängigen Sätze eines Matroids die gleiche Kardinalität.