INFORMATIC Ă PROIECT INTEL TEACH

17
INFORMATICĂ PROIECT INTEL TEACH

description

INFORMATIC Ă PROIECT INTEL TEACH. Grafuri neorientate. - PowerPoint PPT Presentation

Transcript of INFORMATIC Ă PROIECT INTEL TEACH

Page 1: INFORMATIC Ă PROIECT INTEL TEACH

INFORMATICĂ

PROIECT INTEL TEACH

Page 2: INFORMATIC Ă PROIECT INTEL TEACH

Grafuri neorientate

• DEFINITIE: GRAFUL este o mulțime ordonată de forma (X,U) în care X, mulțimea vârfurilor sau nodurilor,e diferită de mulțimea vidă și este finită, iar U este mulțimea muchiilor sau arcelor, adică mulțimea de perechi neordonate de câte două elemente din x.

Page 3: INFORMATIC Ă PROIECT INTEL TEACH

Un graf neorientat poate fi reprezentat sub forma unei figuri geometrice alcatuită din puncte

(vârfuri, noduri) și linii drepte sau curbe ce unesc aceste puncte (muchii,arce). Așadar pentru grafuri neorientate vom folosi termenii de”varf”si “muchie”.

Page 4: INFORMATIC Ă PROIECT INTEL TEACH

EXEMPLU

X={x1,x2,x3,x4,x5,x6,x7} U={[1,2],[2,3],[2,4],[3,4]}

1u1

2

34

5 6

u2 u3

u4

u57

Page 5: INFORMATIC Ă PROIECT INTEL TEACH

• GRADUL UNUI VÂRF reprezintă numărul

muchiilor ce trec prin vârful (nodul) respectiv.• VÂRFUL IZOLAT este vârful care are gradul 0.• VÂRFUL TERMINAL este vârful care are

gradul 1.• TEOREMA: Într-un graf G=(X,U) cu n vârfuri și

m muchii, suma gradelor tuturor vârfurilor este egală cu 2*numărul muchiilor.

Page 6: INFORMATIC Ă PROIECT INTEL TEACH

• Un graf complet este graful G(X,U) în care pentru oricare două vârfuri, există muchii (oricare două vârfuri sunt adiacente).

