Teoria de grafs

De Viquipèdia
Dreceres ràpides: navegació, cerca
Representació d'un graf amb 6 vèrtexs i 7 arestes

La teoria de grafs és una branca de les matemàtiques i la informàtica que es dedica a l'estudi dels grafs, estructures matemàtiques utilitzades per a modelitzar relacions entre parelles d'objectes.[1] En aquest context, un graf consisteix en una col·lecció de vèrtexs o nodes connectats per línies anomenades arestes. Els grafs poden ser no dirigits, és a dir sense fer distinció entre els dos vèrtexs associats a cada aresta, o dirigits, les arestes dels quals van d'un vèrtex a un altre; en aquest cas, les arestes s'anomenen arcs. Els grafs se solen representar gràficament amb un punt o cercle per cada vèrtex, i una línia entre vèrtexs connectats. Si el graf és dirigit, els arcs se simbolitzen amb fletxes, indicant la direcció de la relació entre els dos vèrtexs.

Els grafs són un dels principals objectes d'estudi de la matemàtica discreta. Les aplicacions de la teoria de grafs giren al voltant d'estructures que poden ser sistematitzades amb grafs, com per exemple l'estructura de llocs web, l'anàlisi de xarxes, l'estudi de molècules en química i física, o altres camps com els estudis sociològics.

El precursor de la teoria de grafs fou Leonhard Euler, que la va iniciar tot intentant resoldre el problema dels set ponts de Königsberg.

Definicions[modifica | modifica el codi]

Article principal: Graf (matemàtiques)

En el sentit més habitual del terme,[2] un graf és un parell ordenat G = (V, E), format per un conjunt V de vèrtexs o nodes o punts juntament amb un conjunt E d'arestes o arcs, que són subconjunts de 2 elements de V (és a dir, una aresta relaciona dos vèrtexs, i aquesta relació es representa mitjançant un parell no ordenar dels vèrtexs respecte de l'aresta en qüestió). Per tal d'evitar ambigüitats, hom diu que aquest tipus de graf és no dirigit i simple.

Altres definicions de graf parteixen de diferents concepcions del conjunt d'arestes. En un sentit més general,[3] V és un conjunt amb una relació d'incidència que associa dos vèrtexs amb cada aresta. En un altre sentir, E és un multiconjunt de parells no ordenats de vèrtexs (no necessàriament diferents). Molts autors diuen que aquest tipus de graf és un multigraf o pseudograf.

Hom diu que els vèrtexs que pertanyen a una aresta són els extrems o vèrtexs finals de l'aresta. Pot donar-se el cas que un vèrtex pertanyi al graf i que no pertanyi a cap aresta.

Habitualment, V i E són conjunts finits, i molts dels resultats coneguts no són certs (o són diferents) per a grafs infinits, perquè molts dels arguments fallen en el cas infinit. L'ordre d'un graf és |V|, el nombre dels seus vèrtexs. its number of vertices. La grandària d'un graf és |E|, el nombre de les seves arestes. El grau o valència d'un vèrtex és el nombre d'arestes que estan connectades amb el vèrtex, amb la convenció que una aresta que connecta un vèrtex amb ell mateix (un bucle) es compta dos cops.

Per a una aresta {x, y}, hom acostuma a emprar la notació més breu xy.

Aplicacions[modifica | modifica el codi]

Graf en xarxa format pels editors de Wikipedia (arestes) que contribueixen a versions en diferents idiomes (vèrtexs) durant un mes de l'estiu de 2013[4]

Els grafs es poden usar per modelar diferents tipus de relacions i processos en sistemes físics, biològics,[5] socials i d'informació. Molts problemes pràctics es poden representar mitjançant grafs.

