Graf (matemàtiques)

En teoria de grafs, un graf és una representació abstracta d'un conjunt d'objectes on alguns parells dels objectes estan connectats per enllaços. Els objectes interconnectats són representats per abstraccions matemàtiques anomenades vèrtexs, i els enllaços que connecten alguns parells de vèrtexs s'anomenen arestes. Típicament, un graf es descriu de forma esquemàtica com a conjunt de punts o cercles per als vèrtexs, units per línies o corbes per les arestes. Els grafs són un dels objectes d'estudi de la matemàtica discreta.

Representació d'un graf etiquetat, amb 6 vèrtexs i set arestes

Les arestes poden ser dirigides o no dirigides. Per exemple, un graf es pot construir escollint com a vèrtexs els primers 1000 enters positius, i definint que hi ha una aresta entre dos vèrtexs si i només si els dos enters corresponents tenen com a mínim una xifra decimal en comú. En altres casos la relació entre vèrtexs no és simètrica: per exemple, un graf es pot construir escollint els vèrtexs per ser els primers 1000 enters positius, i definint que hi ha un vèrtex des d'i fins a j si i és un divisor de j. Aquest tipus de graf s'anomena un graf dirigit i les arestes s'anomenen arestes dirigides o arcs; per contrast, un graf on no es dirigeixen els arestes s'anomena no dirigit.

Els vèrtexs també s'anomenen nodes o punts, i les arestes també s'anomenen línies. Els grafs són el tema bàsic estudiat per la teoria de grafs.

Definicions

Les definicions en la teoria de grafs varien. Les següents són qualcunes de les maneres més bàsiques de definir un graf i les estructures matemàtiques relacionades.

En el sentit més comú de la paraula, un graf és un parell ordenat $G:=(V,E)$ que comprèn un conjunt $V$ de vèrtexs o nodes juntament amb un conjunt $E$ d’arestes o línies, les quals són conjunts de dos elements de $V$. Per evitar ambigüitats, aquest tipus de graf es defineix de forma precisa com a graf no dirigit i simple.

Altres interpretacions de graf provenen de concepcions diferents del conjunt d'arestes. En una noció més generalitzada, $E$ és un conjunt juntament amb una relació d’incidència que associa dos vèrtexs amb cada aresta. En una altra noció generalitzada, $E$ és un multiconjunt de parells desordenats de (no necessàriament distints) vèrtexs. Molts autors anomenen aquest tipus d'objecte un multigraf o pseudograf.

Totes aquestes variants i d'altres són descrites de manera detallada més avall.

Els vèrtexs que pertanyen a una aresta s'anomenen extrems, punts extrems, o vèrtexs extrems de l'aresta. Un vèrtex pot existir a un graf i no pertànyer a una aresta (vèrtex aïllat).

Normalment es considera que V i E són finits, i molts dels resultats coneguts no són veritables (o són diferents) per a grafs infinits, perquè molts dels arguments fallen en el cas infinit. L'ordre d'un graf és el nombre de vèrtexs i es denota $|V|$. La mida d'un graf és el nombre d'arestes i es denota $|E|$. El grau d'un vèrtex és el nombre d'arestes que hi connecten, on una aresta que connecta el vèrtex als dos extrems (un bucle) es compta dues vegades.

Les arestes $E$ d'un graf no dirigit $G$ indueixen una relació binària simètrica ~ a $V$ que s'anomena la relació d'adjacència de G. Específicament, per a cada aresta {u,v} els vèrtexs u i v es diuen que són adjacents l'un de l'altre, que es denota u ~ v.

Per a una aresta {u, v}, els teòrics de grafs normalment utilitzen la notació una mica més curta uv.

Tipus de grafs

Distincions en termes de la definició principal

Com s'ha dit a dalt, en contexts diferents pot ser útil definir el terme graf amb graus diferents de generalitat. Quan sigui necessari fer una distinció estricta, s'utilitzen els termes següents. En general, en texts moderns sobre teoria de grafs, llevat que no es digui el contrari, graf significa "graf finit simple no dirigit" (vegi les definicions sota).

Graf no dirigit

Un graf en el qual les arestes no tenen cap orientació, és a dir, no són parells ordenats, sinó conjunts {u, v} (o 2-multiconjunts) de vèrtexs.

Graf dirigit

Un graf dirigit.

Un graf dirigit o dígraf és un parell ordenat $D:=(V,A)$ amb

• $V$ un conjunt els elements del qual s'anomenen vèrtexs o nodes, i
• $A$ un conjunt de parells ordenats de vèrtexs, anomenats arcs, arestes dirigides, o fletxes.

