TEORIA GRAFURILOR

TEORIA GRAFURILORCostantea Alexandra , Pop Georgeta Cls XI A Originile teoriei grafurilor se gasesc in rezolvarea unor probleme de jocuri si amuzamente matematice,care au atras atentia unor matematicieni de seama cum ar fi: Euler, Hamilton, Cayley, Sylvester, Birkoff.Data nasterii teoriei grafului este considerata a fi anul 1736, cand matematicianul Leonhard Euler a publicat un articol in care a clarificat problema celor 7 poduri si a prezentat metode pentru rezolvarea altor probleme de acelasi tip.

Cu 200 ani mai tarziu aparea la Leipzic prima carte de teorie a grafurilor al carei autor este matematicianul maghiar Denes Koreg. In amintirea contributiei lui Euler unele notiuni si tipuri de grafuri de care acesta s-a ocupat sunt denumite de catre Koreg lant eulerian ,graf eulerian,etc. Un alt matematician care s-a ocupat de aceleasi probleme ca si Euler, dar care si-a publicat rezolvarile cercetarilor sale in anul 1873 a fost Carl Hierholzer.

Alte izvoare ale teoriei grafurilor sunt:studiul retelelor electrice, problema celor 4 culori, aplicatiile teoriei grafurilor in chimie(initiate de Cayley), probleme hamiltoniene, grafuri planare.Fizicianul Kirchoff a studiat la mijlocul secolului al XIX-lea retele electrice cu metode care apartin astazi teoriei grafului, contribuind la dezvoltarea acestei teorii.

Termenul graf a fost folosit pentru prima data in sensul sau actual in 1878 de matematicianul Sylvester. 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.

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 se pune cam asa: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.

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.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: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.

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.

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

Grafuri din viata de zi cu zi

Atunci cand cineva vorbeste urat despre iphone

E inevitabil

Ce contine o revista pentru femei

Pe care parte a drumului conduc?