Las respuestas ya están dadas después del signo$=$ de cada pregunta. Pero no sé cómo llegaron a estas respuestas. ¿Qué significa decir$f(A)=1$ y así sucesivamente? No puedo encontrar la conexión.
Respuesta
¿Demasiados anuncios?
Un gráfico puede ser pensado como un par de $(V,E)$ donde $V$ son los vértices y $E$ son los bordes. Un isomorfismo entre dos gráficos, $G_1 = (V_1,E_1)$ $G_2=(V_2,E_2)$ significa que una función $f\colon V_1\to V_2$ que es bijective entre los vértices (uno-a-uno y a, por lo que cada vértice $G_1$ es asignado a un vértice de $G_2$, y cada vértice en $G_2$ es la imagen de uno y sólo un vértice en $G_1$) y para los vértices $v_1,v_2$ de $G_1$, $v_1$ es adyacente a $v_2$ $G_1$ si y sólo si $f(v_1)$ es isomorfo a$f(v_2)$$G_2$.
Así, la respuesta que dan es una descripción de un isomorfismo entre el segundo gráfico y la primera: es una función de un conjunto de vértices de la segunda gráfica, $\{A,B,C,D,G,H,I,J\}$, y los vértices de la primera gráfica, $\{1,2,3,4,5,6,7,8\}$, con la propiedad de que dos vértices en el segundo gráfico de $x$$y$, son adyacentes si y sólo si $f(x)$ es adyacente a $f(y)$ en el segundo gráfico. Por ejemplo, $A$ $I$ son adyacentes, por lo $f(A)=1$ tiene que ser adyacente a $f(I)=4$ (lo que es), y $A$ $J$ no son adyacentes, por lo $f(A)=1$ debe no ser adyacente a $f(J)=7$ (que no es). Se puede comprobar que la función descrita en realidad es un isomorfismo mediante la comprobación de que cada par de vértices adyacentes se envían a los vértices adyacentes, y cada par de no-adyacentes vértices son enviados a la no-adyacentes vértices.
Ahora... ¿cómo llegaron con $f$ en el primer lugar? Bueno, vamos a pensar acerca de los gráficos.
En el segundo gráfico, cada vértice es adyacente a exactamente tres vértices, por lo que si va a ser un isomorfismo entre los dos gráficos, a continuación, cada vértice en el primer gráfico se necesita para ser adyacente a exactamente tres vértices. Esto es cierto, que es un buen comienzo para una posible isomorfismo (si no fuera cierto, tendríamos ninguna esperanza de tener un isomorfismo, y si el hecho de que sepamos que no existe isomorfismo).
También, el segundo gráfico es el "bipartito": se puede dividir a los vértices en dos grupos, de tal manera que todos los bordes están entre los dos grupos, sin bordes entre los vértices en el mismo grupo. Si vamos a encontrar un isomorfismo entre esta gráfica y la primera, tenemos que ser capaces también de separar los vértices de la primera gráfica en dos grupos de cuatro, de forma que todos los bordes están entre los grupos con y sin borde va de un vértice en un grupo a otro vértice en el mismo grupo.
Podemos dividir los vértices en el primer gráfico en dos grupos de cuatro para que todos los bordes están entre los conjuntos? Bien, vamos a ver: si $1$ es en un conjunto, entonces $2$, $4$, y $5$ debe estar en el otro conjunto, porque no puede ser de bordes entre dos vértices en el mismo conjunto (recuerde: estamos tratando de comprobar si existe un isomorfismo). Aviso que si hacemos esto, entonces mejor no ser de cualquiera de los bordes entre $2$, $4$, y $5$, porque vamos a poner en el mismo conjunto (el conjunto que no es el conjunto con $1$). Bueno, no los bordes entre cualquiera de $2$, $4$, y $5$. Y $6$ $3$ necesidad de estar con $1$, debido a que ambos son adyacentes a $2$, y por ello no pueden estar en el mismo conjunto con $2$; la única posibilidad restante es el conjunto de con $1$. Eso significa que $1$, $3$, y $6$ necesitan estar en el mismo conjunto de vértices, lo que significa que no debe haber bordes entre ellos (sin bordes entre dos vértices en el mismo conjunto, ¿recuerdas?). Bueno, no los bordes entre cualquiera de $1$, $3$, y $6$. Y $8$ tiene que ser con $1$, debido a que es adyacente a $4$. Y por lo $7$ tiene que ser con $2$, $4$, y $5$.
Por lo tanto, si podemos encontrar un isomorfismo entre los dos gráficos, entonces podemos dividir los vértices de la primera gráfica en dos conjuntos, como el que en el segundo gráfico, y un conjunto de necesidades que tienen $1$, $3$, $6$, y $8$, y el otro conjunto de necesidades que tienen $2$, $4$, $5$, y $7$. Y todos los bordes deben estar entre los conjuntos, no sin bordes entre los vértices en el mismo conjunto. Todo esto se mantiene, por lo que estamos en el camino correcto!
Así, podemos definir un isomorfismo basado en esto? Hay un montón de simetría, por lo que probablemente no importa de donde se envían $A$, tan largo como hacemos las cosas bien. Así que vamos a enviar a $A$ a $1$: $f(A)=1$. Porque $G$, $H$, y $I$ son adyacentes a $S$, necesitamos $f(G)$, $f(H)$, y $f(I)$ a ser adyacente a $f(A)=1$; así $f(G)$, $f(H)$, y $f(I)$ necesitan ser $2$, $4$, y $5$ en un cierto orden. Decir $f(G)=2$. A continuación, $f(H)$ tiene que ser $4$ o $5$. Si hacemos esto $5$, entonces a partir de la $2=f(G)$ $5=f(H)$ tiene sólo dos mutuamente adyacentes vértice (es decir,$1$$6$), y $G$ $H$ tiene sólo dos mutuamente vértices adyacentes (es decir,$A$$B$), y $A$ ya se asigna a $1$, luego tenemos a $B$ para asignar a $6$. Así que hasta ahora hemos $f(A)=1$, $f(B)=6$, $f(G)=2$, y $f(H)=5$. $B$ es adyacente a $J$, que no es adyacente a $A$, lo $f(J)$ tiene que ser adyacente a $f(B)=6$, pero no a $f(A)=1$; y debe estar en el mismo grupo como $2$ (por lo que tiene ser uno de $2$, $4$, $5$, o $7$); $5$ y $2$ ya están tomadas, $4$ es adyacente a $1$, por lo que tenemos que hacer $f(J)=7$.
Así que hasta ahora hemos $f(A)=1$, $f(B)=6$, $f(G)=2$, $f(H)=5$, y $f(J)=7$. ¿Qué acerca de $C$? $f(C)$ debe ser adyacente a $f(G)=2$$f(J)=7$, pero no a $f(H)=5$; la única posibilidad de que no se ha tomado es $f(C)=3$. Continuando de esta manera se consigue el isomorfismo que dan.
Nota: esta no es la única posible isomorfismo; otras opciones que conducen a otros isomorphisms, de los cuales hay muchos, porque los gráficos son tan simétrica.