En ciències de la computació, els grafs s'utilitzen per representar xarxes de comunicació, organització de dades, dispositius computacionals, flux de computació, etc. Per exemple, l'estructura d'enllaços d'un lloc web es pot representar mitjançant un graf dirigit, on els vèrtexs representen les pàgines web, i les arestes dirigides representen enllaços d'una pàgina a una altra. Una aproximació similar pot servir per modelar problemes de viatges, biologia, disseny de xips, i altres camps. El desenvolupament d'algoritmes per tractar grafs és, per tant, d'una gran importància en ciències de la computació. La transformació de grafs s'acostuma a formalitzar mitjançant sistemes de reescriptura de grafs. Altres aplicacions són les bases de dades orientades a grafs, amb l'objectiu d'emmagatzemar les dades d'una forma transaccional i persistent, així com consultar les dades emmagatzemades en forma de graf.

Els mètodes de la teoria de grafs, en diverses formes, són particularment útils en lingüística, ja que el llenguatge natural té sovint una estructura discreta. Tradicionalment, la sintaxi i la semàntica composicional segueixen estructures basades en arbres, el poder expressiu de les quals rau en el principi de composicionalitat, que es modela mitjançant un graf jeràrquic. Algunes aproximacions més contemporànies, com la gramàtica sintagmàtica nuclear, modelen la sintaxi del llenguatge natural utilitzant estructures de trets, que són grafs acíclics dirigits. En semàtica lexical, especialment aplicada als computadors, és més senzill modelar el significat de les paraules quan s'entén cada paraula en termes d'altres paraules relacionades; les xarxes semàntiques són importants, en conseqüència, en lingüística computacional. També són comuns altres mètodes en fonologia (per exemple, la teoria de l'optimalitat, que utilitza grafs de reticle) i morfologia (per exemple, mofologia d'estats finits, que utilitza transductors d'estats finits) en l'anàlisi del llenguatge mitjançant grafs. De fet, l'aplicació dels grafs a la lingüística ha donat lloc a organitzacions com TextGraphs, WordNet o VerbNet, entre altres.

La teoria de grafs també s'utilitza per estudiar molècules en química i física. En física de la matèria condensada, l'estructura tridimensional de simulacions d'estructures atòmiques complicades es pot estudiar quantitativament recopilant estadístiques sobre algunes propietats de la teoria de grafs relacionades amb la topologia dels àtoms. En química, un graf resulta ser un model natural d'una molècula, on els vèrtexs representen els àtoms i les arestes representen els enllaços químics. Aquesta aproximació és ben utilitzada en el processament per ordinador d'estructures moleculars, des d'editors químics a cerques en bases de dades. En física estadística, els grafs poden representar les connexions locals entre parts d'un sistema que interactuen entre elles, així com la dinàmica d'un procés físic en un tal sistema. De la mateixa manera, en neurociència computacional, es poden utilitzar grafs per representar les onnexions funcionals entre les àrees del cervell que interactuen per donar lloc a diversos processos cognitius, on els vèrtexs representen les diferents àrees del cervell, i les arestes representen les connexions entre aquestes àrees. Els grafs també es poden utilitzar per representar els canals a microescala dels mitjans porosos, on els vèrtexs representen els porus, i les arestes representen els petits canals que connecten els porus.

La teoria de grafs s'usa també àmpliament en sociologia, com una manera, per exemple, de mesurar el prestigi d'un actor, o per explorar l'expansió d'un rumor en les xarxes socials, sobretot en programari per a l'anàlisi de xarxes socials. Sota el paraigua de les xarxes socials existeixen diferents tipus de grafs.[6] Els grafs de relacions personals i d'amistat descriuen si les persones es coneixen les unes a les altres. Els grafs d'influència modelen si certes persones poden influir el comportament d'unes altres. Finalment, els grafs de col·laboració modelen si dues persones treballen juntes d'una certa manera, com actuar junts en una pel·lícula.

De la mateixa manera, la teoria de grafs és útil en biologia i els esforços de conservació, on un vèrtex pot representar regions on existeix una certa espècie, i les arestes representen els camins de migració, o els moviments entre regions. Aquesta informació és important quan s'observen els patrons d'alimenació o quan s'analitza la propagació d'una malaltia, de paràsits, o com els canvis de moviment poden afectar altres espècies.

En matemàtiques, els grafs són útils en geometria i en certes àrees de la topologia, com la teoria de nusos. La teoria algebraica de grafs té relació amb la teoria de grups.

Una estructura de graf es pot ampliar assignant un pes (o valor) a cada aresta del graf. Un graf amb pesos, o graf ponderat, es pot utilitzar per representar estructures on les connexions tenen algun valor numèric. Per exemple, si un graf representa una xarxa de carreteres, els pesos podrien representar la longitud de cada carretera.

Història[modifica | modifica el codi]

El problema dels ponts de Königsberg

Es considera que la primera publicació de la història sobre teoria de grafs fou escrita per Leonhard Euler el 1736, Els set ponts de Königsberg.[7][8] Aquesta publicació, juntament amb la publicació de Vandermonde sobre el Problema de la ruta del cavall, va portar a l'analysis situs iniciat per Leibniz. La fórmula d'Euler que relaciona el nombre d'arestes, vèrtexs i cares d'un políedre convex fou estudiada i generalitzada per Cauchy[9] i L'Huilier,[10] i marca l'origen de la topologia.

Més d'un segle després de la publicació d'Euler sobre els ponts de Königsberg i mentre Listing introduïa la noció de topologia, Cayley estava interessat en l'estudi de certes formes analítiques sorgides del càlcul diferencial per tal d'estudiar una classe particular de grafs, els arbres.[11] Aquest estudi tingué moltes implicacions en química teòrica. Les tècniques que s'hi feien servir tenien a veure amb l'enumeració de grafs amb certes propietats. La teoria enumerativa de grafs sorgí a partir dels resultats publicats per Pólya entre 1935 i 1937 i la seva generalització de De Bruijn el 1959. Cayley va relacionar els seus resultats sobre arbres amb els edtudis contemporanis de composició química.[12] La fusió de les idees provinents de les matemàtiques amb les de la química va originar part de la terminologia estàndard de la teoria de grafs.

En particular, Sylvester va introduir el terme "graf" en un estudi publicat el 1878 a la revista Nature, on dibuixava una analogia entre "invariants quàntics" i "covariants" de l'àlgebra i els diagrames moleculars:

« (anglès) […] Every invariant and co-variant thus becomes expressible by a graph precisely identical with a Kekuléan diagram or chemicograph. […] I give a rule for the geometrical multiplication of graphs, i.e. for constructing a graph to the product of in- or co-variants whose separate graphs are given. […] (català) […] Qualsevol invariant i covariant es pot, doncs, expressar com un graf idèntic a un diagrama de Kekulé o quimiograf. […] Dono una regla per a la multiplicació geomètrica de grafs, és a dir, per construir un graf per al producte d'invariants o covariants donats. […] »

Sylvester, Chemistry and Algebra (Nature)[13]

El primer llibre de text sobre teoria de grafs fou escrit per Dénes Kőnig, i publicat el 1936.[14] Un altre llibre de Frank Harary, publicat el 1969, fou "considerat com el llibre de text definitiu sobre la matèria",[15] i va aconseguir que els matemàtics, químics, enginyers elèctrics i científics socials parlessin un llenguatge comú. Harary va cedir-ne tots els drets al Premi Pólya.[16]

Un dels problemes de teoria de grafs més famós i més estimulant és el problema dels quatre colors: "És o no cert que qualsevol mapa dibuixat al pla pot tenir les seves regions pintades amb quatre colors, de tal manera que dues regions qualssevol amb frontera comuna tinguin colors diferents?" Aquedt problema fou proposat per primer cop per Francis Guthrie l'any 1852, i el seu primer registre escrit és una carta de De Morgan a Hamilton el mateix any. Se n'han proposat moltes demostracions incorrectes, incloses les de Cayley, Kempe i altres. L'estudi i la generalització d'aquest problema realitzats per Tait, Heawood, Ramsey i Hadwiger van portar a l'estudi de les coloracions dels grafs immersos en superfícies amb un gènere arbitrari. La reformulació de Tait va generar una nova classe de problemes, els problemes de factorització, estudiats especialment per Petersen i Kőnig. Les obres de Ramsey sobre coloracions i més especialment els resultats obtinguts per Turán el 1941 van originar una altra branca de la teoria de grafs, la teoria de grafs extremals.

El problema dels quatre colors va quedar sense solució durant més d'un segle. L'any 1969, Heinrich Heesch va publicar un mètode per resoldre el problema mitjançant l'ús d'ordinadors.[17] L'any 1976, Kenneth Appel i Wolfgang Haken van publicar una demostració, que feia ús del concepte de "descàrrega" desenvolupat per Heesch.[18][19] La demostració incloïa comprovar per ordinador les propietats de 1.936 configuracions, cosa que no fou acceptada completament en aquella època a causa de la seva complexitat. Vint anys després, Robertson, Seymour, Sanders i Thomas van proporcionar una demostració més senzilla amb 633 configuracions.[20]

El desenvolupament autònom de la topologia entre 1860 i 1930 va obrir el camí a la teoria de grafs, amb les obres de Jordan, Kuratowski i Whitney. Un altre factor important en el desenvolupament comú de la teoria de grafs i la topologia va venir de l'ús de les tècniques de l'àlgebra moderna. El primer exemple d'aquest ús prové de l'obra del físic Gustav Kirchhoff, qui va publicar el 1845 les seves lleis de Kirchhoff per calcular el voltatge i el corrent en circuits elèctrics.

La introducció dels mètodes probabilístics en la teoria de grafs, especialment en l'estudi de Erdős i Rényi sobre la probabilitat asimptòtica de la connectivitat de grafs, va originar una altra branca, anomenada teoria de grafs aleatoris, que ha estat una font de molts resultats de la teoria de grafs.

Representació gràfica[modifica | modifica el codi]

Els grafs es representen visualment dibuixant un punt o cercle per a cada vèrtex, i un segment entre dos vèrtexs si estan connectats per una aresta. Si el graf és dirigit, el sentit es representa mitjançant una fletxa.

Cal no confondre una representació gràfica d'un graf amb el propi graf (l'estructura abstracta, no visual), ja que existeixen diverses foes d'estructurar-ne la representació gràfica. El que importa és quins vèrtexs estan connectats als altres, i no la seva disposició exacta. A la pràctica, és difícil determinar si dos gràfics representen el mateix graf. Depenent del problema que calgui resoldre, algunes representacions gràfiques poden ser més adequades i fàcils d'entendre que d'altres.

