Hay algo importante que hay que tener en cuenta al estudiar los gráficos: la definición de gráfico. En realidad, hay algunas desviaciones en la forma en que se puede definir un gráfico, pero ésta será suficiente para nuestros propósitos:
A (simple) gráfico $G$ es un par ordenado del conjunto $(V, E)$ (los conjuntos de vértices y bordes respectivamente), donde $E$ consiste en subconjuntos de $V$ de cardinalidad $2$ .
Cuando el gráfico es finito (es decir $V$ y por lo tanto $E$ es un conjunto finito), podemos representar visualmente un gráfico mediante un diagrama, asignando a cada punto de $V$ a un punto distinto en $\Bbb{R}^2$ (u ocasionalmente, $\Bbb{R}^3$ ). Si $\{u, v\} \in E$ entonces trazamos una trayectoria desde el punto que representa $u$ al punto que representa $v$ , no pasando por ningún otro punto que represente un punto en $V$ .
Estos diagramas son lo que a menudo decimos a la gente que son "gráficos", pero en realidad son sólo una forma de representar gráficos. El primer diagrama representa la gráfica: $$G_1 = (\{e_1, e_2, e_3, e_4, e_5\},\{\{e_1, e_2\},\{e_2, e_3\}, \{e_3, e_4\}, \{e_4, e_5\}, \{e_5, e_1\}\}).$$ El segundo diagrama representa el gráfico: $$G_2 = (\{c_1, c_4, c_2, c_5, c_3\},\{\{c_1, c_4\},\{c_4, c_2\}, \{c_2, c_5\}, \{c_5, c_3\}, \{c_3, c_1\}\}).$$ (Obsérvese la forma principal en que he decidido ordenar los elementos de mis conjuntos al definir $G_2$ !)
Obsérvese que, si tomamos la foto de $G_1$ y, digamos, la giramos (manteniendo todas las etiquetas), entonces esa imagen representaría el mismo gráfico $G_1$ . No es algo isomorfo a $G_1$ Me refiero a que tendría exactamente los mismos conjuntos de vértices y aristas, es decir, el gráfico que representa sería literalmente $G_1$ aunque sea una foto nueva. Incluso puedes empezar a mover los vértices independientemente unos de otros (de nuevo, manteniendo las mismas etiquetas), y el diagrama seguirá representando $G_1$ .
De este modo, vemos que hay una enorme variedad de diagramas para representar exactamente el mismo gráfico.
Además, es posible que varios gráficos produzcan el mismo diagrama (excepto con diferentes etiquetas en los vértices). Si se dibuja, por ejemplo $G_2$ con $c_1$ en la misma posición que $e_1$ , $c_4$ donde $e_2$ era, $c_2$ donde $e_3$ era, $c_5$ donde $e_4$ era, y $c_3$ donde $e_5$ y conectando los vértices adyacentes con segmentos de línea, resultaría el mismo diagrama que el de $G_1$ con diferentes etiquetas.
En este sentido, vemos que $G_1$ y $G_2$ son estructuralmente el mismo gráfico, aunque no compartan vértices ni aristas. Así, las imágenes introducen una variedad innecesaria al confundir las posiciones de los vértices, y la definición de conjunto de los grafos introduce una variedad innecesaria al permitir sustituciones de etiquetas que no afectan a la estructura real del grafo. ¿Cómo podemos hablar de que dos grafos son iguales, de forma que no se produzca un falso negativo cuando se mueven los puntos o se les cambia el nombre?
Entra, a la izquierda del escenario, el concepto de isomorfismo de un gráfico. Si tenemos grafos $(V_1, E_1)$ y $(V_2, E_2)$ un isomorfismo del grafo es una biyección $f : V_1 \to V_2$ con la propiedad de que $\{v, w\} \in E_1 \iff \{f(v), f(w)\} \in E_2$ . Por lo tanto, la función preserva la adyacencia.
Dos grafos son "iguales" cuando existe un isomorfismo entre ellos. El isomorfismo se refiere únicamente a la definición de conjunto de los grafos (y, por tanto, no le importa cómo se dibujen), pero seguirá existiendo aunque se cambie el nombre de los vértices. Por lo tanto, podemos ver que $G_1$ y $G_2$ son isomorfas, con un isomorfismo como el descrito anteriormente. La forma en que escribí $G_1$ y $G_2$ también expone claramente este isomorfismo.
¿Cómo puedes saber que el otro par de gráficos no es isomorfo? Creo que Travis lo explica bien en su respuesta. En el gráfico de la derecha, hay tres vértices, por ejemplo $b, c, d$ , tal que cualquier par de ellas es una arista en el grafo, es decir $\{b, c\}, \{c, d\}, \{b, d\}$ son elementos del conjunto de bordes. Si un isomorfismo $f$ existía, tendría que haber puntos $f(b), f(c), f(d)$ tal que $\{f(b), f(c)\}, \{f(c), f(d)\}, \{f(b), f(d)\}$ . No hay tales puntos $f(b), f(c), f(d)$ existen en el primer grafo (mediante una búsqueda exhaustiva rápida), por lo que no existe ningún isomorfismo. Esto implica que no hay manera de reordenar los vértices de un diagrama (y cambiar sus etiquetas) para formar el otro diagrama.
Resumen (o tl;dr):
- Los gráficos se definen mediante conjuntos, no mediante imágenes.
- El mismo gráfico puede dibujarse de muchas maneras, así que no te distraigas porque los vértices se mueven.
- A los isomorfismos no les importan los nombres de los vértices ni sus posiciones.
- Para ver por qué el primer par es isomorfo, pero el segundo par no lo es, véase la respuesta de Travis.
Y estos dos no son isomórfico: 
0 votos
Los dos que no son isomorfos, no están conectados de la misma manera
2 votos
En primer lugar, ¿tienes clara la definición de isomorfo?
1 votos
Todas las propiedades intrínsecas (como los grados de los vértices, la longitud de los ciclos y demás) son iguales en los grafos isomórficos. Las propiedades extrínsecas (como si las líneas se cruzan, los nombres de los vértices y el grado del vértice superior) no son necesariamente las mismas.
0 votos
@Ultradark Aunque ninguno parece estar conectado de la misma manera. Las aristas son diferentes, de lo contrario se verían idénticas, ¿no? Es decir, una estrella no es un pentágono, y dos líneas paralelas (=) no son lo mismo que una cruz (×). ¿Qué me falta?
0 votos
@Mike Yo pensaba que sí, pero supongo que no.
0 votos
Normalmente, para determinar si dos gráficos son isomorfos, se puede intentar encontrar un mapeo del conjunto de vértices de un gráfico al conjunto de vértices del otro, de forma que la estructura del gráfico permanezca inalterada. O bien se puede intentar encontrar una diferencia entre dos grafos, que demuestre que no son isomorfos. El primer par de grafos del artículo es isomorfo porque se pueden asignar los vértices del segundo grafo a los del primero de forma que ambos grafos son un ciclo de 5 $C_5$ . El segundo par de gráficos no es isomorfo, ya que el segundo de ellos tiene un ciclo de 3 (es decir, un "triángulo"), mientras que el primero no.
0 votos
Por cierto, no sé por qué utilizan el primer par de gráficos del artículo como ejemplo. Cada uno de ellos tiene 2 vértices con el mismo nombre?
2 votos
No está utilizando definiciones. Dos cosas son isomorfas dado un isomorfismo, pero no das ninguna. A falta de una, el sentido común sugiere que "isomorfo" significa para algún isomorfismo de un tipo determinado. En el caso de los gráficos, "isomorfo" supone un determinado tipo de isomorfismo. Estás utilizando mal descripciones que son demasiado vagas para ser definiciones. Usted cita MathWorld, pero el descripción introductoria explícitamente informal no la definición. Busca definiciones formales de "isomorfismo" e "isomorfo". También pareces confundir la imagen de un gráfico con el gráfico que representa. Busca una definición formal de "gráfico".
0 votos
@philipxy Estudio informática, pero no soy matemático. Elijo las descripciones que puedo entender. Para mí, el resto bien podría estar escrito en un lenguaje alienígena. Intento simplificar el concepto aquí, no complicarlo. Explícamelo como si tuviera cinco años.
6 votos
Las palabras tienen significado. Hay que aprenderlas. No hay camino real. "Explicar como si tuviera cinco años" lo dice la gente que no está dispuesta a esforzarse por entender las presentaciones que ya encontró. Este post sólo pregunta, qué significa que dos gráficos sean isomorfos, sin ningún esfuerzo de investigación--ver los textos de la flecha de votación del ratón. Si estás atascado en alguna(s) presentación(es) deberías preguntar dónde estás atascado, no pedir otra más. Citas paráfrasis que son claramente de su contexto no definiciones. Son inútiles. Si no lo sabías ya, ahora lo sabes.
2 votos
Digamos que @philipxy tiene toda la razón. La primera frase del artículo de MathWorld no es más que un intento de brillo del significado del isomorfismo del grafo, y no una declaración precisa. La definición precisa se da en el segunda frase que ni siquiera has citado en tu pregunta.
2 votos
Y francamente, pedir a la gente que te lo explique como si tuvieras cinco años me parece una grosería, aunque quizás no lo hayas hecho con mala intención. La razón es que también podrías pedirle a la gente que te lo explique como si tuvieras dos años, o como si fueras su abuela, o alguna otra restricción artificial. Todo concepto o prueba matemática tiene una "complejidad" mínima, y sería tonto e inútil intentar simplificarla más allá de eso. Aprende a reconocer y apreciar la profundidad y la complejidad de las matemáticas, en lugar de menospreciarlas como si los niños de 5 años pudieran entenderlas todas.
0 votos
Hola. ¿Qué quieres decir con "gráfico"? Citas una vaga paráfrasis sin definición. Si no sabes lo que es un grafo, ¿por qué no lo preguntas primero, y por qué incluso preguntas re lo que significa que dos de ellos sean isomorfos? Además citas otras fuentes que definir grafo y grafos isomorfos, así que ¿por qué no preguntas por esas definiciones? (Preguntas no retóricas.) (Si quieres saber lo que la fuente de la cita de la "gráfica" está tratando de comunicar--la escritura es basura, así que esa es una buena pregunta. Si esa es tu pregunta, hazla. Pero investiga primero sobre "grafo" y "grafos isomórficos").
0 votos
Su último comentario ha sido borrado porque ha sido excesivamente grosero. Por favor, absténgase de volver a hacerlo. En mi comentario anterior, expliqué en un lenguaje sencillo que no todo en las matemáticas puede hacerse lo suficientemente simple para que lo entiendas, y que necesitas aprender más antes de que ciertas cosas sean accesibles para ti. Es tu elección si quieres aprender matemáticas correctamente o no. Si no lo haces, he terminado aquí.
0 votos
P.D. Tal vez quieras buscar en Google "teoría de grafos para (niños O chicos)". Acabo de hacerlo. (Porque sospecho que esta pregunta puede responderse para un niño de 5 años. Definitivamente para un niño de n años para algún n relevantemente pequeño. Excepto que no esperaría que las definiciones necesarias fueran muy diferentes de las de MathWorld).
4 votos
Voto por cerrar esta pregunta porque no creo que se trate de matemáticas tal y como está redactado actualmente. Para que se trate de matemáticas, los objetos que se describen deben estar rigurosamente definidos. Por ejemplo, los términos "grafo" e "isomorfismo de grafos" no se han definido correctamente.
0 votos
Para responder a tu pregunta de forma sencilla, imagina que tienes una goma elástica con la forma del primer gráfico. Ahora sabes que puedes estirar, doblar, retorcer la goma elástica de tal manera que forme la forma de una estrella. Ahora imagina que tienes una goma elástica con la forma de la segunda situación, por mucho que lo intentes nunca podrás conseguir que se parezca al otro gráfico. Intuitivamente, se puede pensar en esta forma de ser isomorfo, aunque no en todos los casos, por ejemplo, en los grafos dirigidos.