2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Граф Кэли
Сообщение23.12.2007, 00:01 
Аватара пользователя
Сомик писал(а):
ребра, выходящие из вершины, помечены буквами из алфавита$A=\{a_1,\dots,a_k\}$.

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

 
 
 
 Re: Граф Кэли
Сообщение23.12.2007, 00:13 
Аватара пользователя
maxal писал(а):
Сомик писал(а):
ребра, выходящие из вершины, помечены буквами из алфавита$A=\{a_1,\dots,a_k\}$.

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

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

 
 
 
 
Сообщение23.12.2007, 00:20 
Аватара пользователя
Почему тогда вы пишите "некоторого моноида", а не "некоторого моноида, порожденного A"?

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

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

 
 
 
 
Сообщение23.12.2007, 00:42 
Аватара пользователя
maxal писал(а):
Почему тогда вы пишите "некоторого моноида", а не "некоторого моноида, порожденного A"?


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

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


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

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

 
 
 
 
Сообщение23.12.2007, 01:04 
Аватара пользователя
Сомик писал(а):
По-моему тут дело сложнее. Дело в том, что вершинами графа Кэли являются элементы моноида. Помечанный граф задает дейсвтие моноида $M$ на вершинах $V$. Но как проверить что элементам полученого моноида можно сопоставить вершины $V$.

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

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

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

 
 
 
 
Сообщение23.12.2007, 02:37 
Аватара пользователя
Сомик писал(а):
Конечно изначально нет $M$, но его можно построить, а в силу конечности можно проверить существует ли соответсвие между $M$ и $V$.

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

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

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

 
 
 
 
Сообщение23.12.2007, 03:05 
Аватара пользователя
maxal писал(а):
А ответ на ваш исходный вопрос, похоже, дается в этой статье: http://citeseer.ist.psu.edu/295379.html


Спасибо !!!! :D

 
 
 [ Сообщений: 9 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group