Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Els graf i el seu ús a la vida quotidiana

No description
by

Marc Gamez Luque

on 7 April 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Els graf i el seu ús a la vida quotidiana

Els grafs i el seu ús a la vida quotidiana
Marc Gámez Luque
Manel-Àlex García Martín
Ramon Tous Fernàndez
Índex
0. Introducció al treball de camp
1. Teoria
1.1. Què són els grafs?
1.2. Llista d’adjacències
1.3. Matriu d'adjacència
1.4. Recorregut i Euler
1.5. Cicles i Hamilton
1.6. Arbre d’expansió mínima
1.7. Algorismes
1.7.1. DFS I BFS
1.7.2. Dijkstra
2. Metodologia per a la creació d'un graf
3. Punts d'estudi d'un graf
4. Eines informàtiques
5. Conclusions
1.1. Què són els grafs?

Un graf G és un parell (V,A) on anomenarem:

vèrtexs
als elements de V
arestes
als elements d'A
ordre
de G al nombre de vèrtexs
mida
de G al nombre d’arestes
grau màxim i mínim
d'un graf

i
Llista d’adjacència

1. Vèrtexs adjacents:
2, 3

2. Vèrtexs adjacents:
1,3,9

3. Vèrtexs adjacents:
1,2,4,5

4. Vèrtexs adjacents:
3,5,6


5. Vèrtexs adjacents:
3,4,6,8

6. Vèrtexs adjacents:
4,5,7,8

7. Vèrtexs adjacents:
6,8,12,15

8. Vèrtexs adjacents:
5,6,7,9,10,20

9. Vèrtexs adjacents:
2,8,11,20

10. Vèrtexs adjacents:
8,12,13,20
11.
Vèrtexs adjacents:
9,14,19
12.
Vèrtexs adjacents:
7,10,13,15
13.
Vèrtexs adjacents:
10,12,14,16,18
14.
Vèrtexs adjacents:
11,13,19 ,20
15.
Vèrtexs adjacents:
7,12,17
16.
Vèrtexs adjacents:
13,17,18
17.
Vèrtexs adjacents:
15,16
18.
Vèrtexs adjacents:
13,16
19.
Vèrtexs adjacents:
11,14
20.
Vèrtexs adjacents:
8,9,10,14




1.2. Llista d’adjacències

Llista de longitud n on hi ha la posició i conjunt dels vèrtexs adjacents a v
1.3. Matriu d'adjacència

Taula quadrada en forma binària on cada línia i columna representa un vèrtex.


1.4. Recorregut i Euler

Sigui G = (V,A) un graf, i siguin u, v pertanyents a V.

Un recorregut de u a v de longitud k és una seqüència de vèrtexs i arestes del graf.



Un senderó eulerià és un recorregut obert que passa per totes les arestes de G sense repetir-ne cap.

1.5. Cicles i Hamilton

Un cicle és un recorregut tancat de longitud ≥ 3 amb tots els vèrtexs diferents.



Sigui G connex, s’anomena:

Cicle hamiltonià a un cicle que passa per tots els vèrtexs de G.


1.6. Arbre d'expansió mínima

És un graf connex i acíclic.

Consisteix en eliminar d'un graf connex totes les arestes amb major pes per tal d'obtenir un graf amb la mínima mida i que continuï sent connex.



1.7. Algorismes

És un conjunt finit d'instruccions o passos que serveixen per a executar una tasca o resoldre un problema.

Ens hem centrat en tres: el DFS, BFS i el Dijkstra.





2. Metodologia per la creació d'un graf




3. Punts d'estudi en un graf

Connectivitat
Detecció de cicles
Graf Eulerià i/o Hamiltonià
Arbre d’Expansió Mínima
Colorabilitat



Intenció: a partir dels mapes del metro de Barcelona, del municipi d'Esparreguera i el de la muntanya de Montserrat, crear grafs i estudiar-los.
0. Introducció al treball de camp
5. Conclusions

És possible moure’ns per les diferents línies del metro sense repetir cap estació.

No es poden recòrrer els barris d’Esparreguera sense passar pel barri del centre una sola vegada.

Sí es pot visualitzar un itinerari de Montserrat com a graf.

Conclusió final: importància dels grafs a la vida quotidiana.



4. EINES INFORMÀTIQUES




UCINET I NETDRAW


GRAF DEL BARRI DEL CENTRE D'ESPARREGUERA
GRAF DEL METRO DE BARCELONA
GRAF DEL METRO DE BARCELONA
GRAF DEL METRO DE BARCELONA
GRAF DELS BARRIS D'ESPARREGUERA
GRAF DE MONTSERRAT

Full transcript