Sind folgende Mengen Matroide?

Question

Guten Tag zusammen

Ich habe hier eine Aufgabe:

Ein Paar (M, U) bestehend aus einer Menge M und einem hereditären Mengensystem U
heisst ein Matroid, wenn die folgende Bedingung erfüllt ist:

Für alle Mengen A,B aus U mit |A| < |B| gilt, dass ein Element x ∈ B − A existiert, so dass die Menge A ∪ {x} ebenfalls in U liegt.

Eine Menge A ∈ U heisst unabhängig, eine Teilmenge von M, die nicht in U liegt heisst
abhängig.

Sei M := {1, 2, 3, 4, 5}. Entscheiden Sie für die folgenden Paare ( M, U_i), i = 1, 2, 3, 4, 5, ob
sie Matroide sind:

b) U2 = {∅, {1}, {3}, {1, 3}, {4}, {5}, {4, 5}, {2}},

Das wäre meine Antwort kein Matroide, da man die Menge {2} nicht A ∪ {x} nachbilden kann.

c) U3 = {∅, {1, 2}, {3}, {1, 3}, {4}, {5}, {4, 5}, {2}},

Da wäre meine Antwort Matroide, da man die Menge {2}  benötigt um die Menge {1,2} zu bilden.

Stimmen hier meine Annahmen? Für was gibt mein Lehrer die blaue Bemerkung in dieser Aufgabe an?

Vielen Dank im Voraus!

MfG
Lenovo

Answer 1

Hallo

\(U\subseteq P(M)\) ist hier zunächst eine Menge von ausgewählten (Teil)-Mengen von \(M\). Zusammen ergibt das nun ein Mengensystem. Das Paar \((M, U)\) nennt man Unabhängigkeitssystem, falls gilt:

1.) \(\emptyset\in U\)

2.) Aus \(J\in U\) mit \(I\subseteq J\) (beliebig) folgt \(I\in U\).

Dann sagt man, dass jedes Element aus \(U\) unabhängig genannt wird und jedes Element aus \(P(M)\setminus U\) nicht unabhängig, also abhängig.

Nun zu den Aufgaben:

Damit man überhaupt von Matroiden sprechen kann, muss vorher bekannt sein, dass ein Unabhängigkeitssystem vorliegt.

Zu b). Richtig, es ist kein Matroid, da eben das Matroidaxiom verletzt ist. Gib dafür ein konkretes Beispiel an: Für \(\{2\},\{4,5\}\in U_2\) ist \(|\{2\}|<|\{4,5\}|\) und \(\{4,5\}\setminus \{2\}=\{4,5\}\),aber es gilt dann \(\{2\}\cup \{4\}=\{2,4\}\notin U_2\) und \(\{2\}\cup \{5\}=\{2,5\}\notin U_2\)

Zu c). Ist kein Matroid. Suche dafür wie in b) ein Gegenbeispiel, was das Matroidaxiom verletzt.

Comments

hallo97

Danke vielmals für die Erklärung.

Nur dass ich dies richtig mache, hier ein kleines Beispiel zu c):

A = {2}

B = {1, 3}

Ist in dieser Aufgabe "x ∈ B − A" als Komplement gemeint? Habe ich beim Lösen der Aufgabe diese Bedingung nicht beachtet?

{2} ∪ {3} = {2,3} ∉U₃

und

{2} ∪ {1} = {1,2} ∈ U3

Hier ist U₃ kein Matroide, da {2,3} nicht in der Teilmenge drinnen ist oder?

Vielen Dank!

MfG
Lenovo

---

Ist in dieser Aufgabe "x ∈ B − A" als Komplement gemeint?

Nein, sondern die Differenz von B und A, also \(B\setminus A\) oder geschrieben als \(B-A\).

Für alle Mengen A,B aus U mit |A| < |B| gilt, dass ein Element x ∈ B − A existiert, so dass die Menge A ∪ {x} ebenfalls in U liegt.

Du musst bei solchen Aussagen immer genau hinschauen. Das dick gedruckte fordert die Existenz von mindestens ein solchem Element. Und das ist bei deinem Beispiel der Fall:

Betrache mit \(\{2\},\{1,3\}\in U_3\) jetzt \(\{1,3\}\setminus \{2\}=\{1,3\}\). Nun zu der Aussage: Hier erfüllt \(1\in \{1,3\}\setminus \{2\}=\{1,3\}\) die Eigenschaft \(\{1\}\cup \{2\}=\{1,2\}\in U_3\). Damit existiert hier also mindestens ein Element \(x\in \{1,3\}\setminus \{2\}\), nämlich \(x=1\), sodass \(\{x\}\cup \{2\}\in U_3\) gilt.

Um nun aber zu zeigen, dass die Aussage:

,,Für alle Mengen A,B aus U mit |A| < |B| gilt, dass ein Element x ∈ B − A existiert, so dass die Menge A ∪ {x} ebenfalls in U liegt."

bei \(U_3\) nicht zutrifft, musst du eben die Verneinung da von betrachten und diese dann zeigen:

,,Es gibt Mengen A,B aus U mit |A| < |B|, sodass für alle Elemente x ∈ B − A gilt, dass die Menge A ∪ {x} nicht in U liegt."

Und dafür kannst du mal diese Mengen hier betrachten:

\(\{2\}, \{4,5\}\in U_3\).

---

hallo97

Ahh, danke vielmals. Dann habe ich das falsch verstanden. Ich habe verstanden, dass beide Kombinationen vorkommen müssen (also {2,3} und {1,2}). Aber dann muss nur eine vorkommen.

Beim Beispiel von Ihnen:

{2},{4,5}∈U3.

Hier ist natürlich keine Kombination vorhanden:

{2} ∪ {4} = {2,4} ∉U3

und

{2} ∪ {5} = {2,5} ∉U3

---

{2} ∪ {2} = {2,4} ∉U3

Tippfehler ;) Aber, offenbar hast du das Prinzip hier verstanden. :-)