• Graf partial este graful G1=(X,V) în care V mai mic sau egal cu U (este graful inițial din care se scot niște muchii

Page 7: INFORMATIC Ă PROIECT INTEL TEACH

Exemplu de graf complet cu 4 vârfuri

4

3

1

2

Page 8: INFORMATIC Ă PROIECT INTEL TEACH

Exemplu de graf parțial

1

2

34

5 67

Graful inițial

G=(X,U)

1

2

34

5 67

Graful parțial

G1=(X,V)

Page 9: INFORMATIC Ă PROIECT INTEL TEACH

Algoritmul Roy - Floyd Fie G = (V, E, w), unde V={x1, x2, …, xn}. Algoritmul Roy-Floyd determină atât valorile

distanţelor minime între oricare două vârfuri ale grafului, cât şi drumurile minime corespunzătoare şi se bazează pe următoarea teoremă:

Exemplul Fie graful din figura 2.2.2.1. Trebuie să găsim costurile minime de transport, între oricare două puncte ale grafului. Cu alte cuvinte, trebuie să se determine matricea valorilor minime dintre vârfurile grafului şi drumurile corespunzătoare acestor trasee optime.

Algoritmi pentru determinarea drumurilor minime

Page 10: INFORMATIC Ă PROIECT INTEL TEACH

Algoritmul Roy-Floyd• #include<fstream.h> • #include<conio.h>• #define inf 10000 // pentru "infinit" • int n,m,W[50][50],WM[50][50],d[50],nr=0;• void citire_graf()• { int i,j,cost,k;• ifstream f("roy.txt"); f>>n>>m;• for(i=1;i<=n;i++)• for(j=1;j<=n;j++)• if(i==j) W[i][j]=0;• else W[i][j]=inf;• for(k=1;k<=m;k++)• { f>>i>>j>>cost;• if ((i!=j)&&(cost<W[i][j]))• W[i][j]=cost; }}• void afisare(int M[50][50],int nM)• { int i,j;• for(i=1;i<=nM;i++)• { for(j=1;j<=nM;j++)• { gotoxy(3*j,wherey());• if (M[i][j]==inf) cout<<'\354';• else cout<<M[i][j];}• cout<<endl;}}

Page 11: INFORMATIC Ă PROIECT INTEL TEACH

• void Roy_Floyd() // determina matricea WM a distantelor minime• { int k,i,j;• for(i=1;i<=n;i++)• for(j=1;j<=n;j++) WM[i][j]=W[i][j];• for(k=1;k<=n;k++)• { for(i=1;i<=n;i++)• for(j=1;j<=n;j++)• if(WM[i][k]+WM[k][j]<WM[i][j]) WM[i][j]=WM[i][k]+WM[k][j];}}• void drumuri_minime(int x,int y) // pt. gasirea drumurilor minime d de la x la y• { int z,i;• if (WM[x][y]==inf) cout<<"Nu exista drum!"<<endl;• Else { d[++nr]=x;• if(x==y)• { for(i=1;i<=nr;i++)cout<<d[i]<<" "; // afisare drum minim• cout<<endl;}• else for(z=1;z<=n;z++)• if((z!=x)&&(W[x][z]+WM[z][y]==WM[x][y])) drumuri_minime(z,y);• --nr;} }• void main(void)• { int x,y;• citire_graf();• cout<<"Matricea distantelor directe:\n";• afisare(W,n); Roy_Floyd();• cout<<"Matricea distantelor minime:\n";• afisare(WM,n);• cout<<"Dati nodul initial: x=";cin>>x; Roy Floyd• cout<<"Dati nodul final: y=";cin>>y; • cout<<"Drumurile minime de la nodul "<<x<<" la nodul "<<y<<":\n";• drumuri_minime(x,y);}

Page 12: INFORMATIC Ă PROIECT INTEL TEACH

2.3. Arbori 2.3.1. Definiţii şi elemente de bază• În clasa grafurilor conexe, arborii reprezintă

grafurile cele mai simple (ca structură) şi, de asemenea, cele mai frecvent utilizate în practică. De studiul lor s-au ocupat matematicieni şi fizicieni de seamă: Cayley a studiat arborii pentru aplicaţiile lor în chimia organică, iar Kirchhoff, a studiat accastă categorie de grafuri pornind de la studiul reţelelor electrice. Termenul do arbore a fost introdus de Cayley în 1857, plecând de la o analogie botanică.

• Definiţia 2.3.1.1. Se numeşte arbore un graf conex şi fără cicluri.

2.3.2. Arbore parţial de cost minim. Fie un graf G =(V, E) conex, V = {1, 2, ..., n}, şi o

funcţie C:ER+ asociază fiecărei muchii u, un număr real pozitiv c(u), numit costul său.

Problemă: Să se determine un graf parţial H al lui G care să fie conex şi să aibă costul minim.

Page 13: INFORMATIC Ă PROIECT INTEL TEACH

2.3.2.1. Algoritmul lui Kruskal • Acest algoritm a fost stabilit de Kruskal în anul 1956 şi

de cele mai multe ori referirea la algoritm se face folosind numele autorului

• Descrierea algoritmului: Se porneşte iniţial cu un graf parţial al grafului G care nu conţine nici o muchie, deci conţine n vârfuri izolate. Se poate aşadar considera ca sunt n arbori disjuncţi. La pasul k (k=0, 1, ..., n-2) al algoritmului avem n-k arbori disjuncţi. Obţinem astfel prin unificarea a doi dintre arborii existenţi, aleşi intr-un anumit mod, n-k-1 arbori disjuncţi. Alegerea celor doi arbori ce vor fi unificaţi se face în felul următor: dintre toate muchiile nealese încă, se selectează aceea de cost minim care are cele două extremităţi în doua mulţimi diferite (aceasta condiţie se impune pentru ca adăugarea unei muchii să nu provoace apariţia unui ciclu în graful parţial de cost minim ce se construieşte din aproape în aproape). Evident, după pasul n-2 obţinem un singur arbore.

Page 14: INFORMATIC Ă PROIECT INTEL TEACH

Algoritmul lui Kruskal

Adaug muchia (1,2) cost 2

Adaug muchia (2,3) cost 3

Adaug muchia (3,5) cost 4

Adaug muchia (2,4) cost 7

Adaug muchia (4,6) cost 6

Adaug muchia (6,7) cost 9

Nu adaug muchia (1,5)!!!

1

65

4

2

7

3

3

7

5

46

12

2

8

9

Nu adaug muchiile (3,6); (5,6)!!!Cost total:

2+3+4+6+7+9=31

Page 15: INFORMATIC Ă PROIECT INTEL TEACH

ALGORITMUL LUI KRUSKAL

Kruskal

Page 16: INFORMATIC Ă PROIECT INTEL TEACH

Atât tema cât şi modalităţile de abordare

utilizate şi rezultatele obţinute sunt de un real interes didactic şi ştiinţific. Din punctul de vedere al aplicabilităţii în procesul de predare-învăţare-evaluare se remarcă atât complexitatea aspectelor care permit corelarea cu demersul instructiv-educativ, cât şi eficienţa procedeelor de analiză adoptate. Toate  acestea trebuie corelate cu pertinenţa analizei ştiinţifice de specialitate, din perspectiva căreia observaţiile dovedesc o certă acurateţe a demersului întreprins.

Page 17: INFORMATIC Ă PROIECT INTEL TEACH

ÎN URMA ACESTEI PREZENTĂRI SUNT SIGUR CĂ AM DAT O MÂNĂ DE AJUTOR CELOR CARE NU AU HABAR

DE GRAFURI…