Parkettierung der 2-dim. Ebene mit Dominos

16.05.2009, 20:53

aRo

Parkettierung der 2-dim. Ebene mit Dominos

Hi!

Hier die Aufgabe:

Zitat:

Ein Dominosystem besteht aus einer endlichen Menge von quadratischen Dominos gleicher Größe, deren vier Kanten gefärbt sind. EIne Parkettierung der Ebene ist eine vollständige Überdeckung mit Dominosteinen, ohne Lücken und Überlappungen, so dass aneinandergrenzende Kanten dieselbe Farbe haben (Rotation der Steine ist nicht erlaubt)

1) Konstruieren Sie zu einem gegebenen Dominosystem D eine Formelmenge $\begin{eqnarray*} \Phi(D) \end{eqnarray*}$ , welche genau dann erfüllbar ist, wenn eine Parkettierung von $\begin{eqnarray*} \mathbb Z \times \mathbb Z \end{eqnarray*}$ existiert.

2) Sei D ein Dominosystem. Zeige, dass man mit D auch die gesamte Ebene ZxZ parkettieren kann, wenn man mit D beliebig große endliche Quadrate nxn parkettieren kann.

2) denke kriege ich hin. Das müsste mit dem Lemma von König gehen, das können wir ja nochmal durchgehen, wenn wir die 1) geschafft haben.

Also zur 1)

Man muss ja irgendwie Variablen einführen, die beschreiben, ob man die Dominos aneinander legen kann, oder eben nicht.
Ich würde vielleicht sowas hier vorschlagen:
Man nummeriere die (endlichen) Dominos von 1..n durch.
Dann ist $\begin{eqnarray*} X_{i,j} = 1 \end{eqnarray*}$ wenn Stein i oben und Stein j unten dieselbe Farbe haben.
Und $\begin{eqnarray*} Y_{i,j} = 1 \end{eqnarray*}$ wenn Stein i rechts und Stein j links dieselbe Farbe haben.

So, braucht man noch mehr?
Wie geh ich da am besten ran? Stelle ich mir einfach ein Koordinatensystem vor in dem ich anfangs in jeden Quadranten einen passenden Domino lege und breite mich dann in "Ringen" immer weiter nach außen aus? Dann muss jeder Domino, den ich anlege, an max. 2 Seiten passen.

Könnt ihr mir vielleicht mal zeigen, wie ihr da ran gehen würdet?

19.05.2009, 21:08

Eshmael

Auf diesen Beitrag antworten »

Hey.. hier fremdfragen... du hast ja kein Vertrauen in mich... *hust* =)

Neue Frage »

Antworten »

Parkettierung der 2-dim. Ebene mit Dominos

Verwandte Themen