L'obra de William T. Tutte tingué una gran influència en l'àrea de la representació gràfica de grafs. Entre altres contribucions, Tutte va introduir l'ús de mètodes de l'àlgebra lineal per obtenir representacions gràfiques.

Les representacions gràfiques juguen també un rol essencial en problemes sobre el nombre de creuament i les seves generalitzacions. El nombre de creuament d'un graf és el mínim nombre d'interseccions entre arestes que ha de contenir una representació gràfica al pla d'un graf. Per definició, el nombre de creuament d'un graf planar és zero.

També es poden considerar representacions gràfiques sobre superfícies diferents del pla.

Estructures de dades basades en la teoria de grafs[modifica | modifica el codi]

Article principal: Graf (estructura de dades)

Existeixen diferents formes d'emmagatzemar grafs en un ordinador. L'estructura de dades utilitzada depèn tant de l'estructura del graf com de l'algoritme utilitzat per manipular-lo. En teoria, hom pot distingir entre estructures de llista i de matriu, però a la pràctica la millor estructura acostuma a ser una combinació de les dues. Les estructures basades en llistes són més útils per a grafs dispersos, ja que necessiten menys memòria per emmagatzemar-los. Les estructures matricials, per altra banda, proporcionen un accés més ràpid, però poden consumir més memòria.

