Teoria de grafos topològica
Archiu:Pappus-graph-animation.webm
En matemàtiques, la teoria de grafos topològics és una branca de la teoria de grafos. Estudia l'embebido de grafos en superfícies, l'embebido espacial de grafos i els propis grafos com espais topològics.[1] També estudia les immersions de grafos.
Embeber (o també "incrustar") un grafo en una superfície significa dibuixar el grafo sobre una superfície, com una esfera per eixemple, sense que dos enllaços del grafo es creuen entre sí. Un problema de embebido bàsic que a sovint es presenta com un puzle matemàtic és el problema dels tres servicis. Es poden trobar atres aplicacions en l'impressió de circuits electrònics, a on l'objectiu és imprimir (embeber) un circuit (el grafo) en un circuit imprés (la superfície) sense que dos conexions es creuen entre sí i donen com resultat un curtcircuit.
Grafos com a espais topològics
[editar | editar còdic]A un grafo se li pot associar un complex simplicial abstracte C en un conjunt d'un sol element per vèrtiç i un conjunt de dos elements per aresta.[2] La realisació geomètrica |C| del complex consta d'una còpia d'interval unitat [0,1] per aresta, en els extrems d'estos intervals pegats en els vèrtiços. Des d'este punt de vista, els embebidos de grafos en una superfície o les subdivisions d'atres grafos són instàncies de embebidos topològics, sent el homeomorfisme de grafos l'aplicació del concepte d'homeomorfisme al camp topològic, a on la noció de conectivitat coincidix en el concepte de continuïtat topològica, i un grafo conectat és un arbre si i solament si el seu grup fonamental és trivial.
Atres complexos simpliciales associats en grafos inclouen el complex de Whitney o complex clique, en un conjunt per clique del grafo, i el complex de coincidència, en un conjunt per emparejamiento del grafo (equivalentemente, el complex clique del complement del grafo llínea). El complex de emparejamiento d'un grafo bipartito complet es denomina complex de tauler d'escacs, ya que també es pot descriure com el complex de conjunts de torres que no s'ataquen entre sí en un tauler d'escacs.[3]
Estudis d'eixemple
[editar | editar còdic]John Hopcroft i Robert Tarjan[4] varen obtindre un mig per a comprovar la planitud d'un grafo en temps llineal sobre el número d'enllaços. El seu algoritme fa açò per mig de la construcció d'un grafo embebido que denominen palmera. La prova de planaridad eficient és fonamental per al dibuix de grafos.
Fan Chung et a el[5] varen estudiar el problema del embebido d'un grafo en un llibre en els vèrtiços del grafo situats en una llínea recta coincidente en el llom del llibre. Les seues llínees d'enllaç es dibuixen en pàgines separades de tal manera que les vores que residixen en la mateixa pàgina no es creuen en cap cas. Este procediment permet donar un enfocament abstracte als problemes de disseny que sorgixen en el enrutamiento de plaques de circuit imprés multicapa.
Els grafos embebidos també s'utilisen per a provar resultats estructurals sobre grafos, a través de la teoria del grafo menor i del teorema de l'estructura del grafo.
Vore també
[editar | editar còdic]- Número de creuament (teoria de grafos)
- Genus
- Grafo pla
- Arbre real
- Grafo toroidal
- Combinatoria topològica
- Grafo de voltage
Referències
[editar | editar còdic]- ↑ J.L. Gross and T.W. Tucker, Topological graph theory, Wiley Interscience, 1987
- ↑ Graph Topology, from PlanetMath.
- ↑ Plantilla:Cite arXiv
- ↑ “Efficient Planarity Testing” (1974). Journal of the ACM 21 (4): 549–568. doi:.
- ↑ “Embedding Graphs in Books: A Layout Problem with Applications to VLSI Design” (1987). SIAM Journal on Algebraic and Discrete Methods 8 (1): 33–58. doi:.
Referències
[editar | editar còdic]
- Este artícul conté una traducció derivada de «Teoría de grafos topológica» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.