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. 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 primer problema conegut de la teoria de grafs és el problema dels set ponts de Königsberg. Fou plantejat per Leonhard Euler el 1736 .
Definicions
Xarxa és un conjut d'elements o nodes units per enllaços físics. Un graf és un objecte matemàtic que permet modelar una xarxa.
En el sentit més habitual del terme,Vegeu, per exemple, Iyanaga & Kawada, 69 J, p. 234 o Biggs, p. 4. un graf simple és un parell ordenat , format per un conjunt finit no buit V de vèrtexs o nodes o punts juntament amb un conjunt finit E darestes 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 ordenat dels vèrtexs respecte de l'aresta en qüestió).
Altres definicions de graf parteixen de diferents concepcions del conjunt d'arestes. En un sentit més general,Vegeu, per exemple, Graham et al., p. 5. V és un conjunt amb una relació dincidència que associa dos vèrtexs amb cada aresta. En un altre sentit, E és un multiconjunt de parells no ordenats de vèrtexs (no necessàriament diferents).
Multigraf és un graf que conté parells de vèrtexs units per més d'una aresta. Observem que els vèrtexs Q i S estan units per 2 arestes i els vèrtexs T i S per 3 arestes. center|miniatura|600x600px|Multigraf
Un llaç o bucle és una aresta que uneix un vèrtex amb ell mateix,
Pseudograf és un multigraf amb llaços.
center|miniatura|Pseudograf
Graf dirigit o dígraf és un graf amb els enllaços o arestes, que ara es diran arcs, que van en una única direcció. Un arc és, en aquest cas, un parell ordenat de vèrtexs.
miniatura|Graf dirigit o dígraf|center
Un recorregut en un graf és una manera d'assolir un vèrtex des d'un altre recorrent un conjunt d'arestes una darrera l'altra. center|miniatura|500x500px|Graf dirigit
Per exemple, P Q R és un recorregut per anar del vèrtex P a l'R. Aquest recorregut té longitud 2.
P S Q R S T és un recorregut per anar del vèrtex P al T. Aquest recorregut té longitud 5.
Un recorregut en el qual els vèrtexs apareixen una sola vegada s'anomena cami.
P Q R S és un camí per anar de P a S.
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. Lordre d'un graf és |V|, el nombre dels seus vèrtexs. La grandària o mida 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 o llaç) es compta dos cops. El grau d'un vèrtex es simbolitza amb la lletra d. d(número de vèrtex)=número d'arestes que hi conflueixen.
Per a una aresta }, hom acostuma a emprar la notació més breu xy.miniatura|Representació d'un graf amb 6 vèrtexs i 7 arestes
V=conjunt de vèrtexs= {1,2,3,4,5,6}
E=conjunt d'arestes= {(6,4),(4,5),(5,1),(1,2),(2,3),(3,4),(5,2)}
Lordre de G és el número de vèrtexs que té. n=|V|= ordre de G. En la figura tenim n=6.
La mida de G és el número d'arestes que té. m=|E|=mida de G. En la figura tenim m=7.
El graf de la figura té ordre 6 i mida 7.
El vèrtex 4 té grau 3. És a dir, d(4)=3
Seqüència de graus: 2,3,2,3,3,1
Graus de cada vèrtex d(1)=2, d(2)=3, d(3)=2, d(4)=3, d(5)=3, d(6)=1
En tot graf, la suma dels graus de tots els vèrtexs és el doble del nombre d'arestes. d(v)=2m.
Dos vèrtexs són adajcents si hi ha una aresta que els uneix. Per exemple, els vèrtexs 4 i 5 són adjacents.
El joc del dodecaedre(Hamilton, 1859) és un exemple de graf. Es tracta de trobar un camí que passi per cada ciutat(vèrtexs) una única vegada.
+ E(G1miniatura|Camí de Hamilton en 3Dminiatura|Camí de Hamilton
Connexió Podem combianr 2 grafs per fer un graf més gran. Si els dos grafs són G1=(V(G1), E(G1)) i G₂=(V(G₂), E(G₂)) són disjunts aleshores la seva unió G1G2 és el graf amb vèrtexs V(G1) V(G₂) i la família d'arestes E(G1) E(G₂).
Graf connex
És un graf que no es pot expressar com la unió de dos grafs.
I és no connex en cas contrari.
Cada graf no connex G es pot expressar com la unió de grafs connexos, cadascun dels quals s'anomena component de G.
Exemple
El graf G és no connex amb tres components +miniatura|Graf no connex amb tres components connexes
Representació Representacions d'un graf
Encara que és convenient representar un graf per un diagrama de punts units per línies, aquesta representació pot ser inadequada si volem emmagatzemar un graf gran en un ordinador. Podem epresentar un graf amb una llista o amb una matriu.
1.- Amb una llista
Una manera de representar un graf simple és utilitzant una llista dels vèrtexs adjacents a cada vèrtex.
Observem el graf següent: +miniatura|Graf amb els vèrtexs etiquetatsu: v,y v: u,w,y
w: v,x,y
x: w,y
y: u,v,w,x Hem construït una llista.
2.-Amb matrius
Si G és un graf etiquetat {1,2,3,.....n}, la seva matriu d'adjacència A, és la matriu que té com entrada ij el número d'arestes que uneixen el vèrtex i amb el vèrtex j.
En l'exemple següent n=4 (4 vèrtexs). +miniatura|Graf etiquetat
A=
Si a més, les arestes estan etiquetades {1,2,3,.....m}, la matriu d'incidència M és la matriu nxm que té un 1 a la posició ij si el vèrtex i és incident amb l'aresta j i 0 altrament.
La primera fila de la matriu és: 1 perquè el vèrtex 1 és incident amb l'aresta 1, 0 perquè el vèrtex 1 no és incident amb l'aresta 2, 0 perquè el vèrtex 1 no és incident amb l'aresta 3, 1 perquè el vèrtex 1 és incident amb l'aresta 4, 0 perquè el vèrtex 1 no és incident amb l'aresta 5, 0 perquè el vèrtex 1 no és incident amb l'aresta 6. I anàlogament les altres files.
M=
Aplicacions miniatura|Molécula d'aigua miniatura|Molècula d'aspirina miniatura|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
Els grafs es poden usar per modelar diferents tipus de relacions i processos en sistemes físics, biològics, socials i d'informació. Molts problemes pràctics es poden representar mitjançant grafs. les molècules d'aigua i d'aspirina, per exemple es poden representar amb un graf.
A partir de mitjans del , l'aparició dels ordinadors i el desenvolupament de les telecomunicacions donen un gran impuls a la teoria de 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, morfologia 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 d'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. 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.