#Do_you_understand
Помнишь, у нас был пост про графы? Одна из наиболее известных задач, принадлежащих классу NP, звучит как проблема раскраски графа.
Зачем вообще кого-то красить? Во-первых, раскрашенный граф намного симпатичнее, во-вторых, к этой задаче сводится много логистических проблем.
Правила раскраски таковы - должны быть покрашены все вершины, причем две вершины, соединенные между собой одним ребром, не могут быть одного цвета. Задача найти минимальное количество цветов, которое удовлетворит этому условию.
Это крайне легко сделать для графа из двух-трех-четырех вершин, но, если их будет хотя бы тысяча - компьютеру на расчеты понадобится не один год.
О чем рубрика
Помнишь, у нас был пост про графы? Одна из наиболее известных задач, принадлежащих классу NP, звучит как проблема раскраски графа.
Зачем вообще кого-то красить? Во-первых, раскрашенный граф намного симпатичнее, во-вторых, к этой задаче сводится много логистических проблем.
Правила раскраски таковы - должны быть покрашены все вершины, причем две вершины, соединенные между собой одним ребром, не могут быть одного цвета. Задача найти минимальное количество цветов, которое удовлетворит этому условию.
Это крайне легко сделать для графа из двух-трех-четырех вершин, но, если их будет хотя бы тысяча - компьютеру на расчеты понадобится не один год.
О чем рубрика