Прежде чем развивать менее тривиальный подход к поиску минимальных раскрасок, нам надо понять: а нужно ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Ершов А.П. Введение в теоретическое программирование беседы о методе


Прежде чем развивать менее тривиальный подход к поиску минимальных раскрасок, нам надо понять: а нужно ли рассматривать проблему в полной всеобщности. При всей увлеченности очередной интересной математической задачей надо помнить, что в контексте нашего исследования раскраска вершин графа нам нужна не сама по себе, а как средство экономного распределения памяти. Может быть, графы несовместимости, получающиеся для операторных схем, обладают какими-нибудь специальными свойствами, которые могли бы облегчить поиск минимальной раскраски. Например, известно, что любой плоский граф можно раскрасить не более чем пятью красками.

(cкачать страницу)

Смотреть книгу на libgen

Прежде чем развивать менее тривиальный подход к поиску минимальных раскрасок,  нам надо понять:  а нужно ли рассматривать проблему в полной всеобщности.  При всей увлеченности очередной интересной математической задачей надо помнить,  что в контексте нашего исследования раскраска вершин графа нам нужна не сама по себе,  а как средство экономного распределения памяти.  Может быть,  графы несовместимости,  получающиеся для операторных схем,  обладают какими-нибудь специальными свойствами,  которые могли бы облегчить поиск минимальной раскраски.  Например,  известно,  что любой плоский граф можно раскрасить не более чем пятью красками.