Aplicatii

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.

Advertisements

June 2, 2010 at 5:11 am Leave a comment

Putem calcula usor costul minim/maxim,astfel :

Algoritmi pentru determinarea costului minim/maxim:

Pentru determinarea drumului de cost minim/maxim intre 2 noduri ale unui graf se poate folosi:

1.Algoritmul lui Roy-Floyd

2.Algoritmul lui Dijkstra

Algoritmul lui Roy-Floyd

Algoritmul foloseste un principiu asemanator cu cel care este utilizat pentru determinarea matricei drumurilor:gasirea drumului optim intre 2 noduri oarecare i si j prin descoperirea drumurilor optime care-l compun si care trec prin nodurile k, se face prin transformarea matricei costurilor.
Interpretarea datelor din matricea costurilor obtinute in urma transformarii se face astfel:drumul de la nodul i la nodul j are costul a i,j .Matricea nu furnizeaza info despre etichetele drumului cu costul minim.
Informatiile din matricea costurilor transformata prin algoritmul Roy-Floyd se pot folosi pentru a verifica daca exista drum cu costul minim intre 2 noduri de grafuri,iar in caz afirmativ se poate afisa lungimea lui si se poate descoperi drumul.

Algoritmul lui Dijkstra

Algoritmul Dijkstra construieste drumurile cu costul minim care pornesc de la un nod oarecare x-nodul sursa,pana la fiecare nod din graful G=(A,B), nodul destinatie.Exista o multime cu nodurile care au fost deja selectate-S si o coada de prioritati Q cu nodurile care nu au fost selectate inca:Q=V-S,astfel un nod y este declarat selectat,atunci cand s-a determinat costul final al drumului cu costul min de la nodul sursa x la el.Selectarea unui nodnu este echivalenta cu gasirea drumului cu costul minim deoarece este posibil ca in urma calcularii costului sa rezulte ca nu exista drum de la nodul x la acel drum.
In coada Q prioritatea cea mai mare o are nodul pentru care costul drumului are valoarea cea mai mica dintre toate costurile de drumuri care pornesc de la nodul x la celelalte noduri neselectate inca.La fiecare extragere a unui nod din coada de prioritati Q, nodul este adaugat la multimea S,iar coada de prioritati este reorganizata in functie de acest nod(se calculeaza costul rumurilor de la nodul x la nodurile ramase in coada,considerand ca unele drumuri daca trec si prin nodul extras pot sa-si micsoreze costul).Pentru calcularea drumurilor de lungime minima se intretine o multime in care se memoreaza costul drumurilor de la nodul x la nodurile neselectate,costuri care se recalculeaza la fiecare extragere de nod.
Drumul cu costul minim care porneste din nodul x este format din nodul initial x si creste pana cand coada de prioritati Q nu mai contine noduri.

May 31, 2010 at 2:05 pm Leave a comment

Aplicatii

Arborii reprezintă grafurile cele mai simple ca structură din clasa grafurilor conexe, ei fiind cel mai frecvent utilizaţi în practică.

Etimologie

Arborii au fost studiaţi intensiv de numeroşi matematicieni şi fizicieni.Termenul de arbore a fost folosit pentru prima dată de Cayley, în anul 1857. ;acesta a plecat de la o analogie cu botanica. Arborii au fost studiaţi intensiv de numeroşi matematicieni şi fizicieni.

Putem defini  arborele  binar in modul urmator : un arbore care are un varf numit radacina , al carui grad este 0 , unu sau doi . Daca gradul radacinii este 0 , arborele binar este format numai din radacina . Altfel , radacina se leaga printr – o muchie sau prin doua muchii de unul sau de doua alte noi,varfuri care se deseneaza sub radacina care se numesc fiii(descendenti directi) varfului radacina .

May 20, 2010 at 5:28 am Leave a comment

Arbori

DEF:Se numeste arbore un graf neorientat, conex si fara cicluri.

Se numeste arbore cu radacina un arbore in care exista un nod privilegiat numit radacina.

Se numeste arborescenta sau structura arborescenta un arbore in care s-a stabilit un nod radacina .

Se numeste arbore binar un arbore cu radacina cu proprietatea ca oricare nod poate avea maxim doi descendenti.

Se numeste arbore  binar strict un arbore cu proprietatea cu oricare nod cu exceptia nodurilor terminale are exact doi fii.

Se numeste arbore binar  echilibrat un arbore care are proprietatea ca diferenta inaltimii celor doi subarbori ai sai este maxim 1.

Ex arbore binar strict echilibrat:

Se numeste arbore binar complet un arbore binar care are toate nodurile terminale pe acelasi nivel.

