0 Daumen
289 Aufrufe

Hi Leute,

kann jemand wir zeigen, wie man diese Aufgaben lösen kann, da ich ein Testat habe und muss mich vorbereiten.

Danke


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 ≠ 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) ≠ 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.

1.) 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

von

kann irgend jemand  bitte mir dabei helfen ?

Ein anderes Problem?

Stell deine Frage

Ähnliche Fragen

Willkommen bei der Mathelounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community