Algoritmica

Incarcat la data: 05 Iulie 2011

Autor: garajdieru valentina

Pret: 80 credite

Numar pagini: 107

Tip fisier: zip

Marime fisier: 1205145 kb

Teoria grafurilor, la inceputurile ei, s-a dezvoltat paralel cu algebra. Grafurile au multiple aplcatii practice, fiind strans legate de multe ramuri ale matematicii (cercetari operationale, teoria grupurilor, teoria numerelor), dar sunt folosite si ca modele matematice in rezolvarea unor probleme tehnice, economice, etc. Studiul grafurilor isi are originea in lucrarile lui Euler din 1736, in care studia problema podurilor de la Königsberg.

 

Orasul Königsberg se afla aproape de punctual de varsare a raului Pregolea in Marea Baltica. Raul are pe teritoriul orasului doua brate confluente iar in punctual de confluenta se afla o insula, numita “Curtea Hanului”1. Aceasta insula este legata de maluri prin cinci poduri. Peste fiecare brat al raului mai exista cate un pod. Problema care a aparut cerea sa se gaseasca un traseu continuu care sa treaca o singura data pe fiecare din cele sapte poduri.(vezi figura 1.) Euler a fost primul care a aratat ca aceasta problema nu are solutie.

 

Prima carte de teoria grafurilor a fost publicata de D. König in 1936, Theorie der endlichen und unendlichen Grphen, urmata de cartea lui C. Berge in 1957 Théorie des graphes et ses applications. Fie X o multime finita nevida, X={x1, x2 ,…,xn }. Se numeste graf o pereche G = (X, U) formata din multimea X de varfuri sau noduri si din multimea U={u1, u2, …, um } de perechi de varfuri numite arce sau muchii. Reprezentarea grafurilor poate fi facuta in diferite moduri in functie de cine este “utilizatorul”. Daca este calculatorul, este de preferat ca graful sa fie dat cu ajutorul matricei sale de adiacenta.

 

Altfel, oamenii, prefera vizualizarea grafului sub forma unei colectii de puncte legate prin linii, ceea ce implica darea unor informatii geometrice despre graf. Cardinalul multimii X, se noteaza |X|, si se numeste ordinul grafului G. in cele ce urmeaza vom lucra numai cu grafuri finite. in multimea U putem avea mai multe perechi identice. Daca numarul lor nu depaseste un numar natural q, spunem ca G este un q-graf

 

Un 1-graf se mai numeste si graf orientat. in aceasta situatie U este o submultime a produsului cartezian XX×. Atunci orice element este o pereche ordonata, de forma Uu∈),,(yxu=cu Xyx∈,si il numim arc. Varful x se numeste extremitatea initiala iar varful y se numeste extremitatea finala. in acest caz varfurile x si y se numesc adiacente.

 


Fie X o multime finita nevida, X={x1, x2 ,…,xn }. Se numeste graf o pereche G = (X, U) formata din multimea X de varfuri sau noduri si din multimea U={u1, u2, …, um } de perechi de varfuri numite arce sau muchii. Reprezentarea grafurilor poate fi facuta in diferite moduri in functie de cine este “utilizatorul”. Daca este calculatorul, este de preferat ca graful sa fie dat cu ajutorul matricei sale de adiacenta. Altfel, oamenii, prefera vizualizarea grafului sub forma unei colectii de puncte legate prin linii, ceea ce implica darea unor informatii geometrice despre graf.

 

Cardinalul multimii X, se noteaza |X|, si se numeste ordinul grafului G. in cele ce urmeaza vom lucra numai cu grafuri finite. in multimea U putem avea mai multe perechi identice. Daca numarul lor nu depaseste un numar natural q, spunem ca G este un q-graf

 

Un 1-graf se mai numeste si graf orientat. in aceasta situatie U este o submultime a produsului cartezian XX×. Atunci orice element este o pereche ordonata, de forma Uu∈),,(yxu=cu Xyx∈,si il numim arc. Varful x se numeste extremitatea initiala iar varful y se numeste extremitatea finala. in acest caz varfurile x si y se numesc adiacente.
 

Textul de mai sus reprezinta un extras din "Algoritmica". Pentru versiunea completa a documentului apasa butonul Download si descarca fisierul pe calculatorul tau. Prin descarcarea prezentei lucrari stiintifice, orice utilizator al site-ului www.studentie.ro declara si garanteaza ca este de acord cu utilizarile permise ale acesteia, in conformitate cu prevederile legale ablicabile in domeniul proprietatii intelectuale si in domeniul educatiei din legislatia in vigoare.

In cazul in care intampini probleme la descarcarea fisierului sau documentul nu este nici pe departe ceea ce se doreste a fi te rugam sa ne anunti. Raporteaza o eroare

Important!

Referatele si lucrarile oferite de Studentie.ro au scop educativ si orientativ pentru cercetare academica.

Iti recomandam ca referatele pe care le downloadezi de pe site sa le utilizezi doar ca sursa de inspiratie sau ca resurse educationale pentru conceperea unui referat nou, propriu si original.

Alti utilizatori au mai cautat: PROBLEMEgrafurialgoritmica
Jacheta usoara verde oliv inchis Jacheta usoara verde oliv inchis Descriere produs:Tip: jachetaCuloare: verde oliv inchisMaterial: usorDetalii: margini...
Jacheta usoara violet inchis Jacheta usoara violet inchis Descriere produs:Tip: jachetaCuloare: violet inchisMaterial: usorDetalii: margini...
Camasa alba in dungi Camasa alba in dungi Descriere produs:- camasa alba cu dungi albastre- imprimeu text pe partea din spate- guler...