Otro gráfico de invariante: la matriz de similitud

Question

Preliminares

Deje $n \in \mathbb{N}$ $v$ ser un vértice de un grafo $G$. Vamos a la $n$-barrio de $v$, $N_n(v)$, ser el subgrafo inducido de $G$ contiene $v$ y todos los vértices en la mayoría de las $n$ bordes lejos de $v$.

Con $\epsilon(v)$ la excentricidad de $v$, $N_{\epsilon(v)}(v)$ es obviamente nada pero el componente conectado de $G$ contiene $v$, por lo que es natural para restringir $n$ para un determinado $v$ a los valores de $0,1, ..., \epsilon(v)$.

Considere la posibilidad para cualquiera de los dos vértices $v$, $w$ el mayor $s = s(v,w)$ tal que $N_s(v)$ $N_s(w)$ son isomorfos [añadido:] con el isomorfismo envío de $v$ $w$(para abreviar: $N_s(v) \cong_{vw} N_s(w)$). Si $s(v,w) = \epsilon(v) = \epsilon(w)$, $v$ y $w$ son conjugadas. Para no conjugada vértices $v$, $w$ el número de $s= s(v,w)$ refleja el tamaño de la más pequeña de barrio que es necesaria para distinguir $v$$w$, ya que el $N_{s+1}(v) \ncong_{vw} N_{s+1}(w)$, por definición.

Vamos a llamar al número positivo

$$\sigma(v,w) = \frac{2 \cdot s(v,w)}{\epsilon(v) + \epsilon(w)}$$

el índice de similitud de $v$$w$.

$\sigma(v,w) = 0$ indica que $v$, $w$ tienen diferentes $1$-los barrios (y son máximamente disímiles), $\sigma(v,w) = 1$ indica que $v$, $w$ son conjugado (es decir, máximo similar = indistinguibles por sus barrios).

La matriz $\Sigma(G) = \lbrace \sigma(v,w) \rbrace_{v,w \in V(G)}$ refleja la simetría de la gráfica de $G$:

• Si $\sigma(v,w) = 1$ si $v = w$, el gráfico es asimétrica.
• Si el $1$'s de la matriz vienen en bloques cuadrados a lo largo de la diagonal, estos bloques se indican las órbitas de la gráfica.

$\Sigma(G)$ es un gráfico invariante hasta matriz de equivalencia. (Es esta la mejor redacción?)

Definición: Una $n \times n$-matriz $S$ es una matriz de similitud iff hay un gráfico de $G$ tal que $S = \Sigma(G)$.

Preguntas

Es la noción de $n$-barrio tratados en otros contextos, tal vez bajo otro nombre?

---

Hay ya una investigación sobre este concepto de similitud (o uno)?

---

Cómo podría matrices de similitud ser se caracteriza (suficiente/condiciones necesarias)? ("Una matriz es una matriz de similitud si ...") Alguna idea?

---

¿Cómo serán los gráficos con la misma matriz de similitud (más el mismo vector de excentricidad) estar relacionado? (Que no serán probablemente no tiene que ser isomorfo, pero tal vez algo más débil?)

Answer 1

Esto es agradable. ¿Cuál es la motivación para dividir por $\epsilon(u)+\epsilon(v)$?

A parte de responder a su primera pregunta, sospecho que la noción de $n$-barrio es relativamente común, pero un lugar donde es muy común, si no un elemento básico, en lo Finito Modelo de Teoría (lea también de la Base de la Teoría). Es un componente clave de los diversos localidad propiedades, en particular Gaifman localidad. La cantidad de $s(u,v)$ está estrechamente relacionado con la complejidad de distinguir $u$ $v$ por un primer orden de la consulta en el lenguaje de los gráficos. Específicamente, una consulta de cuantificador profundidad de $k$ no puede distinguir entre los vértices tal que $s(u,v) > (3^{k+1}-1)/2$. Esto tiene muchos usos, un ejemplo típico es el de medir la complejidad de distinguir las entradas de base de datos. Una buena introducción se puede encontrar en los primeros capítulos de Libkin de Elementos Finitos el Modelo de la Teoría.

Answer 2

Esta es una pregunta interesante! Sólo un par de (esperemos) pertinente cosas que vienen a la mente...

1. Cuando te refieres a "matriz de equivalencia" que esencialmente significa que el orden de los vértices, ¿es eso cierto? Esto correspondería a una permutación de similitud de la matriz (ordinarios de la matriz de similitud, con respecto a una matriz de permutación) pero esto es casi siempre a la izquierda que no se dice en la teoría de grafos, de todos modos. (Que a menudo se refieren a "la" matriz de adyacencia de una gráfica, por ejemplo).

2. Sin duda dos gráficos con la misma matriz de similitud no necesita ser isomorfo, como cualquiera de los dos vértices transitiva gráficos tendrán cada uno una matriz de similitud de todos los 1.