Informatica

GRAFURILE ORIENTATE

Definitie

Se numește graf orientat notat cu G o pereche ordonată de mulțimi {X,U} G= {X,U} unde X este mulțimea vârfurilor si U este multimea arcelor.

X={1,2,3,4,5}

U={(1,2),(1,3),(2,5),(4,2),(4,5)}

TERMINOLOGIE
Elementele mutimii U se numesc arce,iar multimea U se mai numeste si multimea arcelor.
Varfurile adiacente sunt orice pereche de varfuri care formeaza un arc.
Pentru arcul (x,y) spunem ca x este extremitate initiala iar y este extremitate finala.
Se numesc arce incidente doua arce care au o extremitate comuna.Se numeste succesor al varfului X orice varf in care ajunge un arc care pleaca din varful X.
Se numeste predecesor al varfului X orice varf in care intra un arc care pleaca din varful X.
Nod sursa al grafului este nodul care are multimea succesorilor formata din toate celelalte noduri mai putin el iar multimea predecesorilor sai este vida. Nod destinatie al grafului este nodul care are multimea predecesorilor formata din toate celelalte noduri mai putin el iar multimea succesorilor sai este vida.Se numeste nod terminal un nod care are suma gradelor egala cu 1.
Se numeste nod izolat un nod care are suma gradelor egala cu 0.

GRADUL UNUI NOD

-grad extern este egal cu numarul arcelor care au extremitate initiala( numarul arcelor care ies din X)
-grad intern este egal cu numarul arcelor care au extremitate finala( numarul arcelor care intra in X)

Se noteaza:

Un varf izolat este un varf care are gradul intern egal cu extern ,egal cu zero.

- Multimea (gama plus) si (gama minus)

-Multimea pentru varful x este egala cu multimea varfurilor care reprezinta succesorii varfului x.

- Multimea reprezinta multimea varfurilor care sunt predecesoare varfului x.

-Multimea (omega plus) si (omega minus)

-Multimea reprezinta multimea muchilor care au ca extremitate initiala varful x.

Multimea reprezinta multimea muchilor care au ca extremitate finala varful x

Un nod terminal este un nod care are suma gradelor externe si interne egala cu 1.

Teoreme

1.Numarul total de grafuri orientate care se pot forma cu n noduri este .

2.Intr-un graf orientat cu n varfuri ,suma gradelor interne ale tuturor nodurilor este egala cu suma gradelor externe ale tuturor nodurilor si cu numarul de arce.

Suma gradelor interne ale tuturor varfurilor este egala cu suma gradelor externe si este egala cu numarul de arc

Lant,drum in grafurile orientate

Def :Numim lant intr-un graf orientat o succesiune de varfuri cu proprietatea ca oricare 2 varfuri consecutive sunt adiacente.

5,1,2,4,3-lant elementar

3,4,2,5-lant elementar

3,4,2,5,1,2-lant neelementar

1,2,3-nu este lant

Numim drum o succesiune de noduri cu proprietatea ca intre oricare 2 varfuri succesive exista un arc.

5,1,2,4,3-nu este drum

3,4,2,5-nu este drum (deoarece intre 3 si 4 nu avem arc,doar intre 4 si 3)

2,1,4,3-drum elementar

Graf Conex

Un graf G se numeste conex daca intre oricare 2 varfuri diferite exista un lant care sa le uneasca.

Componenta conexa a unui graf orientat

Daca avem un graf G care nu este conex,se numeste componenta conexa a grafului G un subgraf al sau care este conex.

Obs :Un graf conex are o singura componenta conexa.

Graful are 2 componente conexe.

Graf tare conex

Def :Un graf orientat G se numeste tare conex daca indeplineste urmatoarea proprietate :pentru oricare 2 varfuri x,y(x !=y) exista drum de la varful x la varful y si un alt drum de la varful y la varful x.

Daca un graf orientat G nu este tare conex se numeste componenta tare conexa a grafului un subgraf tare conex al sau.

GT1                                             GT2

GT1-este un graf conex

Componenta tare conexa :{1,3,7},{4,5},{2},{6}

GT2-este un graf tare conex

GT4

GT4-graful nu este conex

Componentele conexe sunt formate din submultimile ;{1,2},{3,4,5,8},{6,7,9}

Teoreme

1.Daca un graf nu contine un lant intre 2 noduri x si y atunci contine un lant elementar intre nodurile x si y.

2.Daca un graf contine un drum intre 2 noduri x si y atunci contine un drum elementar intre nodurile x si y.

3.Daca un graf contine un ciclu atunci contine si un ciclu elementar.

4.Daca un graf contine un circuit atunci contine si un circuit elementar.

Teoreme :

1.Numarul minim de muchii necesare ca pentru un graf neorientat sa fie conex este n-1.

