¿Isomorfismo en etiquetado grafos donde los vértices de la misma "posición" deben tener etiquetas equivalente?

Question

Estoy buscando información sobre un tipo específico de relación de equivalencia sobre etiquetado de los gráficos. Específicamente, quiero dos etiquetado de los gráficos para ser consideradas equivalentes si sus subyacente sin etiquetar los grafos son isomorfos y vértices en la misma "posición" tienen las etiquetas equivalentes (según algunos relación de equivalencia definida en el vértice de las etiquetas).

Espero el siguiente ejemplo ilustra el tipo de relación de equivalencia en la etiqueta gráficos que estoy buscando.

Ejemplo: El conjunto de posibles vértice etiquetas son las letras del alfabeto inglés, que pueden estar en mayúsculas o minúsculas. Ahora considero que dos vértices etiquetas equivalente si son de cualquiera de los dos una letra mayúscula o ambos una letra minúscula. Ahora, como un ejemplo, considere los siguientes tres gráficos:

Gráfico de $G_{abC}$:

Gráfico de $G_{deF}$:

Gráfico de $G_{GHi}$:

Deje $[a]$ ser la clase de equivalencia de letras minúsculas y $[A]$ la clase de equivalencia de las letras mayúsculas. Si me re-etiquetar cada vértice con el correspondiente equivalencia de la clase, luego de los primeros dos gráficos puedo obtener la misma etiqueta gráfico de $G_{[a][a][A]}$:

Para el tercer gráfico, por otro lado, me da un diferente recalificado gráfico de $G_{[A][A][a]}$:

Así que, aunque todos los tres grafos son isomorfos, quiero decir que sólo los primeros dos gráficos son equivalentes. Específicamente, $G_{abC}$ $G_{deF}$ son equivalentes, pues el reetiquetado con vértice clases de rendimientos de la misma recalificado gráfico de $G_{[a][a][A]}$. El tercer gráfico $G_{GHi}$, por otro lado, no es equivalente a los otros porque su recalificado gráfico de $G_{[A][A][a]}$ es diferente de $G_{[a][a][A]}$.

Así que ¿alguien puede decirme si hay un nombre estándar para una clase de equivalencia de la relación en la etiqueta gráficos? Por otra parte, ¿alguien sabe de las referencias en las que dicha relación de equivalencia que se discute? En particular, estoy interesado en los algoritmos para determinar si dos grafos etiquetados son equivalentes en la forma que he descrito.

Answer 1

Quiero pensar de sus vértices del grafo como "cargada" o "color" (según la equivalencia de las etiquetas). Entonces cuando usted calcular isomorfismos, que desea respetar el colorante. El nauty programa tiene soporte para esto. La manera por defecto que esto es implementado es que un vértice coloreado específico sólo puede enviarse a un vértice que es del mismo color, para que esto debe cumplir exactamente lo que quieres.

Answer 2

Supongamos que $G_1$ y $G_2$ están etiquetados gráficos. Que el conjunto de vértices de un gráfico $G=(V,E)$ ser $V(G)$ donde cada $v \in V(G)$ se supone que tienen una etiqueta única.

Decimos que dos gráficos $G_1$ y $G_2$ son equivalentes si existe un $f(G_1)=(f_v(V_1),f_e(E_1))=G_2$ tal que (1) (preservación de adyacencia, isomorfismo del gráfico) $(v_1,v_2) \in E(G_1) \iff (f_v(v_1),f_v(v_2))\in E(G_2)$ y 2, equivalencia $\forall v \in V(G_1)\; ,\; f_v(v) \sim v$.

(En la reescritura $\sim$ significa el equivalente a).

Además, he utilizado abusivamente $f_v(V_1) = \{f_v(v) | v \in V(G_1)\}$

Lo siento, si estoy siendo claro.