¿Son estos dos gráficos isomorfos?

Question

Cumplen los requisitos de tener una $=$ número de vértices ( $7$ ).

Ambos tienen el mismo número de aristas ( $9$ ).

Ambos tienen $3$ vértices de grado $2$ y $4$ de grado $3$ .

Sin embargo, el gráfico dos tiene $2$ circuitos simples de longitud $3$ mientras que el gráfico uno sólo tiene $1$ de longitud $3$ .

¿No es éste un método válido para comprobar el isomorfismo?

Mi guía dice que estas dos figuras son isomorfas.

Answer 1

Una vez que tengas un isomorfismo, puedes crear una animación que ilustre cómo transformar un gráfico en el otro. Digamos que ${vc}_1$ es una lista de coordenadas de vértices para uno y ${vc}_2$ es la correspondiente lista de coordenadas de vértices de la otra. (Es importante que el orden de las coordenadas de los vértices esté dictado por el isomorfismo). Entonces podemos pasar de un gráfico al otro utilizando una función como

$$p(t) = t \, {vc}_2 + (1-t) {vc}_1.$$

Este es el resultado.

Código

La película puede generarse utilizando el siguiente código de Mathematica.

vc1 = # - {1, 1} & /@ {{0, 2}, {1, 2}, {2, 2}, {1, 1}, 
  {0, 0}, {1, 0}, {2, 0}};
vc2 = {{1/2, -Sqrt[3]/2}, {-1/2, -Sqrt[3]/2}, {-1, 0}, 
  {1/2, Sqrt[3]/2}, {1, 0}, {0, 0}, {-1/2, Sqrt[3]/2}};
vc[t_] := t*vc2 + (1 - t) vc1;
Animate[
  Graph[{1, 2, 3, 4, 5, 6, 7},
    UndirectedEdge@@@{{1, 2}, {2, 3}, {3, 7}, {7, 6}, {6, 5}, {5, 1}, 
     {1, 6}, {4, 5}, {4, 7}},
    PlotRange -> 1.1, VertexCoordinates -> vc[t]],
  {t, 0, 1}, AnimationDirection -> ForwardBackward]

Answer 2

Hay un isomorfismo $f$ dado en los vértices por

$$f(A)=7,\: f(B)=4,\: f(C)=3,\: f(D)=6,\: f(E)=5,\: f(F)=2,\: f(G)=1.$$

A continuación se presenta una ilustración del isomorfismo:

Answer 3

Si dos grafos son isomorfos, si representamos uno de ellos como una matriz, podemos encontrar una matriz de adyacencia para el otro que es idéntica, excepto por los nombres de los nodos y aristas.

Una matriz de adyacencia para el grafo de la izquierda es:

   A B C D E F G
A:   1 1 1       
B: 1     1 1
C: 1         1
D: 1       1   1
E:   1   1     1
F:     1       1
G:       1 1 1

Si identificamos los vértices como (A B C D E F G) = (7 4 3 6 5 2 1), y escribimos la matriz de adyacencia del segundo grafo en ese orden, obtenemos la misma matriz:

   7 4 3 6 5 2 1
7:   1 1 1       
4: 1     1 1
3: 1         1
6: 1       1   1
5:   1   1     1
2:     1       1
1:       1 1 1

Por supuesto, los objetos no son isomórficos si los nombres de los vértices se consideran significativos en la representación. O si hay restricciones, como que A debe identificarse con el nodo 1 (porque, digamos, el grafo forma parte de algún objeto mayor, y la forma en que se conectan a él no es negociable).

Dos entidades que se consideran isomorfas nunca son idénticas, a menos que sean la misma entidad.

Un isomorfismo siempre se basa en preocuparse por algunas posibles diferencias, mientras se declara que otras no importan.

Answer 4

Sí. En el segundo gráfico, el nodo de deslizamiento 4 fuera del cuadrado y observar que los nodos 1,2,3,7,4,5 ahora forman un hexágono, con el nodo 6 en su interior. Nodo 6 corresponde ahora al nodo D . Para obtener detalles rigurosos, consulte la respuesta de Daniel Rust. Se puede comprobar que su construcción es efectivamente un isomorfismo aplicando la definición: que para cualquier $a$ , $b$ en el primer gráfico, $f(a)$ está conectado a $f(b)$ si y sólo si $a$ está conectado a $b$ .