Hola
¿Conoces alguna definición de subgrafo que hable de las matrices de adyacencia? Teniendo eso creo que podríamos entendernos mejor, ya que toda matriz de adyacencia (salvo ordenamiento de vértices, sin contexto alguno) define unívocamente a un grafo.
No entiendo que aporta en este caso la definición a partir de matrices adyacencias. Vuelvo después con ellas.
Creo que tenemos algún tipo de confusión que no acabo de detectar por completo o que me estoy explicando mal o que me estás entendiendo mal o todo junto. Lo has dicho antes y vuelves aquí a insistir en el problema de manejara grafos como dibujos:
Pienso que dando una definición así nos podríamos ahorrar la representación visual del grafo.
En nada de lo que se ha hablado en este hilo es relevante la representación visual del grafo ni se usa para nada.
Nota que si hay diferentes versiones de subgrafos, ¿qué nos impide ir más lejos? Podríamos argumentar que un grafo con un vértice "un poco más arriba que otro" también son isomorfos, pues las matrices de adyacencia siguen coincidiendo.
No estoy seguro de que quieres decir con "diferentes versiones de subgrafos". No tiene sentido hablar de un vértice "más arriba que otro" a no ser que ya no hablemos de grafos, sino de su representación gráfica sobre un plano; pero eso ya sería entrar en algo completamente distinto; en otra estructura mucho más compleja (asignar coordenadas a los vértices lo que sea). Nada de eso viene a cuento aquí.
El concepto de grafo que estoy manejando y que maneja todo el mundo es: un conjunto de vértices \( V \) y un conjunto de aristas que puede verse como un subconjunto del conjunto de pares no ordenados de elementos de \( V \); es decir, cada arista es un par de vértices. Es una definición conjuntista en la que en ningún momento se presupone representación gráfica alguna.
La definición de subgrafo ya la he dicho antes: un grafo formado por unos subconjuntos de vértices y aristas del grafo original; esto supone que las aristas seleccionadas solo pueden conectar vértices de los seleccionados.
En nada de eso influye la representación gráfica del grafo.
Y por otro lado el considerar dos subgrafos distintos como distintos (observa la deliberada redundancia)... ¡es lo más obvio!.
¿Acaso cuando manejas los subconjuntos del conjunto \( \{1,2,3,4\} \), consideras que \( \{1,2\} \) y \( \{3,4\} \) son el mismo subconjunto?
Me refiero a algo como esto: Un subgrafo \( H \) de un grafo \( G \) es un grafo en donde \( M_A(H)\leq M_A(G) \), aunque no es la definición correcta pues faltarían los subgrafos de vértices menores a \( n \).
Un subgrafo estaría formado por un subconjunto de vértices del inicial y una matriz de adyacencia "menor o igual" (en el sentido de que una matriz es menor o igual que otra si lo es cada elemento) que la correspondiente submatriz de la matriz de adyacencia del grafo original. Por correspondiente submatriz me refiero a la que resulta de quedarse con las filas y columnas de los vértices que pertenencen al subgrafo.
¿Realmente crees que se gana algo para estudiar subgrafos con este punto de vista?.
Saludos.
Añadido: Dicho todo esto, dibujar grafos si es muy útil para entender y demostrar algunas propiedades, para tener intuición sobre ellos. Entendemos que lo relevante de esos gráficos no es si un vértice está dibujado más arriba o más abajo, sino que vértices están conectados por aristas.
