Hola, como están? Tengo una dudad sobre unos ejercicios que me dicen que:
a) de la definición de gráficas homeomorfas, es distinto a gráficas homomorfas???, porque en el libro que uso sólo sale la definición siguiente:
)La gráfica \( G_1 \) y \( G_2 \) son un homomorfismo si \( G_1 \) y \( G_2 \) se pueden reducir a gráficas isomorfas mediante una secuencia de reducciones de seri
e.
Pero en wilkipedia encontré la definición de grafo homeomorfo que es:
*)Dos grafos \( G_1 \) y \( G2 \) son homeomorfos si ambos pueden obtenerse a partir del mismo grafo con una sucesión de subdivisiones elementales de aristas.
Lo que yo entiendo es que si es homomorfismo se pueden sacar vértices y aristas reduciendo, pero un homeomorfismo se agregan aristas y vértices?
b)Además me piden una condición necesaria y suficiente para que una gráfica no sea plana, sería que una gráfica no es plana si y sólo si al menos 2 aristas de la gráfica se cruzan.
c) Me dice que muestre, usando la relación de Euler, que un árbol es un grafo plano, lo que no sé es cuál es la relación de Euler, porque no me han enseñado??
d) Me piden que demuestre que si una gráfica simple \( G \) tiene 11 vértices o más entonces una de las dos, \( G \) o \( \bar{G} \) no es plana. , me está diciendo que \( \bar{G} \) sería una subgráfica???
e)Existen gráficas no conexas planas? Sí?
Muchas gracias.