Un arc $a=(x,y)$ es considera dirigit de $x$ a $y$; $y$ s'anomena el cap i $x$ s'anomena la cua de l'arc; es diu que $y$ és un successor directe de $x$, i es diu que $x$ és un predecessor directe de $y$. Si un camí porta des de $x$ fins a $y$, llavors $y$ s'anomena un successor de $x$ i accessible des de $x$, i $x$ es diu que és un predecessor de $y$. L'arc $(y,x)$ es diu l'arc $(x,y)$ invertit.

Un graf dirigit D s'anomena simètric si, per a tots els arcs a D, l'arc invertit corresponent també pertany a D. Un graf dirigit simètric sense bucles D = (V, A) és equivalent a un graf no dirigit simple G = (V, E), on els parells d'arcs inversos a A es corresponen un a un amb les arestes a E; així les arestes a G són |E| = |A|/2, o la meitat del nombre d'arcs a D.

Una variació sobre aquesta definició és el graf orientat, al qual només un d'entre $(x,y)$ i $(y,x)$ pot ser un arc.

Graf mixt

Un graf mixt G és un graf que pot contenir tant arestes dirigides com no dirigides. S'escriu com un triplet ordenat G := (V, E, A) amb V, E, i A definit com a dalt. Els grafs dirigits i no dirigits en són casos especials.

Multigraf

Un bucle és una aresta (dirigida o no dirigida) que comença i acaba en el mateix vèrtex; aquests es poden permetre o no segons l'aplicació. En aquest context, una aresta amb dos extrems diferents s'anomena un enllaç.

El terme "multigraf" denota normalment que es permeten arestes múltiples (i a vegades bucles). Quan els grafs es defineixen per tal de permetre bucles i arestes múltiples, un multigraf es defineix sovint com un graf sense bucles, mentre que, allà on els grafs es defineixen per tal de no permetre bucles i arestes múltiples, el terme es defineix sovint per significar un "graf" que pot tenir tant arestes múltiples com bucles, encara que molts utilitzen el terme "pseudograf" per aquest significat.

Graf simple

Un graf simple amb tres vèrtex i tres arestes. Cada vèrtex té grau 2, així que també és un graf regular.

En contraposició a un multigraf, un graf simple és un graf no dirigit que no té cap bucle i no més d'una aresta entre dos vèrtexs diferents qualssevol. En un graf simple les arestes del graf formen un conjunt (en comptes d'un multiconjunt) i cada aresta és un parell de vèrtexs distints. En un graf simple amb n vèrtexs tots els vèrtexs tenen un grau menor que n (el contrari, però, no és veritable - existeixen grafs no simples amb n vèrtexs en els quals tots els vèrtexs tenen grau menor a n).

Graf ponderat

Un graf és un graf ponderat si un nombre (pes) s'assigna a cada aresta. Tals pesos podrien representar, per exemple, costos, llargades o capacitats, depenent del problema considerat.

El pes del gràfic és suma dels pesos donats a totes les arestes.

Classes de grafs importants

Graf regular

Un graf regular és un graf on cada vèrtex té el mateix nombre de veïns, i. e., tots els vèrtexs tenen el mateix grau o valència. Un graf regular amb vèrtexs de grau k s'anomena un graf k-regular o graf regular de grau k.

Graf complet

Els grafs complets tenen el tret que cada parell de vèrtexs té una aresta que els connecta.

Grafs finits i infinits

Un graf finit és un graf G = (V,E) tal que V(G) i E(G) són conjunts finits. Un graf infinit és aquest amb conjunts de vèrtexs o arestes, o tots dos, infinits.

Més comunament en la teoria de grafs s'implica que els grafs de què es parla són finits, i.e., els grafs finits s'anomenen simplement "grafs", mentre que quan els grafs són infinits se sol explicitar.

Classes de grafs en termes de connectivitat

En un graf no dirigit G, dos vèrtexs u i v s'anomenen connexos si G conté un camí des d'u fins a v. Altrament, s'anomenen inconnexos. Un graf s'anomena connex si tots els parells de vèrtexs distints del graf estan connectats i desconnex altrament.

Un graf s'anomena k-vèrtex-connex o k-aresta-connex si la supressió de k o més vèrtexs (respectivament, arestes) fa el graf desconnex. Un graf k-vertex-connex s'anomena sovint simplement k-connex.

Un graf dirigit s'anomena feblement connex si canviar totes les seves arestes dirigides per arestes no dirigides produeix un graf connex (no dirigit). És fortament connex o fort si conté un camí dirigit des d'u a v i un camí dirigit des de v a u per a tots els parells de vèrtexs u,v.

Propietats dels grafs

