Dejemos que $V = (v_1,...,v_n)$ sea un conjunto de vértices de un grafo dirigido. Denotamos una arista entre dos vértices $v_i$ et $v_j$ por $(i,j)$ . El conjunto de bordes $E$ para un gráfico $(V,E)$ es entonces un conjunto de tuplas $E \in P(\{(i,j) \mid i,j \in \{1,...,n\}\})$ .
Mi pregunta es si para los fijos $n \in \mathbb{N}$ podemos definir eficientemente un mapa $$ F_n : P(\{(i,j) \mid i,j \in \{1,...,n\}\}) \rightarrow \mathbb{R} $$ tal que $F_n(E)=F_n(E')$ si y sólo si los dos grafos son iguales en cuanto a la permutación de los vértices, es decir, si existe una permutación $\sigma \in S_n$ tal que $E = \{(\sigma(i),\sigma(j)) \mid (i,j) \in E'\}$ .
Este mapa debería ser relativamente sencillo de construir con sumas sobre todas las permutaciones. Estoy interesado en invariantes conocidos más simples, que idealmente requerirían menos de $\mathcal{O}(n!)$ cantidad de trabajo para calcular.
Soy nuevo en la teoría de grafos y pensé que alguien debía haber pensado ya en esto, ya que es fundamental para clasificar los grafos. Se agradece cualquier referencia o indicación en la dirección correcta.