2.Un graf conex cu n noduri si n-1 muchii este aciclic si maximal cu aceasta proprietate.

3.Daca un graf neorientat conex are n noduri si m muchii ,numarul de muchii care trebuie eliminate pentru a obtine un graf partial conex aciclic este m-n+1.

4.Daca un graf are n noduri,m muchii si p componente conexe, numarul de muchii care trebuie eliminate pentru a obtine un graf partial aciclic(arbore) este egal cu m-n+p.

5.Pentru a obtine dintr-un graf neorientat conex 2 componente conexe,numarul minim de muchii care trebuie eliminate este cel mult egal cu gradul minim din graf.

6.Numarul maxim de muchii dintr-un graf neorientat cu n noduri si p componente conexe este (n-p)*(n-p+1)/2.

DEFINITIE. Se numeşte graf ponderat un graf orientat sau nu în care fiecărei muchii i s-a asociat un cost dat, de obicei, o funcţie de cost f: U→R. Exemplu de graf ponderat:

DEFINITIE. Graful orientat G1=(X,U1) se numeşte graful transpus al grafului G dacă G1 se obţine din graful G prin inversarea sensului arcelor sale.

REPREZENTAREA GRAFURILOR ORIENTATE

Matricea de incidenţă

Matricea de incidenţă este o matrice cu n linii şi m coloane. Pe fiecare coloană vom avea o valoare de 1 care corespunde extremităţii iniţiale a unui arc, o valoare de -1 care corespunde extremităţii finale a unui arc, toate celelalte fiind 0.

Lista arcelor

Este formată din m elemente care conţin fiecare, câte o pereche de noduri, x şi y care formează un arc.

Lista vecinilor În lista vecinilor pentru fiecare nod se specifică succesorii.

PARCURGEREA GRAFURILOR ORIENTATE IN ADANCIME

Parcurgerea unui graf in adancime se face prin utilizarea stivei (alocate implicit prin subprograme recursive).

Pentru fiecare varf se parcurge primul dintre vecinii lui neparcursi inca

Dupa vizitarea varfului initial x₁, se exploreaza primul varf adiacent lui, fie acesta x₂ , se trece apoi la primul varf adiacent cu x₂si care nu a fost parcurs inca , s.a.m.d.

Fiecare varf se parcurge cel mult odata

De exemplul pentru garful din figura de mai jos, se va proceda in felul urmator:

se porneste din varful 1, (se poate incepe de la oricare alt varf)

se exploreaza in continuare primul vecin al acestuia acestuia : varful 2,

se obtine 1,2

dupa care din 2 se exploreaza varful adiacent cu acesta si care nu a fost vizitat : 3.

se obtine 1,2,3

In continuare ar trebui sa se parcurga vecinul lui 3 nevizitat : 4

se obtine 1, 2, 3, 4

