Blatt 1 Aufgabe 2

  • aja stimmt. hab ich vergessen danke! :)


    Wobei es gibt mehrere Arten wie man die Knoten einfärben kann, eben wie viele vershciedene zuweisungen es für die variablen gibt, die die formel true machen oder?

  • ich hab wieder ein gadget mit 6 knoten verwendet


    soweit ich das verstanden hab ist das weiterhin ein 3-sat problem, weil es gibt 4 klauseln mit je 3 literalen = 12 literale (in der angabe steht, dass es 6 variablen und deren negation gibt also insgesamt die 12 literale)

  • zu b) wie kommt ihr auf 73 Kanten? Ich habe 81 Kanten ausgerechnet.
    Hier meine Rechnung:
    Kanten zwischen den Literalen = 6
    Kanten der Literale zu B = 12
    Kanten der einzelnen Gadgets: 7 Kanten im Gadget + 3 Kanten zu den Literalen * 4 = 10 * 4 = 40
    Kanten von T zu den Gadgets: 4 pro Gadget = 4 * 4 = 16
    Kanten von F zu den Gadgets: 4
    Kanten zwischen T, F und B: 3
    Gesamt: 6 + 12 + 40 + 16 + 4 + 3 = 81

  • pro gadget hab ich: 13 kanten (5 im gadget, 3 zu den literalen, 4 zu T und 1 zu F)


    also insgesamt:
    FTB-Verbindung: 3
    12 Literale mit B: 12
    Verbindung mit Negation: 6
    4*Gadget: 13*4 = 52


    3+12+6+52=73

  • Vielleicht kann mir von euch jemand bei einer Verständnisfrage helfen: Warum haben wir innerhalb des Gadgets 7 Kanten und nicht 5?


    Wäre cool wenn das eine/r erklären könnte

  • Ich nehme an du meinst warum wir innerhalb des Gadgets 5 und nicht 7 Kanten haben


    Da du alle Literale mit B verbunden hast und die oberen 3 Knoten des Gadgets mit T kannst du die Bedingung nicht erfüllen, dass benachbarte Knoten unterschiedliche Farben haben.
    Wenn du dir alle möglichen Belegungen durchdenkst geht es sich nie aus, dass die Bedingung erfüllt wird, wenn die oberen Knoten des Gadgets miteinander verbunden sind.