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 {\displaystyle C_{4}}$
$C_{4}$
$C 5 {\displaystyle C_{5}}$
$C_{5}$
$C 6 {\displaystyle C_{6}}$
$C_{6}$

Datos: Q584521

Este artículo ha sido escrito por Wikipedia. El texto está disponible bajo la licencia Creative Commons - Atribución - CompartirIgual. Pueden aplicarse cláusulas adicionales a los archivos multimedia.