Grafo isomorfo

Universidad Autonoma de Queretaro
Facultad de Informatica

Matematicas Computacionales

Preguntas sobre Grafos

Jorge Luis Ruiz Ramirez
180275
SOF07

¿Qué es un grafo isomorfo?  Dosgrafos son isomorfos cuando existe una correspondencia biunívoca (uno a uno), entre sus vértices de tal forma que dos de estos quedan unidos por una arista en común.
¿Cómo probarlo? Buscando una funciónbiyectiva que convierta los vértices de uno en otro, preservando la estructura de las aristas

Definición: Dos grafos G=(V,A), G’=(V’,A’) son isomorfos si existe una función biyectiva f:VV’ tal que{a,b}A {f(a),f(b)}A’
¿como saber si dos grafos no son isomorfos?
Hay que buscar alguna característica que diferencie la estructura de los dos grafos, como por ejemplo:
* Distinto número devértices o de aristas
* Distinto número de ciclos de una longitud dada
* Distinto número de vértices con un mismo grado n
* Aristas conectando vértices con dos grados tales que noexistan aristas de las mismas características en el otro grafo
Cuál es la diferencia entre un camino y un recorrido en un grafo?
Un recorrido de un grafo es una manera sistematica de explorar susvertices siguiendo la estructura del grafo. Los recorridos dan lugar a esquemas para el tratamiento de grafos. Varias preguntas sobre grafos (como por ejemplo saber si un grafo es conexo o no) puedenresolverse mediante recorridos. En un recorrido puede aplicarse una determinada operacion en cada visita. Nosotros nos centraremos en generar una secuencia de los vertices en el orden en el que sevisitan (igual que se habıa hecho para arboles).
Tanto en los grafos dirigidos como en los no dirigidos las secuencias de vertices pueden formar caminos y ciclos. Definimos un camino de longitud como unasecuencia de vertices u0, u1, . . . , u tales que, para todo i tal que 1 ≤ i ≤ `, (ui−1, ui) ∈ E (si se trata de un digrafo) o {ui−1, ui} ∈ E (si se trata de un grafo). Un camino es simple si todos...