Terminologie:

Nod radacina = un nod special in care nu intra nici o muchie .

Frunze( noduri terminale ) = noduri fara succesori.

In orice  alt nod dintr-un arbore ( diferit de radacina si frunze ) intra cel putin o muchie si iese o muchie.

Predecesorul (parintele) unui nod = nodul de care este legat acesta.

Dintr-un nod pot sa iasa mai multe muchii care il leaga pe acesta de alte noduri numite succesori sau fii.

Doua noduri care au acelasi tata se numesc frati.

Ordinul unui nod este dat de numarul de descendenti directi.

Nodurile sunt organizate pe niveluri . Radacina se gaseste pe nivelul zero , descendentii ei pe nivelul 1 , .. etc.

Inaltime unui arbore este data de numarul maxim dintre nivelurile nodurilor  terminale ( sau este data de lungimea celui mai lung lant care porneste de la radacina si ajunge la un nod terminal ).

Teorema 1 : Orice arbore cu n noduri are ( n-1) muchii.

Teorema 2 : Arbore binar strict care are n noduri terminale are in total ( 2n-1) noduri.

May 18, 2010 at 7:35 pm Leave a comment

Moduri de reprezentare a grafurilor

Se citesc n, numarul nodurilor, si m, numarul muchiilor unui graf, de la tastatura. Se citesc, de asemenea, pe rand, m perechi de numere cu valori cuprinse intre 1 si n,reprezentand muchiile grafului.Sa se memoreze graful

-cu ajutorul matricei de adiacenta

#include<iostream.h>

#define MAX 10

void citire(int &n, int a[MAX][MAX]);

void afisare(int n, int a[MAX][MAX]);

void initializare(int a[MAX][MAX]);

void main()

{int a[MAX][MAX], n;  //a-matricea de adiacenta,n-nr noduri

initializare(a) ;

citire(n,a) ;

afisare(n,a);

}

void initializare(int a[MAX][MAX])  // initializarea matricei

{int i,j;

for(i=0;i<MAX;i++)

for(j=0;j<MAX;j++)

a[i][j]=0;

}

void citire(int &n, int a[MAX][MAX])   //construirea matricei de adiacenta

{int x,y,I,m;

cout<< ‘‘n=’’ ;cin>>n ;

cout<< ‘‘m=’’ ;cin>>m ;  // m-nr muchii

for(i=1;i<=m;i++)

{cout<< “muchia”<<i<< “ : ” ;

cin>>x>>y;

a[x][y]=1;

a[y][x]=1;    //construim matricea simetrica

}

}

void afisare(int n, int a[MAX][MAX])   //afisarea matricei de adiacenta

{int i,j ;

cout<<’’Matricea de adiacenta :’’<<endl ;

for(i=1 ;i<=n ;i++)

{for(j=1 ;j<=n ;j++)

cout<<a[i][j]<< ‘‘ ‘‘;

cout<<endl;

}

}

– cu ajutorul listei de incidenta:

#include<iostream.h>

#define MAX 10

void citire(int &n, int l[MAX][MAX]);

void afisare(int n, int l[MAX][MAX]);

void initializare(int l[MAX][MAX]);

void main()

{int a[MAX][MAX], n;  //l-matricea de adiacenta,n-nr noduri

initializare(l) ;

citire(n,l) ;

afisare(n,l);

}

void initializare(int l[MAX][MAX])  // initializarea matricei

{int i,j;

for(i=0;i<MAX;i++)

for(j=0;j<MAX;j++)

a[i][j]=0;

}

void citire(int &n, int l[MAX][MAX])

{int x,y,I,m;

cout<< ‘‘n=’’ ;cin>>n ;   //n-nr nodurilor

cout<< ‘‘m=’’ ;cin>>m ;  // m-nr muchii

for(i=1;i<=m;i++)

{cout<< “muchia”<<i<< “ : ” ;

cin>>x>>y;    //citim doua noduri adiacente

i[x][0]++;   //indicele de sfarsit a l listei nodului x

i[y]l[x][0]]=y;    //element in lista nodului x

i[y][0]++ ;      //indicele de sfarsit al listei nodului y

i[y]l[y][0]]=x ;    //element in lista nodului x

}

}

void afisare(int n, int l[MAX][MAX])

{int i,j ;

cout<<’’Matricea de adiacenta :’’<<endl ;

for(i=1 ;i<=n ;i++)

{cout<<’’nodul’’<<j<<’’adiacent cu:’’;

for(j=1 ;j<=n ;j++)

cout<<a[i][j]<< ‘‘ ‘‘;  //nodurile adiacente cu nodul i

cout<<endl;

}

}

