Один алгоритм раскраски графа
В этой небольшой заметке я хочу показать, как с помощью алгебры можно решать классическую задачу о раскраске вершин графа. Об этом сюжете я узнал из книги W. Adams, P. An Introduction to Groebner Basis параграф 2. Для начала обсудим все необходимые понятия. Пусть — это некоторое множество, а — множество, состоящее из неупорядоченных пар элементов множества.
Отправьте статью сегодня! Журнал выйдет 18 мая , печатный экземпляр отправим 22 мая. Автор : Моторина Екатерина Алексеевна. Дата публикации : Статья просмотрена: раза.
Раскраска графа это такая разметка графа, при которой любым двум смежным вершинам соответствуют разные цвета. Так как раскрасок графа может быть множество, то чаще всего интересует раскраска графа минимальным количеством цветов. Для раскраски графов сервис использует Жадный алгоритм. По этой причине для некоторых случаев алгоритм может находить близкое к минимального количеству цветов, но не самое минимальное. Toggle navigation Graph Online. Справка Раскраска графа.
