Hola!
Dados los grafos
a) Definir un isomorfismo entre ellos. Justificar.
b) En el grafo \(G_2\) indique qué arista habría que suprimir para que \(X\) sea istmo. Justificar.
Las respuestas escritas tal cual son así:
a)
Hay dos isomorfismos posibles:
1) Función biyectiva \(f(A)=X\), \(f(B)=Y\), \(f(C)=T\), \(f(D)=Z\), \(f(E)=V\), \(f(F)=U\).
Las matrices de adyacencia coinciden: \[\begin{array}{|c|c|c|c|c|c|c|}
\hline
&A&B&C&D&E&F\\
\hline
A&0&1&1&1&1&1\\
\hline
B&1&0&1&1&1&0\\
\hline
C&1&1&0&1&0&0\\
\hline
D&1&1&1&0&0&0\\
\hline
E&1&1&0&0&0&1\\
\hline
F&1&0&0&0&1&0\\
\hline
\end{array}
\qquad
\begin{array}{|c|c|c|c|c|c|c|}
\hline
&X&Y&T&Z&V&U\\
\hline
X&0&1&1&1&1&1\\
\hline
Y&1&0&1&1&1&0\\
\hline
T&1&1&0&1&0&0\\
\hline
Z&1&1&1&0&0&0\\
\hline
V&1&1&0&0&0&1\\
\hline
U&1&0&0&0&1&0\\
\hline
\end{array}\] 2) o bien \(f(A)=X\), \(f(B)=Y\), \(f(C)=Z\), \(f(D)=T\), \(f(E)=V\), \(f(F)=U\).
También se verifica por igualdad de las matrices de adyacencia: \[\begin{array}{|c|c|c|c|c|c|c|}
\hline
&A&B&C&D&E&F\\
\hline
A&0&1&1&1&1&1\\
\hline
B&1&0&1&1&1&0\\
\hline
C&1&1&0&1&0&0\\
\hline
D&1&1&1&0&0&0\\
\hline
E&1&1&0&0&0&1\\
\hline
F&1&0&0&0&1&0\\
\hline
\end{array}
\qquad
\begin{array}{|c|c|c|c|c|c|c|}
\hline
&X&Y&T&Z&V&U\\
\hline
X&0&1&1&1&1&1\\
\hline
Y&1&0&1&1&1&0\\
\hline
T&1&1&0&1&0&0\\
\hline
Z&1&1&1&0&0&0\\
\hline
V&1&1&0&0&0&1\\
\hline
U&1&0&0&0&1&0\\
\hline
\end{array}\]
¿Qué critico? Tres cosas:
1) ¿Por qué se dice que "sólo hay dos isomorfismos"? ¿Por qué no podemos ir de \( G_2 \) a \( G_1 \)?
2) Que a ambos isomorfismos les falten el dominio y codominio. Diría "\(f:G_1\to G_2\mid f(A)=\cdots,f(B)=\cdots,\ldots\)".
3) Que para ambos isomorfismos tengan la misma letra. Diría "\(f:G_1\to G_2\mid f(A)=\cdots,f(B)=\cdots,\ldots\)" para uno y "\(g:G_1\to G_2\mid g(A)=\cdots,g(B)=\cdots,\ldots\)" para otro.
¿Qué les parece?
b)
Para que \( X \) sea istmo, debería suprimirse la arista \(\{V,Y\}\).
¿Qué critico? Una cosa:
La respuesta no está justificada.
Yo diría:
Para justificar la supresión de \(\{V,Y\}\) recordemos la definición de istmo de un vértice.
Definición (istmo de un vértice de un grafo). Sean \( G=(V,A,\varphi) \) un grafo conexo (*), \( v\in V \) y \( a\in A \). \( v \) es un istmo si y sólo si \( {\tilde G}_v \) es no conexo, donde \( {\tilde G}_v=(V\setminus\{v\},A\setminus\{\text{aristas incidentes en \(V\)}\},\Gamma) \).
En nuestro caso, el subgrafo que se forma al quitar el vértice \( X \) es \( {\tilde G}_X=(V\setminus\{X\},A\setminus\{\{V,X\},\{U,X\},\{Y,X\},\{Z,X\},\{T,X\}\},\Gamma) \)
Como vemos, la única opción para que el subgrafo sea no conexo es quitar la arista \(\{V,Y\}\), ya que entre dos vértices cualesquiera no existe ningún camino que los una.
¿Es correcto?
Gracias!
Felices fiestas
(*) En mis apuntes no se especifica que el grafo sea "conexo", pero en los libros lo dice (por eso lo pongo). ¿De las dos maneras está bien?
