En mi clase me dieron algunas condiciones necesarias para que dos gráficos sean isomórficos, estos dos gráficos los satisfacen todos pero yo no Piensa en son isomórficos:
Las secuencias de grados son iguales.
La misma cantidad de vértices/bordes.
$G$ es bipartita $ \iff H$ es bipartita.
¿Hay alguna forma metódica (rápida) de resolver este tipo de preguntas?
Mira los cuatro vértices de grado $3$ en cada gráfico: en $G$ cada uno de ellos es adyacente a dos de los otros, mientras que en $H$ cada uno de ellos es adyacente a uno solo de los otros. Como alternativa, en $G$ forman un $4$ -ciclo, mientras que en $H$ no lo hacen.
Otro enfoque: si los quitas de $G$ Lo que queda es este gráfico, con dos componentes.
*----*
*----*Si los quitas de $H$ lo que queda es un gráfico con $4$ vértices y ninguna arista, una con $4$ componentes.
¡Muchas gracias! Entiendo tu método de borrar todos los vértices con grado $n$ si generalizo esto, ¿se sostiene que $G \simeq H \iff G-\{\text{vertices of degree n}\} \simeq H-\{\text{vertices of degree n}\}$ ?
En general, este problema se conoce como problema de isomorfismo de grafos y es muy difícil de resolver.
En este caso especial se puede demostrar con relativa facilidad. El gráfico de la izquierda tiene un camino formado por 3 vértices distintos de grado 3, pero el gráfico de la derecha no tiene esta propiedad.
Otra diferencia más: En G, puedes eliminar un par de vértices adyacentes para desconectar el gráfico. Sin embargo, el gráfico H no tiene esta propiedad.
¿Recuerdas el viejo chiste de "cómo llego al Carnegie Hall"? "¡Practica, practica, practica!" ? Lo mismo se aplica aquí. Buscas una propiedad que tiene un gráfico que no tiene el otro, y cuantas más propiedades conozcas y más práctica tengas, más fácil será.
Como se ha sugerido en otras respuestas, en general para intentar demostrar que dos grafos NO son isomorfos basta con encontrar algunas condiciones invariantes, por ejemplo en términos de recuentos de vértices de varios grados y recuentos de sus vecinos de varios grados y recuentos de caminos a través de vértices de diferentes grados, etc. Para demostrar que dos grafos SON isomorfos no hay básicamente ningún método rápido conocido, pero se puede limitar la búsqueda del isomorfismo correcto utilizando las restricciones señaladas anteriormente.
En el caso de tus dos grafos, aquí tienes ejemplos de cómo ver que no son isomorfos (similares a otras respuestas). Una forma es contar el número de vértices de grado 3 que tienen 2 vecinos también de grado 3. En tu primer gráfico la respuesta es 4, y en el segundo gráfico la respuesta es 0. También puedes contar cuántos caminos sencillos de longitud 3 pasan sólo por nodos de grado 3. En el primer gráfico puedes encontrar uno, pero en el segundo no. En el primer gráfico puedes encontrar uno, pero en el segundo no.
$G$ es hamiltoniano (tiene un ciclo que utiliza cada vértice una vez) y $H$ no lo es.
Para ver el segundo punto, $H$ tiene varios vértices de grado $2$ . Cualquier ciclo de Hamilton debe utilizar todas las aristas de estos vértices. Pero esas aristas forman un par de $4$ -y no pueden formar parte de un ciclo en todos los vértices.
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