Pentru varful 4 ar trebui sa se parcurga primul sau vecin neparcurs (varful 1 dar acesta a fost deja parcurs. Nu mai avem ce vizita si se trece la nivelul anterior din stiva, la varful 3 :

1, 2, 3, 4 Se parcurge vecinul sau nevizitat, varful 5 .

Se obtine : 1, 2, 3, 4 , 5.

Varful 3 nu mai are vecini nevizitati si se trece pe nivelul anterior din stiva, varful 2 : 1, 2, 3, 4 , 5. Nici acesta nu mai are vecini nevizitati si se trece pe nivelul anterior la varful 1 : 1, 2, 3, 4 , 5. Cum nici acesta nu mai are vecini nevizitati se incheie algoritmul.

GRAFURILE NEORIENTATE

Definiţie

Se numeşte graf neorientat G=(X,U) o pereche de mulţimi (X,U), unde X este o mulţime finită şi nevidă de elemente numite noduri (vârfuri) iar U o mulţime de perechi, formate cu elemente distincte din mulţimea X numite muchii.

Se numesc noduri adiacente orice pereche de noduri între care există o muchie.

ex:muchia (1,2)

Spunem că un nod este incident cu o muchie daca nodul reprezintă o extremitate pentru aceea muchie.

ex:nodul 1 este incident cu muchia (1,2)

Spunem ca 2 muchii sunt incidente daca au un nod comun .

ex: muchia (1,2), (1,3) au nodul 1 comun

Nodurile vecine unui nod sunt toate noduriile adiacente cu nodul respectiv.

Gradul unui nod X al grafului G este egal cu numarul de muchii incidente cu nodul respectiv şi se noteaza cu d(x).

ex:d(3)=5

Un nod care are gradul 1 se numeşte nod terminal.

ex: d(4)=1

Un nod care are gradul 0 se numeşte vârf izolat.

ex: d(7)=0

REPREZENTAREA GRAFURILOR NEORIENTATE

MATRICEA DE ADIACENTA

DEFINITIE

Fie G=(V,M) un graf neorientat, cu n varfuri si m muchii. Matricea de adiacenta asociata grafului G este o matrice patratica de ordinul n, cu n elemente, definite astfel:

i,j={ 1, daca [i,j] apartine M

0, daca [i,j] nu apartine M

EXEMPLU

REPREZENTARE GRAFICA	MATRICEA A	MATRICE DE ADIACENTA
	a11 a12 a13 a14 a21 a22 a23 a24 A= a31 a32 a33 a34 a41 a42 a43 a44	0 0 1 1 0 0 1 1 1 1 0 0 1 1 0 0

PROPRIETATI

matricea de adiacenta este o mnatrice patratica de ordinul n, si simetrica fata de diagonala principala;
matricea de adiacenta are toate elementele, de pe diagonala principala, egale cu zero;
numarul elementelor egale cu 1 de pe linia i(sau coloana j) este egal cu gradul varfului i;
daca varful i este izolat pe linia i (sau coloana j) nu sunt elemente egale cu 1.

IMPLEMENTAREA MATRICII DE ADIACENTA

#include<iostream.h>

void main()

{
int m,n,x,y,i,j, a[20][20];
cout<<" noduri n="; cin>>n;
cout<<"muchii m="; cin>>m;
for(i=1;i<=m;i++)
{    cout<<"x=";cin>>x;
       cout<<"y=";cin>>y;
       a[x][y]=1; a[y][x]=1;      }
cout<<"matricea de adiacenta este="<<endl;
for (i=1;i<=n;i++)

{

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

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

cout<<endl;}

LISTA DE ADIACENTA

Fie G=(V, M) un graf neorientat cu n vârfuri (V={1,2, ..., n}) si m muchii.
Reprezentarea grafului G prin liste de adiacență constă în:
- precizarea numărului de vârfuri, n;
- pentru fiecare vârf i, se precizează lista i a vecinilor săi, adică lista nodurilor adiacente cu nodul i.

Fie graful din figura urmatoare:

Lista vecinilor nodului 3: 2, 4, 5 (noduri adiacente)

Nodul 6 nu are vecini (este izolat)

Pentru intreg graful vom avea mai multe liste :

Nodul 1 :

Nodul 2 :

Nodul 3 :

Nodul 4 :

Nodul 5 :

Implementarea în limbajul C++, a ideii prezentate mai sus, se realizează conform secvenței de program :

int L[20][20];
int nr_vec[20];
cout<<"n=”; cin>>n;
for (i=1;i<=n;i++)
{cout<<"Dați numărul veciniior nodului "<<i; cin>>nr_vec[i];
for (j=1;j<=nr_vec[i];j++)
cin>>L[i][j];}

GRAFURI SPECIALE

Numim lanţ o succesiune de noduri cu proprietatea că oricare ar fi 2 noduri successive ele sunt adiacente.

Se numeşte ciclu ,un lanţ în care toate muchiile sunt distincte 2 câte 2 şi între primul şi ultimul nod există o muchie.

Se numeşte lungimea unui lanţ ,numărul de muchii din care este format.

Se numeşte lanţ elementar,un lanţ care conţine doar noduri distincte.

Se numeşte lanţ simplu,un lanţ care conţine doar muchii distincte.

Graful G se numeşte nul dacă mulţimea U este vidă (nu are muchii).
Un graf se numeşte complet dacă are proprietatea că oricare 2 noduri ale sale sunt adiacente.
Teoremă: Numărul de muchii ale unui graf complet cu n noduri este
[n(n-1)]/2.
Se numeşte graf parţial al lui G=(X,U) graful Gp=(X,V) unde V este egal sau inclus în U (din graful G eliminăm muchii).
Se numeşte subgraf al lui G=(X,U), Gs=(Y,V) unde Y este egal sau inclus în X şi toate muchiile din mulţimea V aparţin şi mulţimii U,care au ambele extremităţi în mulţimea Y,adică se obţine din graful G prin eliminarea unor noduri şi a tuturor muchilor incidente cu acestea.

Se numeşte graf complementar al lui G,graful Gc care are propritatea că 2 noduri sunt adiacente în graful complementar dacă şi numai dacă nu sunt adiacente în graful G.
Teoremă: Numărul grafurilor parţiale ale unui graf cu m muchii este 2 la puterea m.
Teoremă: Numărul de subgrafuri ale unui graf cu n noduri este 2ⁿ-1.
Conexitate
Definitie:

1) Un graf G se numeşte graf conex dacă are proprietatea că pentru orice pereche de noduri distincte există un lanţ care le leagă.
2) Dacă un graf G nu este conex se numeşte componentă conexă a grafului, un subgraf conex
al său maximal în raport cu această proprietate (conţine numărul maxim de noduri din graful G care au proprietatea că sunt legate de un lanţ).

Teoreme:
1) Numărul minim de muchii necesare pentru ca un graf neorientat să fie conex este: n-1,unde n reprezintă numărul de noduri.
2) Un graf conex cu n noduri şi n-1 muchii este aciclic şi maximal în raport cu această proprietate.
3) Dacă un graf neorientat conex are n noduri şi m muchii, numărul de muchii care trebuie eliminate pentru a obţine un graf parţial conex aciclic este: m-n+1.
4) Dacă un graf are n noduri şi m muchii şi p componente conexe, numărul de muchii care trebuie eliminat pentru a obţine un graf parţial aciclic(arbore) este egal cu: m-n+p.
5) Pentru a obţine dintr-un graf neorientat conex 2 componente conexe numărul minim de muchii care trebuie eliminate este egal cu gradul minim din graf.
6) Numărul maxim de muchii dintr-un graf cu n noduri şi p componente conexe este [(n-p)(n-p+1)]/2.
Grafuri speciale

