Algoritmica

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.