Grafs

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. 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.

Definicions Representació de grafs Teoremes Tipus de grafs

Definicions:

Vèrtex / Node: Unitat fonamental de la qual estan formats els grafs.
Aresta / Enllaç: Relació entre dos vèrtexs d'un graf.
Fulla: Vèrtex que té grau 1.
Llaç: Aresta que comença i acaba al mateix node.
Component (o component connex): Subgraf induït en el qual dos vèrtexs qualsevols estan connectats entre si per camins, i que no està connectat a vèrtexs addicionals en la resta de l'graf.
Multigraf (o pseudograf): Graf en el qual trobem algun llaç o en el qual trobem dues arestes idèntiques, és a dir, dues arestes diferents uneixen els mateixos nodes.
Graf simple: Qualsevol graf que no sigui un multigraf.
Grau (o valència): Número d'arestes que incideixen en un vèrtex.
Ordre (d'un graf): Nombre de vèrtexs.
Mida (d'un graf): Nombre d'arestes o arcs.
Camí: Seqüència ordenada d'arestes on el vèrtex final d'una aresta, que no sigui l'ultima, és la inicial de la següent.
Longitud (d'un camí): Nombre d'arestes o arcs que té un camí.
Circuit (o cicle): Camí que comença i acaba en un mateix vèrtex.
Distància (entre dos vèrtexs): Longitud del camí més curt possible entre aquests dos vèrtexs.
Diàmetre (d'un graf): El màxim entre totes les distàncies d'un graf. És a dir, de totes les combinacions possibles de vèrtexs d'un graf.

Representació de grafs

Existeixen moltes formes de representar els grafs, tot i així, ara veurem algunes de les més típiques i estandaritzades.

V = {v1, v2, v3, v4, v5, v6}
E = {{v1, v2}, {v1, v4}, {v1, v5}, {v2, v5}, {v3, v4}, {v3, v5}, {v3, v6}, {v4, v6}}

Aquesta és potser la representació més habitual. Per una banda, tenim V. Inclou tots els nodes o vèrtexs existents a aquell graf. Després tenim E, que representa tots els enllaços entre els nodes anteriors. A la següent figura podem observar quina seria la seva representació gràfica.

Cal destacar que la representació visual d'un graf pot variar molt, i tot i així, continuar sent el mateix graf. Això només depèn de si els nodes i els enllaços entre aquests nodes són els mateixos en ambdós casos.

L'altra manera més habitual de representar grafs és utilitzant matrius d'adjacència. Aquesta matriu quadrada té tantes files i columnes com nodes tingui el graf. Els valors continguts en aquesta matriu indicaran la relació o no-relació entre els nodes.

En cas que sigui un graf no ponderat escriurem un 1 si els dos nodes (fila i columna) estan relacionats, i un 0 si no ho estan.

Si per contra és un graf ponderat, els valors que contindrà seran els pesos de les arestes.

També cal destacar que si el graf NO és dirigit, la matriu serà simètrica.

A la matriu de la dreta podem veure representat el graf anterior.

	v1	v2	v3	v4	v5	v6
v1	0	1	0	1	1	0
v2	1	0	0	0	1	0
v3	0	0	0	1	1	1
v4	1	0	1	0	0	1
v5	1	1	1	0	0	0
v6	0	0	1	1	0	0

Teoremes

Teorema 1 (Euler)

En tot graf G = (V, E), la suma dels graus dels vèrtexs és igual al doble del nombre d'arestes.

D'aquest teorema també podem obtenir una altra afirmació: En tot graf, el nombre de vèrtexs amb grau imparell, és parell.

Teorema 2

Un arbre amb n nodes té n − 1 arestes.

Teorema 3

En un arbre T amb |V| ≥ 2, hi ha com a mínim dos vèrtexs de grau 1 (fulles).

Teorema 4

El nombre de fulles d'un arbre T és més gran o igual a ∆(T), és a dir el nombre de fulles és més gran o igual al grau màxim de l'arbre.

Havel-Hakimi (Seqüència gràfica)

Un conjunt de nombres enters no negatius S = {d₁, ... ,d_n} s'anomena seqüència gràfica si existeix algun graf d'ordre n tal que S és la seqüència de graus del graf.

Resumint: A partir d'una llista amb els graus de tots els vèrtexs d'un graf, podem determinar si aquest graf podria existir o no.

Per tal de verificar si la llista amb els graus és seqüència gràfica o no hem de seguir el següent procediment:

Verificar si es compleixen alguna de les següents característiques. En cas afirmatiu, NO serà seqüència gràfica.
- Algun dels graus és més gran que el nº de nodes - 1, al principi.
- Algun dels graus esdevé negatiu.
- El nombre de graus senars no és parell.
Ordenem la llista de manera decreixent.
Eliminem el nombre més gran (el de més a l'esquerra). En cas de tenir varis nombres iguals, només eliminem un.
Restem 1 als s següents graus de la llista, sent s el número que acabem d'eliminar.
Tornem a reordenar la llista de manera decreixent.
Repetim els passos fins que demostrem que no és seqüència gràfica (punt 1) o fins que tinguem valors molt petits que poguem verificar.

Per exemple, si repetíssim els passos fins a obtenir la llista {1,1}, podríem comprovar fácilment que un graf amb 2 nodes, cadascun d'ells de grau 1, pot existir. O---O

Si vols veure exemples o una explicació més detallada en vídeo, fes clic aquí.

Tipus de grafs

Graf simple: Qualsevol graf que no sigui un multigraf.
Multigraf (o pseudograf): Graf en el qual trobem algun llaç o en el qual trobem dues arestes idèntiques, és a dir, dues arestes diferents uneixen els mateixos nodes.
Graf dirigit: Grafs les arestes dels quals només admeten un sentit.
Graf no dirigit: Graf en el qual els costats no estan orientats (no són arcs).
Graf ponderat: Grafs on cada aresta e està associada a un nombre w(e) anomenat pes o cost, tal que w(e) ϵ R.
Hipergraf: Grafs en els quals les arestes tenen més de dos extrems, és a dir, les arestes són incidents a 3 o més vèrtexs.
Graf infinit: Grafs amb conjunt de vèrtexs i arestes de cardinal infinit.
Graf cíclic: Graf que conté algun cicle simple.
Graf acíclic: Graf que no conté cap cicle simple.
Graf bipartit: Qualsevol graf, els vèrtexs del qual poden ser dividits en dos conjunts, tal que no hi hagi arestes entre els vèrtexs del mateix conjunt. Podem veure que un graf és bipartit si no hi ha cicles de longitud imparell.
Graf complet: Graf on cada vèrtex té un grau igual a n-1, sent n el nombre de nodes del graf.
Graf connex: Un graf és connex si i només si existeix un camí simple per qualsevol parella de nodes del graf.
Graf inconnex: Graf que no és connex.
Graf dens: Graf en el qual el nombre d'arestes és proper al nombre màxim d'arestes que pot tenir el graf.
Graf nul: Graf que té els conjunts d'arestes i de vèrtexs buits.
Graf pla: Graf que és possible dibuixar en el pla sense que cap parell d'arestes es creuin entre si.
Graf aleatori: Graf les arestes del qual estan associades a una probabilitat.
Graf regular: Graf els vèrtexs del qual tenen el mateix grau.

Graf 3-regular
Graf buit: Graf que té el conjunt d'arestes buit.
Graf trivial: Graf buit amb un únic vèrtex.
Arbre: Graf connex i sense cicles.

Algorismes

BFS

La cerca en amplada (de l'anglès BFS - Breadth First Search) és un algorisme utilitzat per recórrer o buscar elements en un graf (principalment en arbres). Es comença a l'arrel (escollint algun node com a element arrel en el cas d'un graf) i s'exploren tots els veïns d'aquest node. A continuació per a cada un dels veïns s'exploren els seus respectius veïns adjacents, i així fins que es recorri tot l'arbre.

Viquipèdia - Cerca en amplada

Característiques:

Permet trobar el camí més curt entre dos nodes, amb la longitud del camí mesurada pel nombre d'arestes.
Permet reconstruir arbres binaris de manera eficient.
Permet comprovar si un graf és bipartit.

Complexitat: O(m) ≤ O(n²)

Procediment:
Per tal de realitzar aquest procés disposarem d'una cua que anirem omplint amb nodes.


1- Comencem amb el node arrel (v) (o seleccionem un node arrel si no és un arbre).
2- Marquem el node (v).
3- Afegim el node (v) a la cua.
Mentre la cua no estigui buida:
	4- Eliminem de la cua el primer node (w).
	Per cada node (x) adjacent a (w) fem:
		Si (x) no està marcat llavors:
			5- Marquem el node (x).
			6- Afegim el node (x) a la cua.

www.cs.us.es/~fsancho

DFS

Una cerca en profunditat (en anglès Depth First Search, DFS) és un algorisme que permet recórrer tots els nodes d'un arbre o graf de manera ordenada, però no uniforme. El seu funcionament es basa a anar expandint cada node que troba, de manera recursiva, recorrent tots els nodes d'un camí concret. Quan ja no queden més nodes per visitar d'aquest camí, es realitza un pas enrere (Backtracking), que permet que pugui tornar a començar el mateix procés amb cadascun dels germans d'un node ja processat.

Viquipèdia - Cerca en profunditat

Característiques:

Permet trobar components connexes.
Permet trobar les arestes de tall d'un graf.
Permet comprovar si un graf és planar.
Permet trobar biconnectivitat en grafs.

Complexitat: O(m) ≤ O(n²)

Procediment:
El procediment que es segueix habitualment en aquest cas és rcursiu. Això vol dir que la funció es va cridant a si mateixa per tornar a repetir un mateix procediment, fins que finalment, el procés acaba. Malgrat això, en aquest cas seguirem un procediment iteratiu perquè sigui més fàcil d'entendre.
Per tal de realitzar aquest procés disposarem d'una pila que anirem omplint amb nodes.


1- Comencem amb el node arrel (v).
2- Afegim el node (v) a la pila.
Mentre la pila no estigui buida:
	3- Treiem un element de la pila (v).
	Si (v) no està marcat com a visitat:
		4- Marquem (v) com a visitat.
		Per qualsevol node que estigui connectat amb (v):
			5- Afegim aquest node a la pila.

www.cs.us.es/~fsancho

Dijkstra

L'algorisme de Dijkstra, també anomenat algorisme de camins mínims, és un algorisme de cerca de camins per determinar el camí més curt donat un vèrtex origen a la resta de vèrtexs en un graf dirigit i amb pesos a cada aresta. El seu nom li ve d' Edsger Dijkstra, qui el va descriure per primera vegada el 1959.

Viquipèdia - Algorisme de Dijkstra

Complexitat (pitjor cas): O(|E| + |V|log|V|)

Procediment:
Per tal de realitzar aquest procés disposarem d'un vector que acabarà contenint les distàncies des del node inicial fins a la resta de nodes.


1- Inicialitzem totes les distàncies del vector amb 
	un valor infinit (o màxim), excepte la del node inicial 
	que serà 0 (la distància del node inicial a ell mateix és 0).
2- Suposant que "a" és el node actual: a = node inicial.
3- Recorrem tots els nodes adjacents de "a", excepte els nodes marcats 
	com a visitats, anomenarem a aquests v_i.
4- Si la distància des del node inicial fins v_i guardada al 
	vector és més gran que la distància des del node inicial fins "a" sumada 
	a la distància des de "a" fins v_i, aquesta se substitueix amb la segona.
5- Marquem com a visitat el node "a".
6- Prenem com a pròxim node actual el de menys valor en el vector i tornem al 
	pas 3 mentre existeixin nodes no visitats.

Kruskal

L'algorisme de Kruskal és un algorisme que serveix per trobar l'arbre generador amb el menor pes que connecta tots els punts d'un graf. Es tracta d'un algorisme voraç, ja que troba l'arbre generador mínim per un graf ponderat connex afegint arcs de pes superior en cada pas. Això significa que troba un subconjunt d'arestes que formen un arbre que inclou cada vèrtex, tal que el pes total de les arestes és el mínim. Si el graf no és connex troba un bosc generador mínim (un arbre generador mínim per a cada component connex).

Viquipèdia - Algorisme de Kruskal

Complexitat (sent m el nombre d'arestes del graf): O(m log m)

Procediment:
Partim d'un graf ponderat amb els seus nodes i enllaços.


1- Dibuixem tots els nodes.
2- Dibuixem l'enllaç de menor pes.
3- Verifiquem si existeix algun cicle.
En cas afirmatiu, eliminem l'enllaç anterior.
4- Tornem a dibuixar l'enllaç de menor pes entre tots els que no haguem fet
	servir encara i repetim el procés fins que tots els nodes estiguin 
	enllaçats, és a dir, fins que tinguem una única component.

Floyd-Warshall

L'algorisme de Floyd-Warshall, descrit l'any 1959 per Bernard Roy, és un algoritme d'anàlisi sobre grafs per trobar el camí mínim en grafs dirigits ponderats. L'algorisme troba el camí entre tots els parells de vèrtexs en una única execució.

Viquipèdia - Algorisme de Floyd-Warshall

Complexitat: O(n³)

Procediment:
El procediment es mostra en pseudocodi.


/* La funció pesAresta retorna el cost del camí que va de i a j
(infinit si no existeix).
n es el número de vèrtexs i pesAresta(i,i) = 0 */

int cami[ ][ ];

/* Una matriu bidimensional. En cada pas de l'algorisme, cami[i][j] 
és el camí mínim de i fins a j usant valors intermedis de (1..k-1). 
Cada cami[i][j] és inicialitzat a pesAresta(i,j) */

procedimient FloydWarshall ()
	per k: = 0 fins a n − 1
	per tot (i,j) en (0..n − 1)
	cami[i][j] = min( cami[i][j], cami[i][k] + cami[k][j] );

Si vols saber més sobre els grafs o vols entrar més en detall en els temes mencionats anteriorment fes clic aquí.

Torna a les guies