Аннотация:
Два вершинных подмножества в графе с раскрашенными вершинами называются
соцветными, если в этих подмножествах содержится по одинаковому
числу вершин каждого цвета. Раскраска вершин графа называется дистрибутивной,
если соцветны окружения любых вершин одного цвета. В статье
изучаются свойства минимальных дистрибутивных раскрасок и излагается алгоритм
полиномиальной сложности, позволяющий находить такие раскраски.
Ил. 2, библиогр. 2
Полный текст:
PDF файл (1063 kB)