Estou lendo sobre classes de gráficos para o qual Graph Isomorfismo ( ) está em . Um desses casos são gráficos de valência limitada (máximo acima do grau de cada vértice), conforme explicado aqui . Mas achei muito abstrato. Ficaria muito grato se alguém puder me sugerir algumas referências de natureza expositiva. Como não tenho formação sólida em teoria de grupos, prefiro trabalhos que usem a teoria de grupos de maneira suave (minha formação é em CS).
17
Respostas:
O algoritmo para isomorfismo de gráfico de grau limitado está tão intimamente ligado à teoria dos grupos (permutação) que duvido que exista uma introdução que use os grupos "apenas suavemente". No entanto, você pode consultar o Ph.D. de Paolo Codenotti tese para um histórico mais completo. Ele não cobre exatamente o isomorfismo de gráfico de grau delimitado, mas cobre as ferramentas necessárias para ele (e o restante da tese trata de hipergrafos de classificação limitada, estendendo o algoritmo mais conhecido para o isomorfismo de gráfico geral ao caso do hipergrafo de classificação limitada) .
Você também pode achar útil o livro Algoritmos Teóricos de Grupos e Isomorfismo de Gráfico , pois cobre a maior parte do contexto necessário (o Capítulo 2, "Conceitos Básicos", tem 47 páginas) e é uma exposição muito mais lenta do que a maioria dos trabalhos publicados sobre o tópico.
fonte
Notação: Let ser gráfico, e = ( v 1 , v 2 ) uma aresta de X . O conjunto vértice V k ser o conjunto de vértices de distância k a partir de e , e deixá- H ser a altura de X .X=(V,E) e=(v1,v2) X Vk k e h X
De acordo com a definição de , V = V 0 ∪ V 1 ... V H e V ( h + 1 ) = ∅ . Seja o subconjunto E k das arestas de X ( 0 ≤ k ≤ h ) definido comoVk V=V0∪V1…Vh V(h+1)=∅ Ek X(0≤k≤h)
O subgrafo é definido comoXi
Por exemplo,X2={(V0∪V1∪V2,E0∪E1)}
é o grupo de automorfismo do gráfico X em que e é fixo. Se B é um grupo gerador de um u t e ( X k ) , que escrever ⟨ B ⟩ = Um u t e ( X k ) , por exemplo, é evidente que uma u t e ( X 0 ) = ⟨ ( v 1 , v 2Aute(X) X e B Aute(Xk) ⟨B⟩=Aute(Xk) Onde ( v 1 , v 2 ) é uma permutação de vértices v 1 , v 2 de X .Aute(X0)=⟨(v1,v2)⟩ (v1,v2) v1,v2 X
Princípio A construção de um grupo gerador de automorfismo de é um problema completo de GI (gráfico isomorfismo) [1]. Portanto, se pudermos calcular o conjunto gerador do grupo automorfismo X (que tem valência limitada no tempo polinomial), podemos resolver o GI no tempo polinomial. Então, queremos determinar A u t e ( X ) .X X Aute(X)
Técnica:
Vamos construir . Para cada X k , construiremos A u t e ( X ( k ) )X0,X1.....Xh Xk Aute(X(k))
Note-se que, uma permutação de pode ser estendido para uma automorphism de um u t e ( X ( k + 1 ) ) .Aute(X(k)) Aute(X(k+1))
So, generators ofAute(X(k+1)) can be obtained from generators for Aute(Xk) .
To construct generator, structure-type ofEk is manipulated. The structure-type of Ek can be divided into finite classes. For example, in the trivalent case, there are only six type (only five of those cases can actually occur).
We will classify the edges inEk into types and will group them into families . This helps to create a number of unique labels.
For a fixed valence, the number of labels is small. At this point, we use the concept of setwise-stabilizers to find permutations which acts on particular label. In the process, we find the generator ofAute(X(k)) . Then, we use the generator ofAute(X(k)) to find the generator of Aute(X(k+1)) , as stated earlier. Proceeding in this manner, we obtain, Aute(X) .
fonte