Grafurile in Viata Reala [PDF]

Zitiervorschau

Grafurile in viata reala

Crișan Vlad Cosma Natan XI A

Cel 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.Nodurile pot fi considerate orase, iar muchiile drumuri; grafurile orientate pot reprezente drumuri cu sens unic intre cladiri. De asemenea, ne putem reprezenta

traiectoria unei calatorii cu ajutorul unui lant al unui graf neorientat.

Grafurile mai pot arata legaturile dintre

anuminte grupuri sau oameni; grafuri orientate pot arata transferul de informatii sau a unor bunuri.Un arbore genealogic este de asemena un graf neorientat.

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

Un exemplu de graf orientat este: reţeaua de străzi a unui oraş. Străzile sunt muchii în graf, iar intersecţiile reprezintă vârfurile grafului. Întrucât mergând pe jos ne putem deplasa pe orice stradă în ambele sensuri, vom spune că din punctul de vedere al pietonilor, „graful unui oraş”este neorientat.

Cu totul altfel stau lucrurile în ceea ce priveşte conducătorii auto, pentru că în orice oraş există străzi cu sens unic. Pentru un şofer străzile trebuie să primească în graf o anumită orientare. Desigur că acele străzi pe care se poate circula în ambele sensuri vor primi orientare dublă. Am ajuns astfel la noţiunea de graf orientat.

Problema Un exemplu de graf din lumea reala

reprezinta drumurile dintre orase. De exemplu, doresc sa aflu daca intre doua orase exista drum care le leaga. Luand doua orase la intamplare,vrem sa stim daca exista drum intre ele.

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 încât orice doua tari care au o frontiera comuna si care nu se reduce la un punct sa aiba culori diferite. 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 vârfurile sale astfel încât orice muchie sa aiba capetele diferit colorate.

Problema podurilor  Să se găsească daca este posibil, o modalitate de

traversare a tuturor celor 7 poduri (notate de la “a” la “g”) parcurgindu-le o singura data pe fiecare, cu reintoarcere in locul de plecare. Notatia “A” – “D” reprezinta portiuni de uscat

Problema podurilor poate fi “transcrisă” folosind

notaţii specifice teoriei grafurilor prin utilizarea unor segmente (ce marchează calea de urmat) şi cercuri (ce marchează intersecţia unor căi figurate prin segmente)