Here you can ask questions and find or give answers to organizational, academic and other questions about studying computer science.

1.1k questions

1.2k answers

1.6k comments

531 users

0 votes

 

Kann jemand diese Aufgabe mir erklären? Da ich bekomme eine Falsche Lösung 

in # Mandatory Modules Bachelor by (120 points)

1 Answer

0 votes

Um die Landkarte mit drei Farben R,G,B einzufärben, verwenden wir Variablen R_i,G_i und B_i für i=0,1,2,3. Aufgrund der Nachbarschaften der Länder muss dabei Folgendes gelten, damit benachbarte Länder unterschiedliche Farben erhalten:

    (R0->!R1) & (G0->!G1) & (B0->!B1) &
    (R0->!R2) & (G0->!G2) & (B0->!B2) &
    (R1->!R2) & (G1->!G2) & (B1->!B2) &
    (R1->!R3) & (G1->!G3) & (B1->!B3) &
    (R2->!R3) & (G2->!G3) & (B2->!B3)

Ferner muss jedes Land eine Farbe bekommen:

    (R0 | G0 | B0) 
    (R1 | G1 | B1) &
    (R2 | G2 | B2) &
    (R3 | G3 | B3)

und jedes Land soll nicht mehr als eine Farbe bekommen:

    (R0 -> !G0 & !B0) & (G0 -> !R0 & !B0) & (B0 -> !R0 & !G0) &
    (R1 -> !G1 & !B1) & (G1 -> !R1 & !B1) & (B1 -> !R1 & !G1) &
    (R2 -> !G2 & !B2) & (G2 -> !R2 & !B2) & (B2 -> !R2 & !G2) &
    (R3 -> !G3 & !B3) & (G3 -> !R3 & !B3) & (B3 -> !R3 & !G3)

Wenn man alle diese Formeln zu einer Konjunktion zusammenfasst, dann entsprechen alle erfüllenden Belegungen den Färbungen der Landkarte. Zum Beispiel kann man einen BDD für diese Formeln bestimmen und daraus alle Färbungen ablesen. Man kann dafür auch andere Formulierungen finden, die zu den obigen Formeln äquivalent sind. 

Da die obigen Formeln viele Wiederholungen für alle Länder enthalten, wurde in der Aufgabe nur nach den Einschränkungen für ein Land gefragt, um die Schreibarbeit für alle Länder zu sparen.

by (166k points)

Related questions

+1 vote
1 answer
+1 vote
1 answer
asked Jul 4, 2020 in # Mandatory Modules Bachelor by nickjo (1.1k points)
0 votes
1 answer
0 votes
1 answer
asked Aug 14, 2020 in * Other Teaching Fields by mauric3 (190 points)
0 votes
1 answer
Imprint | Privacy Policy
...