Schwarz - Weiss

Jester

MamboKurt schrieb:

tip: eine Linie teilt ein Rechteck (oder auch ein polyerder) in _2_ Teile (du hast auch _2_farben).

Das reicht aber nicht wirklich aus. Es ist klar, daß er ggf. umfärben muß. Er muß aber zeigen, daß das konsistent geht, sich also alles so umfärben läßt, daß das gesamte Rechteck wieder korrekt gefärbt ist. Dafür muß man schon ein paar Argumente mehr ankarren.

MamboKurt

deswegen steht da auch "tip" und nicht "lösung"

doppelmuffe

hi,

unterscheide mal die fälle
(a) die neu hinzugekommene linie liegt auf einer alten
und
(b) sie tut es nicht.

(ok, ich glaube, der tipp ist zu schwach...)

Ist noch simpel.
Das ist etwas schwieriger:
http://i11www.iti.uni-karlsruhe.de/members/mecke/publications/files/4Color.pdf

Naja, eure Hausaufgaben werde ich mal nicht machen:

Buzzwords:
- Domainen als Knoten
- Befriedigung von Constraint-Graphen
- Eigenschaften von binären Constraint-Netzwerken
- Arc-Consistency

das problem hier ist einfacher, es handelt sich nicht um beliebige graphen. wenn man das ganze als ein graphenproblem auffassen möchte, ergibt sich durch die konstruktionsvorlage nämlich die interessante eigenschaft, dass die inneren knoten alle eine gerade anzahl an kanten besitzen.

Prof84@home schrieb:

Das ist etwas schwieriger:
http://i11www.iti.uni-karlsruhe.de/members/mecke/publications/files/4Color.pdf

Du Held! Mit 4 Farben ausmalen ist doch viel leichter, als mit 2 !

Jester

Dafür darfste bei den 4 Farben aber nicht nur mit geraden Linien unterteilen, sondern ganz beliebig.
Dann isses ein bißchen schwieriger.

thordk

najo, also im grunde steht da nur "linie", nichts von gerade. könnte also ebenso was gebogenes sein sollte nicht eindeutig "gerade" gemeint sein, ist die lösung sehr einfach: unmöglich.

Dravere

Bitte noch um ein wenig mehr Hilfe. Wo ich stehe ist immer noch so gut wie bei null. Vor allem habe ich auch das Problem das ganze zu erfassen, also was ich eigentlich verwenden muss im Beweis.

Also ich kann ja zum Beispiel sagen, dass wenn ich n = 1 nehme, dass ich dann die zwei Flächen korrekt einfärben kann. Wie kann ich nun beweisen, dass dies auch für n+1 gilt?
Ich habe dann ja zum Beispiel 4 oder 3 Flächen. Die kann man genau aufteilen mit schwarz und weiss. Allerdings bringt mir das so nichts, denn die Flächen müssen ja noch entsprechen korrekt zueinander stehen. Was irgendwie durch die Geraden gegeben ist, also das nicht irgendwo am Rande ein Dreieck liegen kann. Zudem weiss ich auch, dass an einem weissen Polygon es an allen Kanten schwarze Polygone hat und bei den schwarzen Polygonen ist es umgekehrt.

Wäre also wirklich sehr dankbar um weiter Hilfe. Wieso nicht sogar gleich die Lösung? ^^
Will das nun endlich verstehen!

Grüssli

CStoll

OK, du hast ein durch n Geraden zerlegtes Rechteck korrekt eingefärbt (IV) und nimmst nun die Gerade g_n+1 dazu. Dann ist klar, daß du einige Flächen umfärben mußt (weil die durch n+1 zerschnittenen Flächen sich in zwei neue zerteilt haben) - also invertieren wir alle Flächen links von der Gerade^*.

Wenn wir uns jetzt zwei benachbarte Flächen a und b ansehen, gibt es zu ihrer Lage bezüglich g_n+1 drei mögliche Fälle:

a und b liegen beide rechts von g
a und b liegen beide links von g
g ist die gemeinsame Kante von a und b

Was kannst du in jedem Fall über die Farben von a und b aussagen? (du hast die IV und in Fall 3 auch die Vorraussetzung, daß a und b aus einer einzigen Fläche entstanden sind)

^(*) "links" ist recht willkürlich gewählt Wichtig ist, daß g das Rechteck in zwei Teile zerlegt - und die nenne ich mal "links" und "rechts".

Dravere

Hey danke CStoll. Ich glaub ich habe es nun kapiert und habe was niedergeschrieben und werde es morgen, bzw. heute abgeben. Ob es dann stimmt, werde ich erst am Montag sehen. Aber dein "Tipp" hat mich extrem auf die Sprünge geholfen und ich denke eigentlich wirklich, dass ich es begriffen habe, wie es denn nun geht ^^

Vielen Dank für die ganzen Mühen!

Grüssli