Grafurile in viata de zi cu zi

Grafurile in viata de zi cu zi Proiect realizat de :Popa Horea SerbanZahan PavelCuprinsAplicatii practiceNodurileArboriCabluri de inalta tensiuneSistemeCaile aerieneTeoria grafurilorBibliografieProblema celor 4 culoriProblema celor 7 poduri

Aplicatii practiceCel mai bun exemplu de aplicatie practica in viata reala a grafurilor neorientate sunt hartile rutiere.Putem afla astfel cel mai scurt drum pana intr-un anumit punct sau care puncte de pe harta sunt cel mai usor accesibil.

NodurileNodurile pot fi considerate orase, iar muchiile drumuri; grafurile orientate pot reprezente drumuri cu sens unic intre cladiri.

ArboriGrafurile mai pot arata legaturile dintre anuminte grupuri sau oameni; grafuri orientate pot arata transferul de informatii sau a unorbunuri.Unarbore genealogic este de asemena un graf neorientat.

Cablurile de inalta tensiuneCablurile de inalta tensiune care pornesc dintr-o centrala pot fi si ele reprezentate cu usurinta cu ajutorul unui graf orientat, indicand si directia de deplasare a curentului. In acest caz centrala este un nod sursa.

Sisteme La fel se poate reprezenta si un sistem de canalizare, de incalzire sau reteaua de apa curenta.

Caile AerieneMultitudinea cailor aeriene reprezinta grafuri. Nodurile sunt intersectiile (imaginare) si muchiile sunt rutele (imaginare). Noduri pot fi si aeroporturile.

Teoria grafurilorTeoria grafurilor are numeroase apeluri in chimie, contribuind in mare masura la rezolvarea problemelor de numarare a grafurilor apartinand unor clase speciale.Teoria grafurilor este folosita in domenii variate: de la chimie la economie, de la studiul retelelor electrice la critica textelor de politica, devenind o disciplina majora.

Problema celor 4 culori O problema celebra n teoria grafurilor este problema celor patru culori. Ea este mentionata ntr-o scrisoare din 1852 adresata de catre matematicianul De Morgan lui sir William Hamilton unde se referea la o ntrebarea pusa de studentul Francis Guthrie daca o harta oarecare se poate colora cu cel mult patru culori astfel nct orice doua tari care au o frontiera comuna si care nu se reduce la un punct sa aiba culori diferite

Problema celor 4 culori Raspunsul la aceasta problema a fost obtinut n 1976 cu ajutorul unor programe de calcul de catre Appel si Haken. Legat de aceasta problema s-a introdus numarul cromatic al unui graf neorientat ca fiind numarul minim de culori cu care se pot colora vrfurile sale astfel nct orice muchie sa aiba capetele diferit colorate.

Problema celor 7 poduri Adeseori suntem tentati sa credem simplul fapt de a traversa strazi sau poduri nu implica nici o idee deosebita. Iata nsa ca exista o celebra problema de traversare n care singura idee implicata este aceea de traversare, problema celor sapte poduri din Knigsberg. Aceasta banala si totusi foarte controversata problema a dus la aparitia si dezvoltarea teoriei grafurilor.

Problema celor 7 poduri Orasul Knigsberg era asezat pe coasta Marii Baltice, la gurile rului Pregel. Pe ru erau doua insule legate de tarmuri si ntre ele de sapte poduri ca n figura 1. Oamenii care cutreierau aceste insule au observat ca daca porneau de pe malul sudic al rului, nu puteau sa-si planifice plimbarea astfel nct sa traverseze fiecare pod o singura data. Se parea ca ori trebuia sa sara un pod ori sa-l traverseze de doua ori.

Problema celor 7 poduri n anul 1735 Euler a descoperit ca nu mai are rost sa se ncerce, propunnd urmatoarea analiza a problemei, din punct de vedere matematic. Sa consideram mai nti insula estica (fig.2.). Sunt trei poduri care duc la ea. Deoarece se pleaca de pe malul sudic, nseamna ca se pleaca din afara insulei estice. Deoarece fiecare din cele trei traversari trebuie efectuate o singura data, plimbarea trebuie sa se termine pe insula estica.

Problema celor 7 poduri Sa consideram acum insula vestica. Sunt cinci poduri care duc pe ea, iar cinci este din nou numar impar. Asadar plimbarea ncepe n afara insulei, si deci trebuie sa se termine pe insula vestica. Aceasta nseamna ca plimbarea se termina n doua locuri diferite simultan ceea ce e imposibil. Solutia data de Euler este tipica pentru personalitatea si ingeniozitatea sa. Tot el a scris n anul 1736 prima lucrare de teorie a grafurilor despre problema acestor sapte poduri.

Bibliografie https://grafmcis.wordpress.com/2010/05/12/aplicatii-practice/ http://ro.wikipedia.org/wiki/Graf https://www.google.ro/search?q=graf&espv=2&biw=1366&bih=667&site=webhp&source=lnms&tbm=isch&sa=X&ved=0CAYQ_AUoAWoVChMIopLklrmTxgIVh6HbCh1YrwDe&dpr=1#tbm=isch&q=grafuri