Homeomorfismo de grafos

No debe confundirse con homomorfismo de grafos o isomorfismo de grafos.

En Teoría de grafos, se dice que dos grafos ${\displaystyle G_{1}}$ y ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle C_{4}}$  se obtiene un ${\displaystyle C_{5}}$ . Finalmente, si al ${\displaystyle C_{5}}$  se le aplica nuevamente una subdivisión elemental se logra el ${\displaystyle C_{6}}$ . Como tanto ${\displaystyle C_{5}}$  y ${\displaystyle C_{6}}$  se obtuvieron de ${\displaystyle C_{4}}$  se dice que ${\displaystyle C_{5}}$  es homeomorfo a ${\displaystyle C_{6}}$  y se nota ${\displaystyle C_{5}\cong _{H}C_{6}}$ 

•  

  ${\displaystyle C_{4}}$ 

•  

  ${\displaystyle C_{5}}$ 

•  

  ${\displaystyle C_{6}}$ 

•   Datos: Q584521