– cu ajutorul listelor de muchii:

#include<iostream.h>

#define MAX 10

struct muchie    //structura pentru memorarea unei muchii

{intx,y;

};

muchie e[MAX];   //vectorul de muchii

int n,m ;

void citire() ;

void afisare() ;

void main()

{citire() ;

afisare() ;

}

void citire()

{int x,y,i ;

cout<<’’n=’’;cin>>n;

cout<<’’m=’’ ;cin>>m ;   //m-nr muchii

for(j=1;i<=m;j++)

{cout<<’’muchia’’<<j<<’’:’’;

cin>>x>>y;

e[i].x=x      //memoreaza un capat al muchiei

e[i].y=y      //memoreaza al doilea capat al muchiei

}

}

void afisare()

{int i,j;

cout<<’’Graful are’’<<n<<’’noduri’’<<’’si’’<<m<<’’muchii”<<endl;

cout<<’’Muchiile grafului:”<<endl;

for(i=1;i<=m;i++)

cout<<e[i].x<<’’ “<<e[i].y<<endl;   //afiseaza muchia i

}

May 12, 2010 at 6:24 pm Leave a comment

Aplicatii practice

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.

Cablurile 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. La fel se poate reprezenta si un sistem de canalizare, de incalzire sau reteaua de apa curenta.

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

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.

May 12, 2010 at 6:09 pm Leave a comment

Grile

Am selectat cateva grile din variantele de bacalaureat:

1)Care este numărul maxim de componente conexe pe care le poate avea un graf neorientat cu 20 noduri şi 12 muchii?

a. 6 b. 12 c. 10 d. 15

Raspunsd)

2)Câte grafuri neorientate, distincte, cu 4 vârfuri se pot construi? Două grafuri se consideră distincte dacă matricele lor de adiacenţă sunt diferite.

a. 4^6 b. 2^6 c. 6^4 d. 4

Raspuns:b)

3)Într-un graf neorientat cu 10 muchii, fiecare nod are gradul un număr nenul. Doar trei dintre noduri au gradul un număr par, restul nodurilor având gradele numere impare. Care este numărul maxim de noduri pe care poate să le aibă graful?

a. 14 b. 17 c. 10 d. 16

Raspuns: a)

4)Se consideră un graf neorientat cu 10 noduri şi 7 muchii. Care este numărul maxim de componente conexe din care poate fi format graful?

a. 8 b. 7 c. 6 d. 10

Raspuns: c)

5)Care dintre următoarele valori pot reprezenta gradele nodurilor unui graf neorientat cu 6

noduri?

a. 3 2 2 2 3 3 b. 4 2 2 2 3 2 c. 5 2 2 2 0 3 d. 5 2 2 2 1 2

Raspuns: d)

6)Care este numărul maxim de vârfuri de grad 0 pe care le poate avea un graf neorientat cu  10 noduri şi 7 muchii?

a. 5 b. 6 c. 4 d. 7

Raspuns: a)

7)Se consideră graful neorientat G cu 8 noduri, care are următoarele proprietăţi:

– suma gradelor tuturor nodurilor este 12

– graful are exact 3 noduri cu gradul 1

Care este numărul maxim de noduri de grad 0 ale grafului G?

a. 1 b. 4 c. 2 d. 0

Raspuns: a)

8)Care este gradul maxim pe care îl poate avea un nod al unui graf neorientat cu 6 muchii şi 6 noduri dintre care exact două au gradul 0? Care este reprezentarea prin liste de

adiacenţă pentru un astfel de graf?

Raspuns: Grad maxim:3

Lista de adiacenta:

1:2,3,4

2:1,3,4

3:1,2,4

4:1,2,3

5:-

6:-

9)Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, este reprezentat prin matricea de adiacenţă alăturată. Care sunt vârfurile care au gradul maxim?

0 1 1 0 1 1

1 0 1 0 0 1

1 1 0 1 1 0

0 0 1 0 1 0

1 0 1 1 0 0

1 1 0 0 0 0

a. 1 b. 3 c. 1, 3 d. 1, 3, 5

Raspuns: a)

10)Numărul de muchii ale unui graf neorientat cu 12 noduri, în care fiecare nod este adiacent cu exact 11 noduri, este :
a. 144 b. 66 c. 78 d. 11
Raspuns: b)

10)Numărul de muchii ale unui graf neorientat cu 12 noduri, în care fiecare nod este adiacent cu exact 11 noduri, este :

a. 144 b. 66 c. 78 d. 11

Raspuns:b)


May 12, 2010 at 5:53 pm Leave a comment

Older Posts


Categories

  • Blogroll

  • Feeds