Dolog

Színezés a McGregor Graph

Az április, 1975 számában Scientific American, Martin Gardner, az ő oszlopban “Matematikai játékok” közzétett egy listát, amit igénylik, 6 fő matematikai felfedezései 1974 “az egyik vagy másik ok miatt nem megfelelően jelentettek mind a tudományos közösség és a nagyközönség. ” Az egyik egy sík, 110-csomópont gráf tulajdonított William McGregor a Wappingers Falls, New York, hogy azt állította, nem színezett kevesebb, mint 5 szín, ezáltal megcáfolva a még nem bizonyított sejtés, hogy 4 szín elegendő volt színezni bármilyen síkbeli gráf. Milyen sok olvasó nem értékelik volt a kiadás hónapja a kérdés. További információk a történet itt található.

Itt látható a grafikon és rajzolt egy térképet

Próbálok kódolni lehetséges színezésére ez a grafikon a BDD nem igazán lehetséges. Úgy vélem, telne több mint egymilliárd csomópontok (mivel a min-vágott a grafikon 20 csomópontok széles, és a BDD kellene exponenciálisan kódolni szinte minden kombinációja a színek ezek a csomópontok.)

Gráfszínezést a SAT probléma

Másrészt, színezés a grafikon egy logikai SAT (SAT) megoldó nagyon megvalósítható. A megoldó elegendő talál egy lehetséges megoldás, és ez így nem szembesülnek az ijesztő feladattal kódoló összes lehetséges színezékeket. Itt van egy színezés által generált ZChaff megoldó futó alatt egy második egy olyan hordozható számítógépet

Nézze meg az alábbi Youtube videó bemutatja, hogyan ez a keresés bevétel:

Az is lehetséges, hogy a hatályos megoldó, hogy létrehoz egy “kiegyensúlyozott” színezés, mivel megköveteli, hogy megoldást találjanak a két színben (zöld és kék) 27-szer, és két színben (piros és sárga) 28-szor.

SAT megoldó is fel lehet használni, hogy megoldja optimalizálási problémák, elvégzésével egy sor hívásokat a megoldók tenni bináris keresés a célfüggvényt. Ha megkérjük a megoldó, hogy megtalálja a színezés, hogy az első minimalizálja a csomópontok száma zöld színű, akkor a legkevesebb számú kék színű, majd piros, kapunk egy színű, mindössze 7 zöld csomópont, 34 kék és piros is, és 35 sárga.

Ennek alapján a további kísérletek, azt mondhatjuk, hogy akár a feladat a színek, ez a megoldás egyedi tulajdonságokkal rendelkezik:

Ez az egyetlen színezés, ahol az egyik szín alkalmazunk legfeljebb 7-szer.
Ez az egyetlen színezés, ahol az egyik szín használunk legalább 35 alkalommal.

Eredetileg a http://www.cs.cmu.edu/~bryant/boolean/macgregor.html. Menj a honlapon http://www.forallworld.com