Homeomorfismo de grafos

En Teoría de grafos, se dice que dos grafos $G_{1}$ y $G_{2}$ son homeomorfos si ambos pueden obtenerse a partir de un mismo grafo por una sucesión de subdivisiones elementales de aristas. Suele notarse por $G_{1}\cong _{H}G_{2}$.

Este concepto, de naturaleza combinatoria, está relacionado con el concepto topológico de homeomorfismo: cualquier grafo puede representarse como un espacio topológico en que cada vértice queda representado por un punto distinto y cada arista por un arco homeomorfo con el intervalo [0,1]. Dos grafos son homeomorfos en el sentido de la teoría de grafos si y solo si lo son como espacios topológicos.

Ejemplo

Todos los grafos ciclo de n vértices son homeomorfos entre sí. Por ejemplo, si se hace una subdivisión elemental de algún vértice de $C_{4}$ se obtiene un $C_{5}$. Finalmente, si al $C_{5}$ se le aplica nuevamente una subdivisión elemental se logra el $C_{6}$. Como tanto $C_{5}$ y $C_{6}$ se obtuvieron de $C_{4}$ se dice que $C_{5}$ es homeomorfo a $C_{6}$ y se nota $C_{5}\cong _{H}C_{6}$

• 
  $C_{4}$
• 
  $C_{5}$
• 
  $C_{6}$

• Datos: Q584521