Ngjyrosja e Grafikut McGregor

Original Source: http://www.cs.cmu.edu/~bryant/boolean/macgregor.html

Në çështjen e shkencëtarëve amerikanë, Martin Gardner, në shtator të vitit 1975, në kolonën e tij “Mathematical Games” publikoi një listë të asaj që pretendonte se ishin 6 zbulime të mëdha matematikore të vitit 1974, të cilat “për një arsye ose një tjetër u raportuan në mënyrë joadekuate si për komunitetin shkencor, publiku në përgjithësi. “Njëri ishte një grafik i planifikuar me 110 nyje, i atribuar William McGregor nga Wappingers Falls, Nju Jork, që ai pohoi nuk mund të ngjyrohej me më pak se 5 ngjyra, duke mohuar supozimin e paprovuar që 4 ngjyrat ishin të mjaftueshme për të ngjyrosur çdo grafik planor. Ajo që shumë lexues nuk e vlerësuan ishte muaji i botimit të çështjes. Më shumë për historinë mund të gjeni këtu.Këtu është grafiku, i hartuar si një hartë:

Përpjekja për të koduar ngjyrimin e mundshëm të këtij grafiku si BDD nuk është me të vërtetë e realizueshme. Unë vlerësoj se do të merrte më shumë se një miliard nyje (meqë një minutë e prerë e grafikut ka 20 nyje të gjera dhe BDD do të duhet të kodojë në mënyrë eksponenciale pothuajse të gjitha kombinimet e ngjyrave për këto nyje).

Ngjyrosja e Grafikut si një problem SAT

Nga ana tjetër, ngjyrosja e grafikut me një zgjidhje të Boolean satisfiability (SAT) është mjaft e mundshme. Zgjidhja duhet të gjejë vetëm një zgjidhje të mundshme, kështu që nuk përballet me detyrën e frikshme të kodimit të të gjitha ngjyrave të mundshme. Këtu është një ngjyrosje e gjeneruar nga zgjidhësi ZChaff që konkurron nën një sekondë në një kompjuter portativ

Shikoni videon e mëposhtme të Youtube-it që tregon se si vazhdon ky kërkim:

Është gjithashtu e mundur të detyrohet zgjidhësi të krijojë një ngjyrosje “të ekuilibruar”, duke kërkuar që të gjejë një zgjidhje duke përdorur dy ngjyra (jeshile dhe blu) 27 herë dhe dy ngjyra (të kuqe dhe të verdhë) 28 herë.

SAT solvers mund gjithashtu të përdoret për të zgjidhur problemet e optimizimit, duke kryer një seri thirrjesh tek zgjidhësit për të bërë kërkime binare në funksionin objektiv. Nëse kërkojmë zgjidhjen për të gjetur një ngjyrosje që së pari minimizon numrin e nyjeve me ngjyrë të gjelbër, pastaj minimizon numrin me ngjyrë blu dhe pastaj të kuqe, marrim një ngjyrosje me vetëm 7 nyje të gjelbra, 34 blu dhe të kuqe dhe 35 të verdhë.

Bazuar në eksperimente të mëtejshme, mund të themi se, deri në caktimin e ngjyrave, kjo zgjidhje ka vetitë unike:

  • Është ngjyrosja e vetme ku një ngjyrë përdoret më së shumti 7 herë.
  • Është ngjyrosja e vetme ku një ngjyrë përdoret të paktën 35 herë.