Dues arestes d'un graf s'anomenen adjacents (a vegades coincidents) si comparteixen un vèrtex comú. Dues fletxes d'un graf dirigit s'anomenen consecutives si el cap del primer és al final de la segona, d'aquesta manera, les arestes {x,a},{a,y} serien consecutives. De manera similar, dos vèrtexs s'anomenen adjacents si comparteixen una aresta comuna (consecutius si són al cap i final d'una fletxa); en aquest cas es diu que l'aresta comuna uneix els dos vèrtexs. Una aresta i un vèrtex en aquella aresta s'anomenen incidents.

El graf amb només un vèrtex i cap aresta s'anomena el graf trivial. Un graf amb només vèrtexs i cap aresta es coneix com a graf degenerat. El graf amb cap vèrtex i cap aresta s'anomena a vegades el graf nul o graf buit, però no tots els matemàtics permeten aquest objecte.

En un graf ponderat o dígraf, cada aresta està associada amb qualque valor, diversament anomenat cost, pes, llargada o altres termes depenent de l'aplicació; tals grafs sorgeixen en molts contexts, per exemple en problemes d'encaminament òptims com el problema del viatjant de comerç.

Normalment, els vèrtexs d'un graf, per la seva natura com a elements d'un conjunt, són distingibles. Aquesta classe de graf es pot anomenar com a vèrtex-etiquetat. Tanmateix, per a moltes qüestions és millor tractar els vèrtexs com indistingibles; llavors el graf es pot anomenar no etiquetat (naturalment, els vèrtexs poden ser encara distingibles degut a les propietats del mateix graf, p. ex., pel nombre d'arestes incidents). Els mateixos comentaris s'apliquen a les arestes, de manera que els grafs que tenen arestes etiquetades s'anomenen grafs d'arestes etiquetades. Els grafs amb etiquetes a les arestes o als vèrtexs es designen més generalment com etiquetats. Consegüentment, els grafs en els quals els vèrtexs són indistingibles i les arestes són també indistingibles s'anomenen no etiquetats. (Fixi's que en la literatura el terme etiquetat es pot aplicar a unes altres classes de marcatge, a més a més de la que serveix només per distingir vèrtexs diferents o arestes.)

Exemples

Un graf amb sis nodes.

L'esquema de la dreta és una representació gràfica del graf següent:

• $V:=\{1,2,3,4,5,6\}$
• $E:=\{\{1,2\},\{1,5\},\{2,3\},\{2,5\},\{3,4\},\{4,5\},\{4,6\}\}.$

El fet que el vèrtex 1 sigui adjacent al vèrtex 2 és a vegades denotat per 1 ~ 2.

• En la teoria de categories una

Viccionari

categoria petita es pot considerar un multigraf dirigit amb els objectes com vèrtexs i els morfismes com arestes dirigides. Els functors entre categories indueixen qualcuns, però no necessàriament tots, dels morfismes de dígraf.

• En la informàtica els grafs dirigits s'utilitzen per representar màquines d'estats finits i moltes altres estructures discretes.
• Una relació binària $R$ en un conjunt $X$ és un graf dirigit. Dos arestes $x$, $y$ de $X$ estan connectats per una fletxa si $xRy$.

Grafs importants

Exemples bàsics són:

• En un graf complet cada parell de vèrtexs és unit per una aresta, és a dir, el graf conté totes les arestes possibles.
• En un graf bipartit, els vèrtexs es poden dividir en dos conjunts, W i X, de manera que totes les arestes tinguin un vèrtex en cada un dels dos conjunts, o equivalentment on cap parell de vèrtexs de W és adjacent i cap parell de vèrtexs de X és adjacent. També es pot definir com un graf amb número cromàtic 2.
• En un graf bipartit complet, el conjunt de vèrtex és la unió de dos subconjunts disjunts, W i X, de manera que tots els vèrtexs a W siguin adjacents a tots els vèrtexs a X però no hi hagi cap aresta dins de W o X.
• En un graf lineal o graf camí de llargada n, els vèrtexs es poden llistar en ordre, v₀, v₁,..., v_n, de manera que les arestes siguin v_i−1v_i per cada i = 1, 2, ..., n. Si un graf lineal és un subgraf d'un altre graf, llavors és també un camí en aquest graf.
• Un graf cicle de llargada n és un camí tancat sense autointerseccions; equivalentment, és un graf connex 2-regular. Els seus vèrtexs es poden anomenar v₁,..., v_n de manera que les arestes siguin v_i−1v_i per cada i = 2,...,n i v_nv₁. Si un graf cicle és un subgraf d'un altre graf, llavors és també un cicle en aquest graf.
• Un graf planar es pot dibuixar en un pla sense arestes que es creuin (és a dir, incrustades en un pla).
• Un arbre és un graf connex sense cicles.
• Un bosc és un graf sense cicles (i.e. un o més arbres).

Altres classes més avançades de grafs són:

• El graf de Petersen i les seves generalitzacions.
• Grafs perfectes.
• Cografs
• Altres grafs amb grups d'automorfisme grans: grafs transitius de vèrtex, transitius d'arc, i transitius de distància.
• Grafs fortament regulars i la seva generalització; grafs regulars de distància.

Operacions sobre grafs

Hi ha diverses operacions que produeixen grafs nous a partir de vells, que es podrien classificar en les categories següents:

• Operacions elementals, a vegades anomenades "operacions d'edició" sobre grafs, que creen un graf nou des de l'original mitjançant un canvi simple i local, com addició o supressió d'un vèrtex o una aresta, fusió i partició de vèrtexs, etc.
• Operacions de reescriptura de grafs que canvien l'aparició d'algun patró dins del graf amfitrió per una instància del corresponent graf de substitució.
• Operacions unàries, que creen un graf significativament nou des del vell. Exemples:
  • Graf lineal
  • Graf dual
  • Graf complementari
• Operacions binàries, que creen un graf nou de dos grafs inicials. Exemples:
  • Unió disjunta de dos grafs
  • Producte cartesià de grafs
  • Producte tensorial de grafs
  • Producte fort de grafs
  • Producte lexicogràfic de grafs

Generalitzacions

En un hipergraf, una aresta pot unir més de dos vèrtexs.

Un graf no dirigit es pot veure com un complex simplicial que consta d'1-símplexs (les arestes) i 0-símplexs (els vèrtexs). Com a tal, els complexos són generalitzacions de grafs, ja que tenen en compte símplexs de dimensions més grans.

Tots els grafs causen un matroid.

En la teoria de models, un graf és només una estructura. Però en aquest cas, no hi ha cap limitació sobre el nombre d'arestes: pot ser qualsevol nombre cardinal.

En la biologia computacional, l'anàlisi de grafs de potència introdueix grafs de potència com a representació alternativa de grafs no dirigits.

Bibliografia

• Iyanaga, Shôkichi; Kawada, Yukiyosi. Encyclopedic Dictionary of Mathematics. MIT Press, 1977. ISBN 0-262-09016-3. 
• Zwillinger, Daniel. CRC Standard Mathematical Tables and Formulae. 31a ed.. Chapman & Hall/CRC, 2002-11-27. ISBN 1-58488-291-3. 
• Balakrishnan, V. K.. Graph Theory. 1a edició. McGraw-Hill, 1997-02-01. ISBN 0-07-005489-4. Trudeau, Richard J. Introduction to Graph Theory. Corrected, enlarged republication.. Nova York: Dover Publications, 1993. ISBN 978-0-486-67870-2 [Consulta: 8 agost 2012]. 
• Hernando, Carmen; Jiang, Tao; Mora, Mercè; Pelayo, Ignacio M.; Seara, Carlos (2005-04). "On the Steiner, geodetic and hull numbers of graphs". Discrete Mathematics. 293 (1–3): 139–154. doi:10.1016/j.disc.2004.08.039.
• Berge, Claude. Théorie des graphes et ses applications (en francès). Dunod, Paris: Collection Universitaire de Mathématiques, II, 1958, p. viii+277.  Translation: [1962] {{{títol}}} (en anglès). Dover, New York: Wiley, 2001. 
• Biggs, Norman. Algebraic Graph Theory. 2a edició. Cambridge University Press, 1993. ISBN 0-521-45897-8. 
• Bollobas, Bela. Modern Graph Theory. 1a edició. Springer, 2002-08-12. ISBN 0-387-98488-7. 
• Bang-Jensen, J.; Gutin, G.. Digraphs: Theory, Algorithms and Applications. Springer, 2000. 
• Diestel, Reinhard. Graph Theory. 3a edició. Berlin, New York: Springer-Verlag, 2005. ISBN 978-3-540-26183-4. .
• Graham, R.L., Grötschel, M., and Lovász, L. Handbook of Combinatorics. MIT Press, 1995. ISBN 0-262-07169-X. 
• Gross, Jonathan L.; Yellen, Jay. Graph Theory and Its Applications. CRC Press, 1998-12-30. ISBN 0-8493-3982-0. 
• Gross, Jonathan L., & Yellen, Jay. Handbook of Graph Theory. CRC, 2003-12-29. ISBN 1-58488-090-2. 
• Harary, Frank. Graph Theory. Addison Wesley Publishing Company, gener 1995. ISBN 0-201-41033-8. 

Vegeu també

A Wikimedia Commons hi ha contingut multimèdia relatiu a: Graf

• Glossari de teoria de grafs
• Teoria de xarxes
• Base de dades orientada a grafs
• Anàlisi de xarxes
• Xarxa bayesiana