Graf

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

En matemàtiques, 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 diagramàtica com a conjunt de cercles per als vèrtexs, units per línies o corbes per les arestes.

Per exemple, un graf es pot construir escollint com a vèrtexs els primers 1000 enters positius, i definint què hi ha un aresta entre dos vèrtexs si i només si aquells dos enters 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 seguents son 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 es un parell ordenat $G := (V, E)$ que compren un conjunt $V$ de vèrtex o nodes juntament amb un conjunt $E$ d'arestes o linies, els quals son subconjunts de dos elements de $V$. Per evitar ambigüetats, aquest tipus de graf es defineix de forma precisa com graf no dirigit i simple.

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

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

Els vèrtex que pertanyen a una aresta s'anomenen extrems, punts extrems, o vèrtex 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 son diferents) per a grafs infinits, perquè molts dels arguments fallen en el cas infinit. L'ordre d'un graf és el nombre de vèrtex 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 de 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'adjacencia 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. Més comunament, en texts moderns en la teoria de grafs, llevat que no es digui el contrari, graf significa "gràfic finit simple no dirigit" (vegi les definicions sota).

Graf no dirigit

Un graf en el qual les arestes no tenen cap orientació, es a dir, no son parells ordenats, sinó conjunts {u, v} (o multiconjunts de 2) 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)$ és considerat ser 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$ es diu de ser un successor de $x$ i accessible des de $x$, i $x$ es diu que es 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 son |E| = |A|/2, o la meitat del nombre d'arcs a D.

Una variació sobre aquesta definició és el graf orientat, al qual no més d'un de $(x, y)$ i $(y, x)$ poden ser arcs.

Graf mixt

Un graf mixt G és un graf al qual es poden dirigir algunes arestes i se'n poden indirigir algunes. S'escriu com un triple ordenat G := (V, E, A) amb V, E, i A definit com a dalt. Els grafs dirigits i indirigits en son 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). Als llocs on els grafs es defineixen per tal que es permetin bucles i arestes múltiples, un multigraf es defineix sovint com a un graf sense bucles, mentre que, on els grafs es defineixen per tal que no es permetin 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 (més que no 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, capacitats, etc. depenent del problema.

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 gràfic 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 el 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 els grafs infinits s'anomenen d'igual manera.

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 al graf estan 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-connectat s'anomena sovint simplement k-connex.

Un graf dirigit s'anomena feblement connex si canviar totes les seves arestes dirigides per arestes indirigides produeix un graf connex (indirigit). Ésfortament connex o fort si conté un camí dirigit des du 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 forma similar, dos vèrtexs s'anomenen adjacents si comparteixen una aresta comuna (consecutives si son al cap i final d'una fletxa), en quin 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 grafs 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 elements d'un conjunt són distingibles. Aquesta classe de gràfic es pot anomenar de vèrtex etiquetats. Tanmateix, per a moltes qüestions és millor tractar vèrtexs com indistinguibles; llavors el graf es pot anomenar inetiquetat (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 indistinguibles i les arestes són indistinguibles 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.

La fotografia é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 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.
• 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 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
• Un graf cicle de llargada n és un camí tancat sense autointerseccions; equivalentment, és un graf connex amb grau 2 a tots els vèrtexs. Els seus vèrtexs es poden anomenar v₁, ..., v_n de manera que les arestes siguin v_i−1v_i fper cada i = 2,...,n and v_nv₁
• Un graf planar es pot dibuixar en un pla sense arestes que es creuin (i.e., incrustades en un pla).
• L'arbre és un graf connex sense cicles.
• El 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 unes quantes operacions que produeixen grafs nous desde 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 per un canvi simple, local, com addició o supressió d'un vèrtex o una aresta, fusió i partició de vèrtexs, etc.
• Operacions de reescritura de grafs que canvien l'aparició d'algun graf de patró dins del graf amfitrió per un instància del corresponent graf de substitució.
• Operacions Unàries, que creen un graf significativament nou des del vell. Exemples:
  • graf Línia
  • 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 de 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.

Vegeu també

• Graf dual
• Glossari de teoria de grafs
• Teoria de xarxes
• Base de dades orientada a grafs

Referències

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

• Balakrishnan, V. K.. Graph Theory. 1st. McGraw-Hill, 1997-02-01. ISBN 0-07-005489-4. 
• Berge, Claude. Théorie des graphes et ses applications (en french). Dunod, Paris: Collection Universitaire de Mathématiques, II, 1958, p. viii+277.  Translation: [1962] {{{títol}}} (en english). Dover, New York: Wiley, 2001. 
• Biggs, Norman. Algebraic Graph Theory. 2nd. Cambridge University Press, 1993. ISBN 0-521-45897-8. 
• Bollobas, Bela. Modern Graph Theory. 1st. Springer, 2002-08-12. ISBN 0-387-98488-7. 
• Bang-Jensen, J.; Gutin, G.. Digraphs: Theory, Algorithms and Applications. Springer, 2000. 
• Diestel, Reinhard (2005), Graph Theory (3rd ed.), Berlin, New York: Springer-Verlag, ISBN 978-3-540-26183-4, <http://diestel-graph-theory.com/GrTh.html>.
• 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, January 1995. ISBN 0-201-41033-8. 
• 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. 31st. Chapman & Hall/CRC, 2002-11-27. ISBN 1-58488-291-3.