0 Daumen
503 Aufrufe

Wir fixieren einen unendlichen Graphen (V, E): Dieser besteht aus einer (abzählbar) unendlichen Menge V von “Punkten”
und aus einer Menge E ⊆ {{x, y}| x, y ∈ V, x 6= y} von “Kanten” (die Punkte x und y sind “verbunden”, wenn {x, y} ∈ E
gilt). Der Graph (V, E) heißt k-färbbar, wenn es eine Funktion f : V → {1, . . . , k} gibt, sodass für alle x, y ∈ V gilt: Ist
{x, y} ∈ E so hat man f (x) 6= f ( y). Um die Situation in der Aussagenlogik zu beschreiben, führen wir Aussagenvariablen
pxi für x ∈ V und i = 1, . . . , k ein. Intuitiv besagt pxi, dass der Punkt x die i-te Farbe zugewiesen bekommt.
(a) Man gebe eine Formelmenge Φ mit der folgenden Eigenschaft an: Es gilt I Φ genau dann, wenn es für jedes x ∈ V
genau ein i ∈ {1, . . . , k} mit I(pxi) = 1 gibt.
(b) Man gebe eine Formelmenge Ψ an, welche genau dann erfüllbar ist, wenn (V, E) ein k-färbbarer Graph ist.
(c) Man verwende Kompaktheit, um die folgende Aussage zu beweisen: Wenn (V0
, {(x, y) ∈ E | x, y ∈ V0
}) für eine
beliebige endliche Teilmenge V0 ⊆ V ein k-färbbarer Graph ist, dann ist der ganze Graph (V, E) ebenfalls k-färbbar.Bildschirmfoto 2018-05-05 um 22.48.43.png

von

1 Antwort

0 Daumen

a) Sei

    φ≥1(x) = ∨i=1..k pxi und

    φ≤1(x, i) = pxi →∧j=1..k,j≠i ¬pxj.

φ≥1(x) sagt aus, dass Knoten x minestens eine Farbe bekommt.

φ≤1(x, i) sagt aus, dass wenn Knoten x die Farbe i bekommt, dass x dann keine andere Farbe bekommt.

Φ = ∪x∈V,i∈{1, ..., k}≥1(x), φ≤1(x, i)}.

b) Sei

    ψ(x, i) = pxi→∧{x,y}∈E ¬pyi.

ψ(x, i) sagt aus, wenn der Knoten x die Farbe i hat, dann hat kein benachbarter Knoten die Farbe i.

Ψ = ∪x∈V,i∈{1, ..., k} {ψ(x, i)} ∪ Φ.

von 76 k 🚀

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community