Incrustación de gráficos

En la teoría de grafos topológica , una incrustación (también escrito imbedding ) de un gráfico en una superficie es una representación de sobre en el que puntos de están asociados con vértices y arcos simples ( homeomórficos imágenes de ) están asociados con los bordes de una manera tal que:${\ Displaystyle G}$ ${\ Displaystyle \ Sigma}$${\ Displaystyle G}$${\ Displaystyle \ Sigma}$${\ Displaystyle \ Sigma}$${\ Displaystyle [0,1]}$

Aquí una superficie es un compacto , conectado - colector .${\ Displaystyle 2}$

De manera informal, una incrustación de un gráfico en una superficie es un dibujo del gráfico en la superficie de tal manera que sus bordes pueden cruzarse solo en sus puntos finales. Es bien sabido que cualquier gráfico finito puede incrustarse en un espacio euclidiano tridimensional . ^[1] Un gráfico plano es aquel que se puede incrustar en un espacio euclidiano bidimensional.${\ Displaystyle \ mathbb {R} ^ {3}}$${\ Displaystyle \ mathbb {R} ^ {2}.}$

A menudo, una incrustación se considera una clase de equivalencia (bajo homeomorfismos de ) de representaciones del tipo que se acaba de describir.${\ Displaystyle \ Sigma}$

Algunos autores definen una versión más débil de la definición de "incrustación de gráficos" omitiendo la condición de no intersección para los bordes. En tales contextos, la definición más estricta se describe como "incrustación de gráficos no cruzados". ^[2]

Este artículo se ocupa únicamente de la definición estricta de incrustación de gráficos. La definición más débil se analiza en los artículos " dibujo de gráfico " y " número de cruce ".

El gráfico de Heawood y el mapa asociado incrustados en el toro.