Teoría de grafos topológicos - Topological graph theory
En matemáticas , la teoría de grafos topológicos es una rama de la teoría de grafos . Estudia la incrustación de gráficos en superficies , incrustaciones espaciales de gráficos y gráficos como espacios topológicos . También estudia inmersiones de gráficos.
Incrustar un gráfico en una superficie significa que queremos dibujar el gráfico en una superficie, una esfera, por ejemplo, sin dos bordes que se crucen. Un problema de incrustación básico que a menudo se presenta como un rompecabezas matemático es el problema de las tres cabañas . Se pueden encontrar otras aplicaciones en la impresión de circuitos electrónicos donde el objetivo es imprimir (incrustar) un circuito (el gráfico) en una placa de circuito (la superficie) sin que dos conexiones se crucen entre sí y provoquen un cortocircuito .
Gráficos como espacios topológicos
A un gráfico no dirigido podemos asociar un complejo simplicial abstracto C con un conjunto de un solo elemento por vértice y un conjunto de dos elementos por borde. La realización geométrica | C | del complejo consiste en una copia del intervalo unitario [0,1] por borde, con los puntos finales de estos intervalos pegados en los vértices. En este punto de vista, las incrustaciones de gráficos en una superficie o como subdivisiones de otros gráficos son instancias de incrustaciones topológicas, el homeomorfismo de los gráficos es solo la especialización del homeomorfismo topológico , la noción de un gráfico conectado coincide con la conectividad topológica y un gráfico conectado es un árbol si y solo si su grupo fundamental es trivial.
Otros complejos simpliciales asociados con gráficos incluyen el complejo Whitney o complejo clique , con un conjunto por clique del gráfico, y el complejo de emparejamiento , con un conjunto por emparejamiento del gráfico (de manera equivalente, el complejo clique del complemento del gráfico de líneas ) . El complejo de emparejamiento de un gráfico bipartito completo se denomina complejo de tablero de ajedrez , ya que también se puede describir como el complejo de conjuntos de torres que no atacan en un tablero de ajedrez.
Estudios de ejemplo
John Hopcroft y Robert Tarjan obtuvieron un medio para probar la planaridad de un gráfico en el tiempo lineal al número de aristas. Su algoritmo hace esto mediante la construcción de un gráfico incrustado que denominan "palmera". La prueba de planaridad eficiente es fundamental para dibujar gráficos .
Fan Chung y col. estudió el problema de incrustar una gráfica en un libro con los vértices de la gráfica en una línea a lo largo del lomo del libro. Sus bordes están dibujados en páginas separadas de tal manera que los bordes que residen en la misma página no se crucen. Este problema abstrae los problemas de diseño que surgen en el enrutamiento de placas de circuito impreso multicapa.
Las incrustaciones de gráficos también se utilizan para probar resultados estructurales sobre gráficos, a través de la teoría menor de gráficos y el teorema de la estructura del gráfico .
Ver también
- Número de cruce (teoría de grafos)
- Género
- Gráfico plano
- Arbol real
- Gráfico toroidal
- Combinatoria topológica
- Gráfico de voltaje