Homeomorfismo de grafos

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

En Teoría de grafos, decimos 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[editar]

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