Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  


AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Grafuri - graf orientat

c

+ Font mai mare | - Font mai mic





DOCUMENTE SIMILARE

Trimite pe Messenger
Operatori logici pe biti
Nume de variabile
Switch
Structuri cu autoreferire
Intrari si iesiri standard-getchar si putchar
Tablouri de pointeri, pointeri pe pointeri
O colectie de programe utile
Operatori de incrementare si decrementare
Bucle - While si For
STRUCTURI DE GRAF - GRAFURI CA STRUCTURI DE DATE

TERMENI importanti pentru acest document

Grafuri

Aspecte teoretice




Un graf este o pereche G = (VM), unde V este o multime de varfuri, iar M   V V este o multime de muchii.

Definitii

Se numeste graf neorientat o pereche ordonata de multimi notata G=(V, M) unde:

V: este o multime finite si nevida, ale carei elemente se numesc noduri sau varfuri;

M: este o multime, de perechi neordonate de elemente distincte din V, ale carei elemente se numesc muchii.

Exemplu de graf neorientat:

G=(V,M) unde: V= .

M=,,}

Perechea G este graf neorientat deoarece respecta definitia prezentata mai sus, adica:

V:este finite si nevida;

M:este o multime de perechi neordonate(submultimi cu doua elemente)de elemente din V.

Se numeste graf orientat o pereche ordonata de multimi notata G = (V, U), unde:

V: este o multime, finita si nevida, ale carei elemente se numesc noduri sau varfuri;

U: este o multime, de perechi ordonate de elemente distincte din V, ale carei elemente se numesc arce.

Exemplu de graf orientat:

G = (V, U) unde: V =

U = , , }

Perechea G este graf orientat deoarece respecta definitia prezentata mai sus, adica:

V:este finite si nevida;

M:este o multime de perechi ordonate de elemente din V.

In continuare, pentru grafurile neorientate, vom nota submultimea, care reprezinta o muchie, cu [x, y] (intr-un graf neorientat muchia [x, y] este aceeasi cu muchia [y,x]) iar, pentru un graf orientat submultimea , care reprezinta un arc, cu (x, y) (intr-un graf orientat arcul (x, y) este diferit de arcul (y, x)) In baza celor spuse anterior, graful neorientat prezentat in exemplul de mai sus se reprezinta textual astfel:

G=(V, M) unde: V=

M= ,

iar cel orientat astfel:

G=(V, M) unde: V=

M=

Doua varfuri unite printr-o muchie (graf neorientat) sau printr-un arc (graf orientat) se numesc adiacente.

Un drum este o succesiune de muchii sau arce de forma

            [a1a2],    [a2a3], , [an-1an]
sau de forma
            (a1,  a2), (a2a3), , (an-1an)

dupa cum graful este orientat sau neorientat.

Lungimea drumului este egala cu numarul muchiilor sau al arcelor care il constituie. Un drum simplu este un drum in care nici un varf nu se repeta. Un ciclu este un drum care este simplu, cu exceptia primului si ultimului varf, care coincid. Un graf aciclic este un graf fara cicluri. Un subgraf al lui G este un graf (V',  M'), unde V'   V, iar M' este formata din muchiile din M care unesc varfuri din V'. Un graf partial este un graf (VM'), unde M'   M.

Un graf neorientat este conex, daca intre oricare doua varfuri exista un drum. Pentru grafuri orientate, aceasta notiune este intarita: un graf orientat este tare conex, daca intre oricare doua varfuri i si j exista un drum de la i la j si un drum de la j la i.

Exemplu de graf conex neorientat

Graful este conex, deoarece oricare ar fi varfurile x si y, x ≠ y, exista un lant in G care sa le lege.

Exemplu    de graf conex orientat

Graful este conex, deoarece oricare ar fi varfurile x si y, x ≠ y, exista un lant in G care sa le lege.

Exemplu de graf tare conex

Graful este tare conex, deoarece, oricare ar fi varfurile x si y, exista un drum in G de la x la y si unul de la y la x.

In cazul unui graf neconex, se pune problema determinarii componentelor sale conexe. O componenta conexa este un subgraf conex maximal, adica un subgraf conex in care nici un varf din subgraf nu este unit cu unul din afara printr-o muchie a grafului initial. Impartirea unui graf G = (V,  M) in componentele sale conexe determina o partitie a lui V si una a lui M.

Varfurilor unui graf li se pot atasa informatii numite uneori valori, iar muchiilor li se pot atasa informatii numite uneori lungimi sau costuri.



Parcurgerea in latime a acestui graf se poate face dupa unul din programele:

Programul 1 (abordare nerecursiva)

#include<conio.h>

#include<iostream.h>

#include<stdio.h>

int a[20][20];

int coada[20], viz[20];

int i, n, el, j, p, u, pl, m, x, y;

main()

for(i=1;i<=n;i++) //secventa care precizeaza ca

viz[i]=0; //nodurile sunt nevizitate

cout<<'dati nodul de plecare: '; cin>>pl;

viz[pl]=1;

coada[1]=pl;

p=1;

u=1;

while(p<=u)

p=p+1;

}

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

cout<<coada[i]<<' ';

Programul 2 (abordare recursiva)

Utilizam o functie pe care am numit-o parc_latime si care contine un parametru formal, i, care reprezinta pozitia curenta la care s-a ajuns in coada. Algoritmul este urmatorul: se parcurg nodurile grafului, cu j; daca j este adiacent cu nodul curent din coada si j este nevizitat se adauga la coada si se marcheaza ca fiind vizitat; daca mai sunt elemente in coada se trece la urmatorul si se reapeleaza functia.

#include<conio.h>

#include<iostream.h>

#include<stdio.h>

int a[20][20];

int coada[20], viz[20];

int i, n, j, u, pl, m, x, y;

void parc_latime(int i)

if(i<=u) parc_latime(i+1);}

main()

for(i=1;i<=n;i++) //secventa care precizeaza

viz[i]=0; //ca nodurile sunt nevizit

cout<<'dati nodul de plecare: '; cin>>pl;

viz[pl]=1;

coada[1]=pl;

u=1;

parc_latime(1);

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

cout<<coada[i]<<' ';

getche();

Parcurgerea in adancime a acestui graf se poate face dupa programul:

#include<conio.h>

#include<iostream.h>

#include<stdio.h>

int a[20][20];

int viz[20];

int i, n, j, pl, m, x, y;

void parc_adancime(int pl)

main()

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

viz[i]=0;

cout<<'dati nodul de plecare: '; cin>>pl;

parc_adancime(pl);






Politica de confidentialitate



DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 914
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2022 . All rights reserved

Distribuie URL

Adauga cod HTML in site