Autor Tema: Invariante de grafos

0 Usuarios y 1 Visitante están viendo este tema.

19 Abril, 2021, 06:16 pm
Leído 203 veces

carambola

  • $$\Large \color{#5372a0}\pi\,\pi$$
  • Mensajes: 59
  • País: es
  • Karma: +0/-0
Probar formalemente que la secuencia de grados es una invariante del isomorfismo de grafos:

Para todo vèrtice se tiene que $$d(u) = d(f(u))$$ donde $$f$$ es una biyección que determina el isomorfismo

Gracias

19 Abril, 2021, 06:33 pm
Respuesta #1

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,079
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Probar formalemente que la secuencia de grados es una invariante del isomorfismo de grafos:

Para todo vèrtice se tiene que $$d(u) = d(f(u))$$ donde $$f$$ es una biyección que determina el isomorfismo

Un isomorfismo de grafos \( (V,A) \) y \( (V',A') \) es una aplicación biyectiva \( f:V\to V'  \) entre sus vértices tal que dos vértices son adyacentes en el primero si y sólo si lo son en el segundo, es decir:

\( \{u,v\}\in A \) si y sólo si \( \{f(u),f(v)\}\in A \)

Ahora:

\( d(u)=cardinal\{v\in V|\{u,v\}\in A\} \)

\( d(f(u))=cardinal\{v'\in V'|\{f(u),v'\}\in A'\} \)

Comprueba que los conjuntos \( \{v\in V|\{u,v\}\in A\} \) y \( \{v'\in V|\{u,f(v)\}\in A\} \) son biyectivos mediante la aplicación \( f \) y por tanto tienen el mismo cardinal.

Saludos.