En teoria de grafs, el test de planaritat és un problema que consisteix en demostrar si un graf és pla, és a dir, si pot ser dibuixat a un pla sense que hi hagi interseccions entre les arestes. Es tracta d'un problema molt estudiat en ciències computacionals i per això té molts de possibles algorismes i optimitzacions, sovint relacionades amb la implementació de nous tipus d'estructures de dades. La majoria d'aquests mètodes operen en O(n) (temps lineal), on n és el nombre d'arestes o bé de vèrtexs del graf. En lloc d'un simple valor booleà (cert/fals), és preferible que el resultat de l'algorisme sigui una distribució planar del graf sempre que aquesta sigui possible, o bé una identificació dels obstacles de la planaritat, és a dir els subgrafs no planars. Tot i això, si un algorisme troba un subgraf no planar pot estar segur de que el resultat final no és planar i retornar-ho sense computacions addicionals.
Els tests de planaritat utilitzen teoremes i criteris que caracteritzen la planaritat d'un graf.
Teorema de Kuratowski
|
Una subdivisió del graf és un graf format al subdividir les arestes a rutes d'una o més arestes. El teorema de Kuratowski estipula que un graf G és pla si no és possible subdividir les arestes de K₅ o K3,3 i després possiblement afegir arestes i vèrtexs addicionals, per obtenir un graf isomòrfic a G. De la mateixa manera, un graf G és pla si i només si no conté un subgraf H homeomòrfic a K₅ o K3,3. A aquest subgraf H se l'anomena subgraf de Kuratowski.[2] Kuratowski també va demostrar que subdividir o escurçar un graf no en canvia la planaritat.[3] La fórmula d'Euler permet demostrar que K₅ i K3,3 no són planars, per tant qualsevol graf que els inclou no és planar.[4] Habitualment, grafs no planars contenen un gran nombre de subgrafs de Kuratowski. És possible extreure un gran nombre de subgrafs de Kuratowski en temps lineal.[5] El teorema ha estat demostrat de diverses maneres.[6][7][8]
Teorema de Wagner
|
Si un graf és planar, també ho són tots els seus subgrafs: Eliminar vèrtexs i arestes no pot fer que un graf planar deixi de ser-ho. Descrivim un graf no planar minimal com aquell graf el qual tot i no ser planar al eliminar qualsevol vèrtex o aresta, passa a ser-ho. Una altra manera d'entendre el teorema de Wagner per tant és que només hi ha dos grafs no planars minimals; K₅ i K3,3. En certa manera el teorema de Kuratowski forma part del teorema de Wagner, ja que una subdivisó pot ser convertida a un subgraf del mateix tipus al contreure tots els eixos menys un en cada ruta formada pel procés de subdivisió, però en canvi convertir un subgraf a una subdivisió del mateix tipus no sempre és possible. Tot i això, en el cas del dos grafs K₅ i K3,3, és trivial demostrar que almenys un d'aquests dos grafs com a subgraf també en té un d'ells com a subdivisió, per tant tots dos teoremes són equivalents.[10]
El teorema pot ser reformulat d'aquesta manera: tot graf no planar pot ser descompost en peces més simples. Aquesta idea és la precursora del teorema estructural de grafs[11] i el teorema de Robertson-Seymour[12] Anàlegs del teorema de Wagner també són utilitzats en la teoria de matroides.[13]
Criteri de planaritat de Fraysseix-Rosenstiehl
Es caracteritzen els grafs en termes d'ordenament dreta-esquerra de les arestes en un arbre de cerca en profunditat (Depth-first search).
Donat un graf G, definim un arbre T de cerca de profunditat al dibuixar les arestes trobades quan es descobreix un vèrtex per primera vegada. Això forma un arbre de Trémaux, és a dir, les arestes restants connecten un parell de vèrtexs que estan relacionats entre ells com a ancestre i descendent en T. Per tant, aquestes connexions o frondes no poden entrecreuar diferents branques de l'arbre.
Podem definir cada parell de frondes com T-similars si es troben al mateix costat de la branca, o T-oposades si es troben a costats oposats.
|
Altres criteris
- Criteri de planaritat de Whitney:
|
Donat un graf G=(V,E), ha d'existir un altre graf (dual) G'=(V',E') i una correspondència entre les arestes E' i E de tal manera que un subgrup T de E formi un arbre d'expansió de G si i només si les arestes corresponents al subgrup complementari E-T formen un arbre d'expansió de G'. Per tant, G és planar si i només si existeix un graf dual que té un matroide dual al matroide de G. G' també s'anomena el dual algebraic de G, per tant el criteri de Whitney pot ser descrit simplement: Un graf és planar si i només si té un dual algebraic.[14]
- Criteri de planaritat de Mac Lane:
Es caracteritzen els grafs per les bases dels seus espais de cicles binaris.
|
Per cada cicle c en un graf G, es pot formar un vector m-dimensional 0-1 que té un 1 a les coordenades de posició corresponents a les arestes en c, i un 0 en la resta de coordenades de posició. L'espai de cicle C(G) del graf és el vector format per totes les combinacions lineals possibles de vectors formades en aquesta via. La 2-base de G és una base de C(G) amb la propietat que, per cada aresta E de G, com a molt dos vectors base tenen coordenades diferents a 0 en la posició corresponent a E. El graf és planar només si té una 2-base.[15]
- Teorema de Schnyder:
Es caracteritzen els grafs per la dimensió de Dushnik–Miller d'un ordre parcial associat.
El poset (partially ordered set) d'incidència P(G) d'un graf amb vèrtexs V i arestes E és el poset amb alçada 2 que té V ∪ E com a elements. L'ordre dimensional del poset és el menor nombre possible d'ordenaments als quals la interacció correspon a l'ordre parcial donat.
|
- Criteri de planaritat de Colin de Verdière:
Utilitza teoria espectral dels grafs per definir un paràmetre μ(G) (Invariant de Colin de Verdière), corresponent al major co-rang possible en una matriu simètrica dels vectors.
|
Mètode d'addició de rutes
El mètode d'addició de rutes de John Hopcroft i Robert Tarjan va ser el primer a ser publicat (1974) que complia un temps lineal O(n).[16] Actualment hi ha una implementació de l'algorisme publicada a la Llibreria de Dades Eficients i Algorismes (LEDA).[17][18][19]
El 2012, Martyn G. Taylor va generalitzar l'algorisme per generar totes les permutacions d'un ordre cíclic per representacions planes de components biconnectats.[20]
Mètode d'addició de vèrtexs
El mètode d'addició de vèrtexs consisteix en mantenir una estructura de dades representativa de les possibles representacions d'un subgraf induït del graf, i afegint-hi vèrtexs d'un en un. Aquest mètode inicialment (1967) era molt ineficient O(n²), creat per Abraham Lempel i Shimon Even.[21] Va ser millorat més tard per Even i Tarjan, que van trobar una solució amb temps lineal.[22] i per Kellog S. Booth i George S. Lueker, que van desenvolupar l'arbre PQ, una eficient estructura de dades. Gràcies a aquestes millores aquest mètode és més eficient que el d'addició de rutes.[23] Aquest mètode també va ser ampliat per permetre representacions planars en un pla de forma computacionalment eficient.[24] Al 1999, Shih i Hsu van simplificar aquests mètodes utilitzant arbres PC recorregut transversal de l'arbre DPS dels vectors.[25]
Mètode d'addició d'arestes
Al 2004, John Boyer i Wendy Myrvold van desenvolupar un algorisme O(n) simple inspirat en el mètode d'arbre PQ, que utilitza addicions d'arestes per computar una representació planar sempre que sigui possible. En cas contrari, una subdivisió de Kuratowski és computada.[26] Aquest és un dels mètodes més utilitzats avui dia, juntament amb el test de planaritat de Fraysseix, de Mendez i Rosenstiehl.[27][28]). S'han fet comprovacions experimentals amb versions preliminars per comparar-ne l'eficiència.[29] A més, el test de Boyer–Myrvold va ser ampliat per extreure múltiples subdivisions de Kuratowski en temps lineal.[30][31]
Mètode de construcció de seqüències
Aquest mètode utilitza una construcció inductiva de grafs per construir de forma incremental, partint de K₄, representacions planars de cada component de G, i per tant una representació planar del graf.[32] Això permet reduir el test de planaritat a comprovar a cada pas si la següent aresta afegida té els dos extrems a la cara externa de la representació actual. Tot i que la idea és conceptualment simple i funciona a temps lineal, el mètode és complex en trobar la seqüència construïda.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