Les estructures de llista inclouen la llista d'incidència, una llista de parells de vèrtexs, i la llista d'adjacència, que llista de forma separada els veïns de cada vèrtex.

Les estructures matricials inclouen la matriu d'incidència, una matriu de zeros i uns, on les files representen els vèrtexs i les columnes representen les arestes; i la matriu d'adjacència, on tant les files com les columnes representen els vèrtexs. En ambdós casos, un 1 representa dos objectes adjacents i un 0 indica dos objectes no adjacents (o, en el cas de grafs dirigits, +1 o -1 per expressar l'orientació de cada aresta, i 0 si els objectes no són adjacents). La matriu Laplaciana és una versió modificada de la matriu d'adjacència, que incorpora informació sobre els graus dels vèrtexs, i és útil en alguns càlculs com el teorema de Kirchhoff sobre el nombre d'arbres d'expansió d'un graf. La matriu de distàncies, de la mateixa manera que la matriu d'adjacència, té files i columnes que representen els vèrtexs, però, en comptes de tenir entrades amb valor 0 o 1, contenen la longitud d'un camí mínim entre dos vèrtexs.

Problemes de teoria de grafs[modifica | modifica el codi]

Enumeració[modifica | modifica el codi]

Existeix una àmplia literatura sobre l'enumeració de grafs: el problema de comptar els grafs que satisfan unes determinades condicions. Algunes d'aquestes obres es poden trobar a Harary & Palmer 1973.

Subgrafs, grafs induïts i menors[modifica | modifica el codi]

Un problema comú, conegut com a problema d'isomorfisme de subgrafs, és trobar un graf fixat com a subgraf d'un graf donat. Una raó és que moltes propietats dels grafs són hereditàries per a subgrafs, la qual cosa vol dir que un graf té la propietat si i només si tots els seus subgrafs també la tenen. Malauradament, el problema de trobar subgrafs maximals d'un cert tipus sol ser un problema NP-complet. Per exemple:

Un problema similar consisteix a trobar els subgrafs induïts d'un determinat graf. De nou, algunes propietats importants dels grafs s'hereden als subgrafs induïts, la qual cosa significa que un graf té una propietat si i només si tots els seus subgrafs induïts la tenen. El problema de trobar subgrafs induïts maximals d'un cert tipus també acostuma a ser NP-complet. Per exemple:

Un altre problema, el problema del menor contingut, consisteix a trobar un graf fixat com a menor d'un graf donat. Un menor o subcontracció d'un graf és qualsevol graf obtingut a partir d'un subgraf i contraient-ne algunes arestes. Moltes propietats dels grafs són hereditàries per a menors, la qual cosa vol dir que un graf té una propietat si i només si tots els seus menors també la tenen. Per exemple:

Una altra classe de problemes té a veure amb fins a quin punt es pot reconstruir un graf si se n'ha eliminat algun punt. Per exemple:

Coloració de grafs[modifica | modifica el codi]

Molts problemes tenen a veure amb diferents formes d'acolorir grafs, per exemple:

Problemes d'encaminament[modifica | modifica el codi]

Flux de xarxes[modifica | modifica el codi]

Existeixen multitud de problemes relacionats amb el concepte de xarxa de flux, per exemple:

Problemes de visibilitat[modifica | modifica el codi]

Problemes de recobriment[modifica | modifica el codi]

Els problemes de recobriment en grafs són casos especials dels problemes de trobar subgrafs, i acostumen a estar fortament relacionats amb el problema de la clique o amb el problema del conjunt independent.

Problemes de descomposició[modifica | modifica el codi]

El concepte de descomposició, definida com la partició del conjunt d'arestes d'un graf (amb els vèrtexs necessaris per a cada part), admet una multitud de variants. De vegades s'exigeix descompondre un graf en subgrafs isomorfs a un cert graf; per exemple, descompondre un graf complet en cicles hamiltonians. Altres problemes especifiquen una família de grafs en els quals s'ha de descompondre un graf donat, per exemple, una família de cicles, o descompondre un graf complet Kn en n − 1 arbres especificats que tinguin, per exemple, 1, 2, 3, …, n − 1 arestes.

Alguns problemes concrets de descomposició són:

Classes de grafs[modifica | modifica el codi]

Molts problemes tenen a veure amb caracteritzar els membres de diverses classes de grafs. Alguns exemples són:

  • Enumerar els membres d'una classe.
  • Caracteritzar una classe en funció d'estructures prohibides.
  • Determinar relacions entre classes (és a dir, si una propietat de grafs n'implica una altra).
  • Trobar algoritmes eficients per decidir la pertinença o no d'un graf a una classe.
  • Trobar representacions per a membres d'una classe.

Referències[modifica | modifica el codi]

  1. Basart i Muñoz, Josep Maria. Grafs: fonaments i algorismes. 2a ed.. Barcelona: Servei de publicacions de la UAB, 1998. 
  2. Vegeu, per exemple, Iyanaga & Kawada, 69 J, p. 234 o Biggs, p. 4.
  3. Vegeu, per exemple, Graham et al., p. 5.
  4. Hale, Scott A. «Multilinguals and Wikipedia Editing». Proceedings of the 6th Annual ACM Web Science Conference, WebSci 2014, ACM, 2013. arXiv: 1312.0976. DOI: 10.1145/2615569.2615684.
  5. Mashaghi, A. «Investigation of a protein complex network». European Physical Journal B, 41, 1, 2004, pàg. 113–121. DOI: 10.1140/epjb/e2004-00301-0.
  6. Rosen, Kenneth H. Discrete mathematics and its applications. 7a edició. Nova York: McGraw-Hill. ISBN 978-0-07-338309-5. 
  7. Biggs, Lloyd & Wilson 1986
  8. Euler, Leonhard «Solutio problematis ad geometriam situs pertinentis». Commentarii academiae scientiarum Petropolitanae, 8, 1741, pàg. 128-140.
  9. Cauchy, Augustin Louis «Recherche sur les polyèdres - premier mémoire». Journal de l'École Polytechnique, 9 (Cahier 16), 1813, pàg. 66–86.
  10. L'Huilier, Simon Antoine Jean «Mémoire sur la polyèdrométrie». Annales de Mathématiques, 3, 1861, pàg. 169–189.
  11. Cayley, Arthur «On the theory of the analytical forms called trees». Philosophical Magazine, 13, 85, 1857, pàg. 172–176. DOI: 10.1017/CBO9780511703690.046.
  12. Cayley, Arthur «Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen». Berichte der deutschen Chemischen Gesellschaft, 8, 2, 1875, pàg. 1056–1059. DOI: 10.1002/cber.18750080252.
  13. Joseph Sylvester, James «Chemistry and Algebra». Nature, 17, 1878, pàg. 284. DOI: 10.1038/017284a0.
  14. Tutte, William Thomas. Graph Theory. Cambridge University Press, 2001, p. 30. ISBN 978-0-521-79489-3 [Consulta: 14 març 2016]. 
  15. Gardner, Martin. Fractal Music, Hypercards, and more…Mathematical Recreations from Scientific American. W. H. Freeman and Company, 1992, p. 203. 
  16. Society for Industrial and Applied Mathematics «Looking Back, Looking Ahead: A SIAM History». The George Polya Prize, 2002, pàg. 26 [Consulta: 14 març 2016].
  17. Heesch, Heinrich. Untersuchungen zum Vierfarbenproblem. Mannheim: Bibliographisches Institut, 1969. 
  18. Appel, K.; Haken, W. «Every planar map is four colorable. Part I. Discharging». Illinois J. Math., 21, 1977, pàg. 429–490.
  19. Appel, K.; Haken, W. «Every planar map is four colorable. Part II. Reducibility». Illinois J. Math., 21, 1977, pàg. 491–567.
  20. Robertson, N.; Sanders, D.; Seymour, P.; Thomas, R. «The four color theorem». Journal of Combinatorial Theory Series B, 70, 1997, pàg. 2–44. DOI: 10.1006/jctb.1997.1750.

Bibliografia[modifica | modifica el codi]

Vegeu també[modifica | modifica el codi]

Enllaços externs[modifica | modifica el codi]

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Teoria de grafs Modifica l'enllaç a Wikidata

Llibres de text en línia[modifica | modifica el codi]