Repas Grafs

Grafs

1/4 Concepte

•

Vèrtex

Arc

a

b

Aresta

a

b

Arc

• •

Aresta

a

b

a

“a està connectat amb b (a la inversa no ho sabem)”

b

b

“a està connectat amb b, i b està connectat amb a”

=

a

Notació gràfica

Arcs vs Arestes

•

a

Graf = formalisme per descriure la relació entre un conjunt d’objectes anomenats vèrtex. Entre dos vèrtex pot existir una connexió anomenada aresta o arc. Dos vèrtex connectats es diu que són adjacents.

• •

Aresta i arc indiquen diferents tipus de connexió: o Arc: unidireccional o Aresta: bidireccional Graf dirigit: un graf on només hi han arcs. Graf no dirigit: un graf on només hi han arestes

b

Graf dirigit

d a

•

b c

G = ( V, E ) V = { a, b, c, d } E = { (a, b), (b, d), (d, b), (c, b), (d,a) }

•

Un graf dirigit G és un parell (V,E) on: o V és un conjunt de vèrtexos. o E és un conjunt d’arestes. Cada aresta és un parell ordenat de vèrtexos. Parell ordenat: L’arc (a, b) no és igual a l’arc (b, a)

Definició formal

Grafs

2/4

•

c a

b d

G = ( V, E ) V = { a, b, c, d } E = { {a,b}, {b,c}, {b,d}, {c,d} }

•

Un graf no dirigit G és un parell (V,E) on: o V és un conjunt de vèrtexos. o E és un conjunt d’arestes. Cada aresta és un parell no ordenat de vèrtexos. Parell no ordenat: Considerem {x,y} i {y,x} la mateixa aresta.

Graf no dirigit Definició formal

Subgraf

• •

Un subgraf d’un graf és un subconjunt dels vèrtex i arestes. Formalment, un subgraf G’ = (V’, E’) d’un graf G = (V, E) ha de satisfer: o V’ ⊆ V o E’ ⊆ E o E’ ⊆ V’ × V’

Graf complet Clique

K2

K3

• • • •

K4

3-clique

Un graf complet és aquell que té totes les arestes possibles. Un graf complet amb n vèrtex s’anomena Kn. Un graf complet amb n vèrtex té n*(n-1)/2 arestes. Un subgraf complet d’un altre graf s’anomena clique.

Grafs

3/4 Camí Cicle

c a

z

b x

d

Camí? Si Si No Si

c→ b → a b→ d → c→ b s→ x s→ z → x→ s

b

c

a

d

x

s

Cicle? No Si No Si

e Cicle: b→c→e→d→b

z

Cicle: x→ s→ z→x

s

Graf cíclic – conté algun cicle

b

•

c

•

Un camí en un graf G=(V,E) és una seqüència sense repeticions de vèrtex de V, on cada vèrtex està connectat amb el següent de la seqüència. Un camí tancat (el primer i l’últim vèrtex són iguals) s’anomena cicle o circuit.

b

c

a

d z x

s

Graf acíclic – no conté cap cicle

b

c d

d a a

e

Graf cíclic Graf acíclic

e

e

Cicle: a → b → c → d → e → a

Cicle: e → a → b → c → e →d→b→e

Cicle hamiltonià – cicle que passa per tots els vèrtex (sense repeticions)

Cicle eulerià – cicle que passa per totes les arestes (es poden repetir vèrtex però no arestes)

Cicle hamiltonià Cicle eulerià

Grafs

4/4

a

b a 0 1 0

a b c

c b 1 0 1

a

c 0 1 0

a b c

Matriu d’adjacència M[x, y ] = 0 o 1 • 0: x no està connectat amb y • 1: x està connectat amb y

b

c

Estructura de dades: Implementació

b a

c

b

Llistes d’adjacència L(x) = llista encadenada dels nodes als que es pot accedir des de x

Si considerem un graf amb n vèrtex i m arestes, la representació d’un graf en memòria té una mida polinòmica: O(n2) per matrius i O(n + m) per llistes.

Operacions sobre grafs

Totes les operacions següents es poden fer en temps polinòmic: 1. 2. 3. 4. 5. 6. 7.

Creació d’un graf. Inserció / esborrat d’un vèrtex / aresta. Donats dos vèrtex, decidir si són adjacents. Donat un vèrtex, obtenir la llista de vèrtex adjacents. Donats dos vèrtex decidir si hi ha un camí entre ells. Donat un graf, decidir si és un graf acíclic. Donat un graf, decidir si és un graf complet.

2

a

1

4

b

• 5

0

c 3

b 8

d Camí mínim entre a i d: a→b→c→d Cost del camí mínim: 2+1+3=6

•

•

Podem afegir informació (etiquetes) a les arestes d’un graf. Pot tenir diferents significats: distància, temps, cost, ... El camí mínim entre dos vèrtex (shortest path) és el camí on la suma d’etiquetes és mínima. El camí mínim entre dos vèrtex es pot calcular en temps polinòmic (Dijkstra).

Cerca de camins mínims