Алгоритм раскраски вершин графа может быть реализован также в виде последовательности склеивания соцветных вершин графа. ... - Большая Энциклопедия Нефти и Газа



Выдержка из книги Горбатов В.А. Логическое управление распределёнными системами


Алгоритм раскраски вершин графа может быть реализован также в виде последовательности склеивания соцветных вершин графа. Поскольку при склеивании соцветных вершин графа Vf и Vj все цепи нечетной длины, соединяющие данные вершины, преобразуются в циклы нечетной длины, а все цепи четной длины - в циклы четной длины, степень желательности соцвет-ности вершин можно оценивать значением L ( vt, Vj) S3 ( i j) j / S2 ( i j), где S3 ( i j), S2 ( i j) - соответственно элементы куба и квадрата матрицы смежности S графа.

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

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

Алгоритм раскраски вершин графа может быть реализован также в виде последовательности склеивания соцветных вершин графа. Поскольку при склеивании соцветных вершин графа Vf и Vj все цепи нечетной длины, соединяющие данные вершины, преобразуются в циклы нечетной длины, а все цепи четной длины - в циклы четной длины, степень желательности соцвет-ности вершин можно оценивать значением L ( vt, Vj) S3 ( i j) j / S2 ( i j), где S3 ( i j), S2 ( i j) - соответственно элементы куба и квадрата матрицы смежности S графа.