Граф Кэли

[Сомик]

Пусть задан некоторый конечный ориентированный размечанный граф$G$. Степерь исхода кажой вершины равна $k$, ребра, выходящие из вершины, помечены буквами из алфавита$A=\{a_1,\dots,a_k\}$.
Какие существуют оптимальные алгоритмы проверки того, что граф$G$ является графом Кели некотрого монойда?
Можно ли условие "являться графом Кели" записать в виде некотрого соотноешния матриц смежности, которыми задан граф $G$?

[maxal]

Сомик писал(а):

ребра, выходящие из вершины, помечены буквами из алфавита$A=\{a_1,\dots,a_k\}$.

Какой в этом смысл?

[Сомик]

maxal писал(а):

Сомик писал(а):

ребра, выходящие из вершины, помечены буквами из алфавита$A=\{a_1,\dots,a_k\}$.

Какой в этом смысл?

Смысл в том, что $A=\{a_1,\dots,a_n\}$ - суть проржадющие элементы моноида.

[maxal]

Почему тогда вы пишите "некоторого моноида", а не "некоторого моноида, порожденного A"?

Добавлено спустя 2 минуты 56 секунд:

Если порождающие элементы известны, то задача по сути сводится к проверке выполнения для них свойства ассоциативности. Если же они не известны, то все сложнее.

[Сомик]

maxal писал(а):

Почему тогда вы пишите "некоторого моноида", а не "некоторого моноида, порожденного A"?

Согласен. Можно написать некоторого моноида, порожденного A.

maxal писал(а):

Если порождающие элементы известны, то задача по сути сводится к проверке выполнения для них свойства ассоциативности. Если же они не известны, то все сложнее.

По-моему тут дело сложнее. Дело в том, что вершинами графа Кэли являются элементы моноида. Помечанный граф задает дейсвтие моноида $M$ на вершинах $V$. Но как проверить что элементам полученого моноида можно сопоставить вершины $V$. Ну точнее, я понимаю, что это можно проверить, но меня интересут наиболее эффективный метод. Я уверен, что этот вопрос уже изучался, но, к сожалению, я так и не смог нигде это найти.

Нашел много работ на тему - когда граф Кэли планарен (не очень понял в зачем это надо ), а вот про проверку графа быть Кэлевым не смог найти

[maxal]

Сомик писал(а):

По-моему тут дело сложнее. Дело в том, что вершинами графа Кэли являются элементы моноида. Помечанный граф задает дейсвтие моноида $M$ на вершинах $V$. Но как проверить что элементам полученого моноида можно сопоставить вершины $V$.

У вас же нет $M$ (точнее оно как раз и определяется заданным графом) поэтому и сопоставлять нечего. Другое дело, что можно поставить вопрос о том, какие из вершин соответствуют порождающим элементам из множества $A$.

[Сомик]

maxal писал(а):

У вас же нет $M$ (точнее оно как раз и определяется заданным графом) поэтому и сопоставлять нечего. Другое дело, что можно поставить вопрос о том, какие из вершин соответствуют порождающим элементам из множества $A$.

Конечно изначально нет $M$, но его можно построить, а в силу конечности можно проверить существует ли соответсвие между $M$ и $V$. Порождающие элементы $A$ заданы и если некотрой вершине $v_0 \in V$ сопостаить единицу монойда, то той вершине, куда идет ребро из $v_0$ с пометкой$a_i$ сопоставляется элемент монойда $a_i$.
Но задача меня интересует именно в той постановке. Задан ориентированный помечанный граф, является ли он графом Кели, для некотрого монойда порожденного $A$

[maxal]

Сомик писал(а):

Конечно изначально нет $M$, но его можно построить, а в силу конечности можно проверить существует ли соответсвие между $M$ и $V$.

Если вы построите $M$, исходя из данного графа, то у вас автоматически будет и соответствие между $M$ и $V$. Поэтому задача о нахождении такого соответствия не представляет самостоятельного интереса.

Добавлено спустя 7 минут 44 секунды:

А ответ на ваш исходный вопрос, похоже, дается в этой статье:
Pierre Fraigniaud, Cyril Gavoille, M. Robson. On recognizing Cayley graphs.

[Сомик]

maxal писал(а):

А ответ на ваш исходный вопрос, похоже, дается в этой статье: http://citeseer.ist.psu.edu/295379.html

Спасибо !!!!