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

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

Teoria Grafurilor

No description
by

Draghicescu Darius

on 4 January 2014

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Teoria Grafurilor

Teoria Grafurilor
Începuturi...
Problema celor 7 poduri
Adeseori suntem tentați să credem că simpla
acțiune de a traversa străzi sau poduri nu implică nici o idee deosebită. Iată însa că problema celor șapte poduri din Königsberg demonstrează contrariul. Această banală și totuși foarte controversată problemă a dus la apariția și dezvoltarea teoriei grafurilor. 

Graf neorientat
Graf orientat
Orasul Königsberg era așezat pe coasta Mării
Baltice, la gurile râului Pregel. Pe râu erau două insule legate de țărmuri și între ele de șapte poduri.
Oamenii care cutreierau aceste insule au observat
că dacă porneau de pe malul sudic al râului, nu puteau să-și planifice plimbarea astfel încât să traverseze fiecare pod o singura dată
Se părea ca ori trebuie să sară un pod ori să-l
traverseze de două ori.În anul 1735 Euler a descoperit că nu mai are rost să se încerce, propunând urmatoarea analiză a problemei, din punct de vedere matematic:
Aplicabilitate:
Aplicabilitate în geografie
În geografie, cel mai bun exemplu de
utilizare a grafurilor ar fi reprezentarea rutelor respectiv calculul unor trasee.
În cazul grafurilor orientate, perechile de vârfuri din mulţimea E sunt ordonate şi sunt denumite arce, acestea, din urmă, putând fii parcurse doar în sensul indicat (x,y). Vârful x se numeşte extremitate iniţială a arcului , iar vârful y se numeşte extremitate finală a arcului .
Noțiuni introductive
Un graf este o pereche ordonată de mulțimi, notată G=(X,U), unde X este o mulțime finită și nevidă de elemente numite noduri sau vârfuri, iar U este o mulțime de perechi de vârfuri.*
Există două tipuri de grafuri, și anume:
Grafuri orientate
Grafuri neorientate

În cazul grafurilor neorientate, perechile de vârfuri din mulţimea E sunt neordonate şi sunt denumite muchii, acestea putând fi parcurse în ambele sensuri. Vârfurile x şi y se numesc extremităţile muchiei .

Elemente de bază.
Problema celor 7 poduri

Masterand: Drăghicescu Darius, an I SIG
Graful G(X,U) cu mulțimea vârfurilor X(1,2,3,4,5) respectiv mulțimea muchiilor U((1,2), (1,3), (2,3), (4,5)).
* sursa: http://ro.wikipedia.org/wiki/Graf
sursa: http://ro.wikipedia.org/wiki/Graf
Graful G(X,U) cu mulțimea vârfurilor X(1,2,3,4,5) respectiv mulțimea arcelor U((1,2), (1,3), (1,5), (3,1), (4,2))
sursa: http://ro.wikipedia.org/wiki/Graf
Leonhard Euler (1707-1783) – fizician şi matematician elvețian, a avut contribuţii majore în demonstrarea unor teoreme
matematice, în teoria numerelor, a funcţiilor trigonometrice şi desigur, a grafurilor.
fig.1: graf neorientat
fig.2: graf orientat
fig.3: Leonhard Euler (1707-1783)
fig.4: podurile din Königsberg
Să considerăm insula estică:
Sunt trei poduri care duc la ea.Deoarece
se pleacă de pe malul sudic, înseamnă că se pleacă din afara insulei estice. Deoarece fiecare din cele trei traversări trebuie efectuate o singură dată, plimbarea trebuie să se termine pe insula estică.
fig.5: insula estică
Să considerăm insula estică:
Sunt cinci poduri care duc pe insula, din nou,
număr impar. Așadar plimbarea începe în afara insulei, deci trebuie să se termine tot pe insulă.
Așadar înseamnă că plimbarea se termină în
două locuri diferite simultan, ceea ce este imposibil.
Euler a transpus problema ce i s-a pus intr-o
formă simplificată, utilizând noduri pentru a reprezenta pământul și muchii pentru a reprezenta podurile, dându-i un sens matematic. Deoarece într-un graf doar informația referitoare la vârfuri și muchii este importantă, forma acestuia nu este relevantă.
Soluția dată de Euler este tipică pentru
personalitatea și ingeniozitatea sa. Tot el a scris, în 1736 prima lucrare de teorie a grafurilor.
fig.6: insula vestică
fig.7: reprezentarea sub formă
de graf a problemei
Chiar dacă nu o realizăm, zilnic ne lovim de probleme a căror
rezolvare implică utilizarea conceptului de graf, în numeroase domenii.
Inginerie: retele de transport energie (conducte de gaz, țiței, rețele electrice), trasarea căilor de comunicație, planificarea rutelor de transport,etc.
Economie: rezolvarea unor probleme care implică determinarea unor drumuri critice.
Psihologie: reprezentarea relațiilor interumane
Matematică: teoria mulțimilor
Informatică: dezvoltarea diverșilor algoritmi
Am putea crede că geografia nu folosește acest concept; greșit!
Având în vedere faptul că geografia este o știință interdisciplinară, aceasta utilizează concepte din mai toate domeniile mai sus enunțate, grafuril având o implicație majoră în munca noastră.
fig.8: harta rutieră a României.
Surse de date:
http://en.wikipedia.org/wiki/Seven_Bridges_of_K%C3%B6nigsberg
http://ro.wikipedia.org/wiki/Graf
http://89.121.249.92/2010-2011/Catedre/Informatica/11/graf1.pdf
gsod-calan.wikispaces.com/file/view/grafuri-notiuni+introductive.ppt

Vă mulțumesc pentru atenția
acordată!
Full transcript