Teoría de grafos topológica
En matemáticas, la teoría de grafos topológicos es una rama de la teoría de grafos. Estudia el embebido de grafos en superficies, el embebido espacial de grafos y los propios grafos como espacios topológicos.[1] También estudia las inmersiones de grafos.
Embeber (o también "incrustar") un grafo en una superficie significa dibujar el grafo sobre una superficie, como una esfera por ejemplo, sin que dos enlaces del grafo se crucen entre sí. Un problema de embebido básico que a menudo se presenta como un puzzle matemático es el problema de los tres servicios. Se pueden encontrar otras aplicaciones en la impresión de circuitos electrónicos, donde el objetivo es imprimir (embeber) un circuito (el grafo) en un circuito impreso (la superficie) sin que dos conexiones se crucen entre sí y den como resultado un cortocircuito.
Grafos como espacios topológicos
editarA un grafo se le puede asociar un complejo simplicial abstracto C con un conjunto de un solo elemento por vértice y un conjunto de dos elementos por arista.[2] La realización geométrica |C| del complejo consta de una copia de intervalo unidad [0,1] por arista, con los extremos de estos intervalos pegados en los vértices. Desde este punto de vista, los embebidos de grafos en una superficie o las subdivisiones de otros grafos son instancias de embebidos topológicos, siendo el homeomorfismo de grafos la aplicación del concepto de homeomorfismo al campo topológico, donde la noción de conectividad coincide con el concepto de continuidad topológica, y un grafo conectado es un árbol si y solo si su grupo fundamental es trivial.
Otros complejos simpliciales asociados con grafos incluyen el complejo de Whitney o complejo clique, con un conjunto por clique del grafo, y el complejo de coincidencia, con un conjunto por emparejamiento del grafo (equivalentemente, el complejo clique del complemento del grafo línea). El complejo de emparejamiento de un grafo 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 se atacan entre sí en un tablero de ajedrez.[3]
Estudios de ejemplo
editarJohn Hopcroft y Robert Tarjan[4] obtuvieron un medio para comprobar la planitud de un grafo en tiempo lineal con respecto al número de enlaces. Su algoritmo hace esto mediante la construcción de un grafo embebido que denominan palmera. La prueba de planaridad eficiente es fundamental para el dibujo de grafos.
Fan Chung et al[5] estudiaron el problema del embebido de un grafo en un libro con los vértices del grafo situados en una línea recta coincidente con el lomo del libro. Sus líneas de enlace se dibujan en páginas separadas de tal manera que los bordes que residen en la misma página no se cruzan en ningún caso. Este procedimiento permite dar un enfoque abstracto a los problemas de diseño que surgen en el enrutamiento de placas de circuito impreso multicapa.
Los grafos embebidos también se utilizan para probar resultados estructurales sobre grafos, a través de la teoría del grafo menor y del teorema de la estructura del grafo.
Véase también
editarReferencias
editar- ↑ J.L. Gross and T.W. Tucker, Topological graph theory, Wiley Interscience, 1987
- ↑ Graph Topology, from PlanetMath.
- ↑
- ↑ Hopcroft, John; Tarjan, Robert E. (1974). «Efficient Planarity Testing». Journal of the ACM 21 (4): 549-568. S2CID 6279825. doi:10.1145/321850.321852. hdl:1813/6011.
- ↑ Chung, F. R. K.; Leighton, F. T.; Rosenberg, A. L. (1987). «Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design». SIAM Journal on Algebraic and Discrete Methods 8 (1): 33-58. doi:10.1137/0608002.
Datos: Q4115842
