эквивалентность вершин графа

[Missir]

Есть связный граф с раскрашенными вершинами. Каждому набору вершин с одинаковой валентностью и одинаковым цветом соответствует свой, одинаковый набор смежных узлов, характеризуемый одинаковым набором сочетаний цветов и валентностей.
Можно ли в этом случае утверждать, что одинаковые вершины являются эквивалентными, в том смысле, что при дальнейшем исследовании в глубину из этих узлов, никаких различий между ними не будет?

[mihaild]

"Валентность вершины" - степень?
Что такое "узлы"?

[Missir]

да степень, узлы это вершины (опечатка)

[mihaild]

Missir в сообщении #1626390 писал(а):

Каждому набору вершин с одинаковой валентностью и одинаковым цветом соответствует свой, одинаковый набор смежных узлов смежных вершин

Тогда я это не понимаю. Что значит "соответствует", одинаковый с чем? "Набор вершин с одинаковой валентностью и цветом" - это все вершины данной степени и цвета, или просто какое-то множество вершин, у которых цвета и степени совпадают?
Напишите более четко. И желательно пример приведите.

[Drimacus]

Можно поточнее, что значит

Missir в сообщении #1626390 писал(а):

при дальнейшем исследовании в глубину из этих узлов, никаких различий между ними не будет?

Вообще непонятно, что подразумевается под "исследованием в глубину" и под "различием" (если "узлы" считать вершинами). Пути или вообще связные подграфы, содержащие каждую из данных одинаково крашеных вершин с одинаково крашеными смежными вершинами? Если да, то они, конечно же, могут различаться, т.к. вы не конкретизировали раскраску, и все, что достаточно далеко от вершин, смежных к выбранным, может быть произвольным. Например, возьмем раскраску цепочки 7 вершин $12323245$, две тройки имеют одинаково крашеных соседей, но не все подграфы, их содержащие (даже пути) одинаковые.
Вы наверняка имели в виду что-то не столь тривиальное, но тогда объясните конкретнее и точнее, что именно.

[Missir]

Попробую так:
1 все вершины графа делятся на несколько групп,
2 каждая группа характеризуется валентностью и цветом, т.е. в пределах группы валентности и цвета вершин одинаковые,
3 кроме этого, у членов каждой группы не только одинаковые цвета и валентности, но и одинаковые смежные вершины,
т.е. связаны с вершинами одного и того же набора групп

Например:
группа А: все вершины красные, трёхвалентные, каждая из них связана с вершиной из группы Б и двумя вершинами из группы С,
группа Б: все вершины красные, трёхвалентные, связаны с вершиной группы А и двумя вершинами группы С,
грyппа С: все вершины зелёные, трёхвалентные, связаны с вершиной Б и двумя вершинами А,

являются ли эти группы автоморфизмами?

[mihaild]

Что значит "группа является автоморфизмом"? Для пары вершин группы существует автоморфизм графа, сохраняющий цвета, переставляющий эти две вершины?
Нет конечно. Пример (придумайте, как провести ребра): в группе А 5 красных вершин, каждая связана с двумя из Б, в группе Б 5 синих вершин, каждая связана с двумя из А. Степени у всех вершин равны 2.