Це український переклад * сторінки  http://www.cs.cmu.edu/~bryant/boolean/macgregor.html

 Автора

  Рэндала Э. Брайанта

 Засновника Університету

Почесного професора комп’ютерних наук

з великим досвідом в області електротехніки та обчислювальної техніки

Школа комп’ютерних наук

Університету Карнегі-Меллона

США

Оригінальна стаття

Розфарбовування графа МакГрегора

Рэндал Э. Брайант

У квітневому випуску журналу Scientific American за 1975 рік Мартін Гарднер у своїй колонці «Математичні ігри» опублікував перелік шести основних математичних відкриттів 1974 року народження, про які «з тієї чи іншої причини недостатньо повідомлялося як науковому спів-товариству, так і громадськості в цілому». Одним з них бaув планарний граф зі 110 вузлами, що приписується Вільяму МакГрегору з Ваппінгерс-Фоллс, штат Нью-Йорк, який, за його твердженнями, не можна розфарбувати менш ніж в 5 кольорів, тим самим спростовуючи поки ще не доведене припущення про те, що 4х кольорів досить для фарбування будь-якого планарного графа. Це не сподобалося багатьом читачам, ще місяць опісля публікації номеру. Детальніше про історію можна прочитати тут.

Ось графік, намальований у вигляді карти

Спроба закодувати можливе забарвлення цього графа як BDD практично нездійсненна. Я припускаю, що для цього буде потрібно більше одного мільярда вузлів (оскільки мінімальний розріз графа має ширину 20 вузлів, і BDD потрібно експоненціально кодувати майже всі комбінації кольорів для цих вузлів).

Розфарбування графіка як завдання SAT

З іншого боку, розфарбування графа за допомогою вирішувателя логічної здійсненності (SAT) цілком можлива. Вирішувачу потрібно знайти тільки одне можливе рішення, тому перед ним не стоїть складне завдання кодування всіх можливих розмальовок. Ось кольори, створені вирішувачем ZChaff, який пропрацював менше ніж одну секунду на портативному комп’ютері.

Подивіться наступне відео на Youtube, що показує, як просувається цей пошук: https://youtu.be/0gt503wK7AI

Також можна змусити вирішувач генерувати «збалансовану» розмальовку, зажадавши від нього знайти рішення, використовуючи два кольори (зелений і синій) 27 раз і два кольори (червоний і жовтий) 28 разів.

Вирішувачі SAT також можуть використовуватися для вирішення завдань оптимізації, виконуючи серію викликів вирішувачів для виконання довічного пошуку по цільовій функції.  Якщо ми попросимо вирішувальну програму знайти розмальовку, яка спочатку мінімізує кількість вузлів, забарвлених в зелений колір, а потім мінімізує число, забарвлене в синій колір, а потім в червоний, ми отримаємо розмальовку всього з 7 зелених вузлів, 34 синіх і червоних і 35 жовтих.

На підставі подальших експериментів можна констатувати, що до призначення кольорів це рішення має унікальні властивості:

  • Це єдине забарвлення, в якому один колір використовується не більше 7 разів.
  • Це єдине забарвлення, в якому один колір використовується не менше 35 разів.

 

Рендал Э. Брайант

Останнє поновлення: середа, 12 травня, 10:19:05 EDT 2010

 

© 2020. This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License

 

Цей документ є авторизованим перекладом документа Школи Комп’ютерних Наук Карнеги Мелон Университету (https://www.cs.cmu.edu/). 

Публікація цього переказу здійснюється відповідно до етапів, описаними в правилах підготовки авторизованих перекладів ( Policy for W3C Authorized Translations ). У всіх спірних випадках основною вважається оригінальна версія цього документа англійською мовою.

 

* Український уповноважений переклад

Публікація 29 жовтня 2020

Поточна версія:

https://thesisowl.com/2020-10-29-macgregor_tu1/

Остання версія:

https://thesisowl.com/2020-10-29-macgregor_tu2/

Оригінальна версія (англійською мовою):

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

Поточна версія:

https://thesisowl.com/2020-10-21-write-recommendation_1tu/

Остання версія:

https://thesisowl.com/2020-10-21-write-recommendation_2tu/

Оригінальна версія (англійською мовою):

https://homes.cs.washington.edu/~mernst/advice/write-recommendation.html

Організатор перекладу:

ThesisOwl,

Україна, Київ, 01014,

бул. Лесі Українки, 26, 3 поверх

Сайт: https://thesisowl.com

Редакторська правка перекладу

EuroWay

Україна, Київ, 03035, Солом’янська площа, 2, 6 поверх

Координатор перекладу

Девід Діаз (email: [email protected] )

Цей документ є авторизованим перекладом документа Товариства комп’ютерних наук та інженерії Вашингтонського університету (https://homes.cs.washington.edu/). Публікація цього переказу здійснюється відповідно до етапів, описаними в правилах підготовки авторизованих перекладів ( Policy for W3C Authorized Translations ). У всіх спірних випадках основною вважається оригінальна версія цього документа англійською мовою.

 

** Creative Commons

Ми публікуємо цей переклад і звуковий файл, що його відтворює для людей з проблемами зору, як похідні документи за ліцензією Creative Commons. Ви можете використовувати наші матеріали і розвивати роботу в некомерційних або комерційних цілях за умови, що ви виконаєте оригінальну публікацію і включіть зворотне посилання на thesisowl.com 

 (https://thesisowl.com/2020-10-21-write-recommendation_2t/).

Це офіційна ліцензія Creative Commons:

Attribution-ShareAlike 4.0 International (CC BY-SA 4.0)

 

Ви можете:

Share – копіювати і поширювати матеріал на будь-якому носії і будь-якому форматі.

Adapt – ремикшировать, перетворювати і доповнювати матеріал для будь-яких цілей, навіть в комерційних цілях.

На наступних умовах:

Attribution – ви повинні вказати відповідну позначку, надати посилання на ліцензію і вказати, чи були внесені зміни. Ви можете зробити це будь-яким розумним способом, але не будь-яким способом, який передбачає, що ліцензіар схвалює вас чи ваше використання.

ShareAlike – якщо ви зменшуєте, трансформуєте або доповнюєте матеріал, ви повинні поширювати свої матеріали з тією самою ліцензією, що і оригінал.

Деталі ліцензії:   https://creativecommons.org/licenses/by-sa/4.0/

 

ЯК пославшись на ЦЮ ПУБЛІКАЦІЮ (HOW TO CITE THIS PUBLICATION):

Якір (ancor) – ThesisOwl

URL – https://thesisowl.com/2020-10-21-write-recommendation_2t/