0 Daumen
398 Aufrufe

f.PNG

auf dem Bild ist die Aufgabe auf jeden Fall klarer.

könnt jemand bitte damit helfen es geht hier um wadldartiges Clutter.

es wäre sehr nett wenn jemand da hilft da ich seit lange am denken bin aber ich komme immer noch nicht auf die Lösung .

Sei X eine endliche Menge und F ⊆ P(X) ein Clutter.

Wir nennen F einfach, falls für alle A, B ∈ F mit A 6= B gilt |A ∩ B| ≤ 1 und |A| ≥ 2. Weiter heißt F
waldartig, falls für jede Teilfamilie W ⊆ F ein A ∈ W und ein Element a ∈ A existiert, sodass für alle
B ∈ W mit B 6= A gilt: Wenn A ∩ B 6= ∅, dann A ∩ B = {a}.
Sei C ⊆ P(X) eine beliebige Menge von Teilmengen von X. Eine echte 2-Färbung von C ist eine Abbildung
f : X → {rot, blau}, sodass für alle A ∈ C gilt A ∩ f
−1({rot}) 6= ∅ und A ∩ f−1({blau}) 6= ∅.
(i) Sei G ein zusammenhängender Graph mit mindestens 2 Knoten. Wir definieren die folgende Menge:
B(G) := {V (B) | B ⊆ G und B ist ein Block von G} ⊆ P(V (G))
Beweisen Sie: B(G) ist ein einfaches und waldartiges Clutter.
(ii) Zeigen Sie, dass für jedes einfache und waldartige Clutter F ⊆ P(X) eine echte 2-Färbung existiert

von

Bitte logge dich ein oder registriere dich, um die Frage zu beantworten.

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage sofort und kostenfrei

x
Made by a lovely community
...