Homeomorfismo de grafos

Homeomorfismo de grafos

Este término no debe confundirse con isomorfismo de grafos.


En Teoría de grafos, decimos que dos grafos G1 y G2 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 homemorfismo: 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 C4 se obtiene un C5. Finalmente, si al C5 se le aplica nuevamente una subdivisión elemental se logra el C6. Como tanto C5 y C6 se obtuvieron de C4 se dice que C5 es homeomorfo a C6 y se nota C_5 \cong_H C_6



Wikimedia foundation. 2010.

Игры ⚽ Поможем сделать НИР

Mira otros diccionarios:

  • Teoría de grafos — Diagrama de un grafo con 6 vértices y 7 aristas. En matemáticas y en ciencias de la computación, la teoría de grafos (también llamada teoría de las gráficas) estudia las propiedades de los grafos (también llamadas gráficas). Un grafo es un… …   Wikipedia Español

  • Topología — Para otros usos de este término, véase Topología (desambiguación). Ilustración del Teor …   Wikipedia Español

Compartir el artículo y extractos

Link directo
Do a right-click on the link above
and select “Copy Link”