Un graf G se numeşte graf bipartit dacă există două mulţimi nevide de noduri A si B care au proprietatea: A ∩ B= Ø iar A U B=X şi orice muchie din mulţimea U are o extremitate în mulţimea A şi o altă extremitate în mulţimea B.
Un graf bipartit se numeşte graf bipartit complet dacă pentru oricare nod X care aparţine mulţimii A şi orice nod Y care aparţine mulţimii B există o muchie care le leagă.

Se numeşte lanţ Hamiltonian,lanţul care conţine toate nodurile grafului şi este elementar.
Un graf care conţine un ciclu Hamiltonian se numeşte graf Hamiltonian.
Un ciclu se numeşte eulerian,ciclul elementar ce conţine toate muchiile grafului.
Se numeşte graf eulerian,graful care conţine un ciclu eulerian.

TEOREME

1) Un graf cu mai mult de 2 noduri este Hamiltonian dacă graful fiecărui nod este mai mare sau egal decât n/2.

2) Un graf ce nu conţine vârfuri izolate este eulerian dacă şi numai dacă este conex iar gradele tuturor noduriilor sunt numere pare.
3) Numărul de cicluri hamiltoniene dintr-un graf complet cu n noduri este (n-1)!/2.

PARCURGEREA GRAFURILOR NEORIENTATE

Prin parcurgerea unui graf se întelege "vizitarea" vârfurilor sale într-o anumita ordine, data de un anumit criteriu.

Exista doi algoritmi de parcurgere a grafurilor neorientate:

Ø algoritmul de parcurgere în latime BF;

Ø algoritmul de parcurgere în adîncime DF.

1. Algoritmul de parcurgere în latime BF

Se porneste de la un vârf de start care se viziteaza, apoi se viziteaza toti vecinii lui. Pentru fiecare dintre aceste vârfuri, se viziteaza vecinii lui care nu au fost înca vizitati. Pentru noile vârfuri se procedeaza la fel: se viziteaza vecinii acestora care nu au fost înca vizitati. Procedeul continua pâna când s-au vizitat toate vârfurile.

Figura 9.

Exemplu:

Fie graful G=(X,U) din figura 9. presupunem ca vârful de start este 1.

Pasii parcurgerii	Noduri vizitate
· Vizitam mai întâi vârful de start unu;	1
· Vizitam apoi vecinii lui 1, care sunt 2, 5 si 6	2, 5, 6
· Pentru fiecare dintre acesti vecini ai lui 1, vizitam si vecinii sai nevizitati înca: - vecinii lui 2 sunt 1, 3 si 4, dar nevizitati sunt decât 3 si 4 - vecinii lui 5 sunt 1, 2 si 7, dar nevizitat este numai 7 - vârful 6 nu mai are vecini nevizitati
	3,4
	7

· Am vizitat pâna acum vecinii vârfurilor 1,2,5 si 6. Mai trebuie vizitati vecinii noilor vârfuri vizitate la pasul anterior, si anume vecinii vârfurilor 3,4 si 7. Dar observam ca vârfurile 3,4 si 7 nu mai au vecini nevizitati.deci parcurgerea se încheie.

Ordinea vizitarii în parcurgerea BF este 1, 2, 5, 6, 3, 4, 7.

2. Algoritmul de parcurgere în latime BF

Metoda este urmatoarea: alegem vârful de pornire, pentru acesta se alege primul vecin al sau nevizitat înca, pentru acest vecin cautam primul vecin al sau nevizitat si asa în continuare. În cazul în care un vârf nu mai are vecini nevizitati atunci ne întoarcem la nodul anterior, iar pentru acel nod cautam urmatorul vecin nevizitat al sau.

Pentru graful de mai sus, din fig 9,parcurgerea în adâncime plecând de la vârful 1 este: 1,2,3,4,6,7,5.