¿Cómo puedo producir ' canónica ' formas para grafos bipartidos arraigados?

Question

Los gráficos me interesa son grafos bipartitos con una raíz especificado vértice. Porque hay una raíz, todos los vértices están graduadas por su distancia desde la raíz. Debido a que el grafo es bipartito, los vértices en profundidad $d$ sólo alguna vez conectados a otros vértices en las profundidades $d \pm 1$ (y, en particular, no de la profundidad de $d$).

Cuando me representan estos gráficos, I orden de los vértices en cada profundidad, y el registro de los bordes por una serie de matrices, esencialmente la lista de las matrices de adyacencia de cada profundidad a la siguiente. (Es decir, la totalidad de la matriz de adyacencia es simétrica y el bloque de tridiagonal, con cero diagonal de bloques. Acabo de escribir el superdiagonal bloques.)

Ahora, si puedo cambiar el orden de los vértices a cierta profundidad (esto sólo permutes las filas de una matriz y las columnas de la siguiente), obviamente tengo la misma gráfica. Me gustaría un algoritmo que recoge un orden particular en cada profundidad, para cada gráfico, la producción de una "forma canónica", con las siguientes propiedades:

1. el algoritmo es idempotente, aplicar una segunda vez no hace nada,
2. el algoritmo es estable, en el sentido de que si usted acaba de ver en la primera $d$ profundidades de un gráfico y ver que el gráfico ya está 'en forma canónica', entonces cuando se produce una forma canónica para el conjunto de la gráfica de los primeros a $d$ profundidades no son cambiadas, y
3. como muchos isomorfo gráficos como sea posible son identificados!

Puede que no sea posible satisfacer a 3. completamente; por ejemplo, la identidad de la operación cumple 1. y 2., pero hace un muy mal trabajo en 3. No es esencial para mi aplicación que cada isomorfo par de gráficas en las que se identifican. (Yo estaría usando este algoritmo para acelerar una combinatoria de búsqueda de ciertos tipos de gráficos, donde sé que estoy innecesariamente la producción de muchos isomorfo copias de la misma gráfica, pero los detalles de la búsqueda requieren que use esta representación.)

¿Alguien sabe de un algoritmo? ¿Alguien puede sugerir algo bueno?

Answer 1

Usted puede encontrar Mugnier y de Chein papel "Caracterización y reconocimiento algorítmico de grafos conceptuales canónicos" (1993) útil.

Ver http://www.springerlink.com/content/77342v2587l40qtn/

Answer 2

Este problema es a través de algoritmos equivalente general para el problema de encontrar un canónica de etiquetado para un gráfico. A ver, por un gráfico arbitrario, añadir un nuevo vértice adyacente a todo y llamar a la raíz, luego subdividir cada borde con un nuevo vértice. El resultado es una arraigada bipartito gráfico. Volviendo a la original es fácil. Canónica de etiquetado ha desconocido peor de los casos la complejidad, a pesar de que hay programas efectivos como nauty, la felicidad y las Huellas que puede manejar gráficos con miles de vértices.

Answer 3

Creo que la mejor manera de hacerlo es la siguiente algoritmo trivial. Cuando quieras orden de los vértices en la profundidad d+1, aspecto en el que ya se ordenó el nivel d y asociado con cada vértice en el nivel d+1 la cadena cuya i-ésima bit es 1 si está conectado a la i-ésima vértice en el nivel d y 0 si no lo es. A continuación, la orden de los vértices en el d+1 de nivel de acuerdo a la lexicográfica del orden de las cuerdas, de decidir las igualdades de acuerdo con el orden original de los vértices en el adjecency de la matriz (o de cualquier otra forma). Creo que está claro que es imposible hacerlo mejor si usted insiste en la propiedad 2, ya que en este algoritmo podemos diferenciar todos los vértices que podemos.

Answer 4

No sé de ninguna respuesta definitiva a tu pregunta, pero sería una idea para cada nivel por orden creciente? llega un poco más (aunque no tanto) al isomorfismo