Графы, орбиты которых содержат не более чем три вершины

Abstract

В статье рассмотрен усовершенствованный алгоритм Визинга-Назарца и изучена применимость этого полиномиального алгоритма для разбиения вершин обыкновенных графов на орбиты. С этой целью определены r -строго подобные, строго подобные вершины и множества вершин и изучены их свойства. Отмечено, что любая орбита графа полностью входит в один из классов строго подобных вершин. С другой стороны, доказано, что если классы строгого подобия состоят не более чем из трёх вершин, то эти классы и есть орбиты.