Post on 13-Oct-2019
transcript
1
GRAFURI NEORIENTATE ............................................................................................................................................................................................................................. 3
Se numeste graf partial ............................................................................................................................................................................................................................... 4
Se numeste subgraf .................................................................................................................................................................................................................................... 4
Reprezentarea grafurilor neorientate ........................................................................................................................................................................................................ 7
matricea de adiacenta .................................................................................................................................................................................................................... 7
listele vecinilor ................................................................................................................................................................................................................................ 7
vectorul muchiilor ........................................................................................................................................................................................................................... 7
Moduri de memorare ale unui graf ............................................................................................................................................................................................................ 7
Proprietatile matricei : ................................................................................................................................................................................................................................ 9
Vectorul muchiilor. ..................................................................................................................................................................................................................................... 9
Parcurgerea grafurilor ..............................................................................................................................................................................................................................12
Algoritmul de parcurgere in latime BF (Breadth First); ............................................................................................................................................................................14
Algoritmul de parcurgere in adancime DF (Depth First); .....................................................................................................................................................................15
Aplicatie ....................................................................................................................................................................................................................................................16
In C++ vom afisa matricea de adiacenta: ..................................................................................................................................................................................................17
Calcularea gradelor nodurilor ...................................................................................................................................................................................................................18
Parcurgerea in latime: ..............................................................................................................................................................................................................................19
CONEXITATE ..............................................................................................................................................................................................................................................22
Definiţie -lant ............................................................................................................................................................................................................................................23
Sa se afiseze un lant de lungime minima intre nodurile a si b: ................................................................................................................................................................26
Se numeşte graf hamiltonian ....................................................................................................................................................................................................................29
Grafuri hamiltoniene si euleriene .............................................................................................................................................................................................................31
2
3
Notiuni de bazã : Definitii:grad, subgraf :
http://portal.edu.ro/bac2012/materiale/TIC_011/M1/index.html
GRAFURI NEORIENTATE
Definiţie: Se numeşte graf neorientat o pereche ordonată de mulţimi (X,U), X
fiind o mulţime de elemente numite noduri sau vâfuri, iar U o mulţime din X
numite muchii.
Pentru graful de mai sus avem:
X={1, 2, 3, 4, 5, 6, 7, 8} :noduri
U={(1,2), (1,4), (1,5), (2,3), (2,5), (3,4), (6,7)} ;muchii
Dacă u1şi u2 sunt două muchii ce au o extremitate comună ele se vor numi
adiacente.
4
Definiţie : Un graf parţial al grafului G=(X,U) este un graf G1(X,V) astfel încât V U,
adică G1 are aceeaşi mulţime de vârfuri ca G, iar muţimea de muchii V este chiar U sau o
submulţime a acesteia.
Se numeste graf partial daca se pastreaza nodurile si se suprima niste muchii
Ex. Mai jos avem un graf parţial al grafului de mai sus (Fig. 1)
Cu alte cuvinte, un graf parţial al unui graf se obţine păstrând aceeaşi mulţime de
noduri şi eliminând o parte din muchii.
Definiţie : Un subgraf al unui graf G=(X,U) este un graf H(Y,V) astfel încât Y X
iar V conţine toate muchiile din U care au ambele extremităţi în Y. Vom spune că
subgraful H este indus sau generat de mulţimea de vârfuri Y.
Se numeste subgraf daca se elimina niste noduri
Ex. Mai jos avem un subgraf al grafului din Fig. 1 obţinut prin eliminarea nodului 3
5
Definiţie : Gradul unui vârf x este numărul muchiilor incidente cu x.
Gradul vârfului x se notează d(x).
Ex. în Fig. 1 : d(1)=3 ; d(4)=2 ; d(8)=0 ; d(6)=1 ;
Un vârf care are gradul 0 se numeşte vârf izolat.
Un vârf care are gradul 1 se numeşte vârf terminal.
Propoziţia 1 : Dacă un graf G(X,U) are m muchii şi n vârfuri, iar X={x1,x2,...,xn}
atunci suma gradelor fiecarui nod este dublul muchiilor :
d(x1)+d(x2)+...+d(xn)=2*m ;
Corolar : În orice graf G există un număr par de vârfuri cu grad impar.
6
Definiţie : Se numeşte graf complet cu n vârfuri un
graf care are proprietatea că orice două noduri diferite sunt
adiacente.
4 varfuri are : 4*(4-1)/2=6 muchii
Propoziţia 2 : Un graf complet Kn are n(n-1)/2 muchii.
Definiţie: Un graf G=(X,U) se numeşte bipartit dacă
există două mulţimi nevide A, B astfel încât X=A U B, A∩B
7
= şi orice muchie a lui G are o extremitate în A iar cealaltă în B.
Unele noduri din A pot fi adiacente cu nodurile din B
Definiţie: Un graf bipartit complet dacă pentru orice x din
A şi y din B, există muchia (x,y).
toate noduriledin A sunt adiacente cu nodurile din B
Reprezentarea grafurilor neorientate
Cele mai cunoscute forme de reprezentare ale unui astfel de graf sunt:
matricea de adiacenta,
listele vecinilor si
vectorul muchiilor.
Moduri de memorare ale unui graf
8
1. Lista vecinilor : Putem memora graful dând pentru fiecare nod mulţimea nodurilor cu
care formează arce în care el este pe prima poziţie. x1 { x2, x3,x5}
x2 { x1, x3 }
x3 {x1, x2}
x4 { 0}
x5 { x1 }
x6 { x10, x7}
x7 { 6,8}
x8 { 9,7 }
x9 { x10, x8}
x10 { x6, x9}
2. Un graf poate fi memorat printr-o matrice pătratică booleană, de dimensiune egală cu
numărul de noduri, în care o poziţie aij va fi 1 dacă există muchia (xi,xj) şi 0 în caz
contrar, numită matricea adiacenţelor directe.
x1 x2 x3 x4 x5 x6
x1 0 1 1 1 1 0
x2 1 0 1 1 1 1
x3 1 1 0 0 0 0
x4 1 1 0 0 1 1
x5 1 1 0 1 0 0
x6 0 0 0 1 0 0
9
Proprietatile matricei : 1. Este o matrice simetrica
2. Elementele de pe diagonala principale sunt egale cu 0
3. Suma elementelor pe lini i sau coloana j este egala cu gradul nodului i
4. Daca toate elementele pe linia/ coloana i sunt egale cu 0 atunci nodul este izolat
5. Daca toate elementele sunt egale cu 1 mai putin cele de pe DP atunci inseamna ca
graful este complet
Vectorul muchiilor.
Fiecare muchie a grafului poate fi privita ca o inregistrare cu doua componente: cele doua
varfuri care constitue extremitatile muchiei. Notand aceste extremitati cu nod1 si nod2, putem
defini tipul de date tmuchie, astfel:
int tmuchie
{ int nod1, nod2;
};
Graful in ansamblul sau, este o multime de muchii, adica o multime de elemente de tipul
tmuchie.In consecinta definim graful ca un “vector de muchii”, adica un vector cu elementele
de tipul muchie:
tmuchie vector[25];
10
Exemplul 2: Reprezentăm graful de mai sus prin cele două metode :
1.
0000000
0010000
0100000
0000110
0001010
0001101
0000010
A 2.
7
56
65
3,24
4,23
4,3,12
21
_
.
vecinilorlistanodul
Def. Fie graful G = (X,U). Un graf parţial se obţine din G păstrând toate vârfurile
şi suprimând nişte muchii.
Def. Fie graful G = (X,U). Un subgraf al lui G se obţine din G eliminând nişte vârfuri şi
păstrând doar acele muchii care au ambele extremităţi în mulţimea vârfurilor rămase.
Ex :
-graful initial
11
a. Eliminam muchiile care trec prin nodul 4 → graf partial
Am eliminat muchiile u3 şi u4, păstrând toate vârfurile.
b. Eliminăm vârfurile 5,6,7 şi muchiile corespunzătoare(u5) → subgraf
12
Parcurgerea grafurilor
Ne amintim:
Ce este un graf? Se numeşte graf neorientat o pereche ordonată de mulţimi (X,U), X fiind o mulţime
de elemente numite noduri sau vâfuri, iar U o mulţime de perechi neordonate
numite muchii.
Ce este un graf
partial?
Se numeste graf partial daca se pastreaza nodurile si se suprima niste muchii
Ce este un subgraf? Se numeste subgraf daca se elimina niste noduri dintr-un graf
Cum aflam gradul
unui nod?
Gradul unui nod x este egal cu numărul muchiilor adiacente cu x.
Construim matricea de adiacenta si suma de ‘1’ de pe fiecare linie este egal cu
gradul nodului i de pe linia i
Care sunt
proprietatile unei
matrice de
adiacenta?
(reprezentarea
grafului in
memorie)
Este o matrice simetrica
Elementele de pe diagonala principale sunt egale cu 0
Suma elementelor pe lini i sau coloana j este egala cu gradul nodului i
Daca toate elementele pe linia/ coloana i sunt egale cu 0 atunci nodul este izolat
Dac toate elementele sunt egale cu 1 mai putin cele de pe DP atunci inseamna ca
graful este complet
13
http://portal.edu.ro/bac2012/materiale/TIC_011/M8/index.html
1) parcurgere in latime BF (Breadth First):
6,3,5,1,4,2
2) parcurgere in adancime DF (Depth First):
6,3, 1,2,4,5
14
Algoritmul de parcurgere in latime BF (Breadth First);
Metoda consta in:
1) se viziteaza varful de pornire,
2) se viziteaza toate varfurile adiacente in ordine crescatoare,
3) in ordine crescatoare se alege primul varf adiacent cu varful de pornire si se
viziteaza toate varfurile adiacente cat timp este posibil.
Exemplul 1:
Presupunem ca varful de pornire este 1,atunci parcurgerea BF este:1,2,5,6,3,4,7.
Pentu 3 varf de pornire:3,2,4,1,5,6,7.
Pentru implementare vom folosi :
1) un vector care are proprietatile unei cozi, fie
c=(c1,c2,…,ck). Capetele de intoducere si
extragere vor fi identificate prin pozitiile p si
respectiv u.
2) Mai avem nevoie de un vector viz cu n elemente, in care elementele viz[k]
(k=1,2,….,n) au semnificatia: viz*i+=0, daca varful i nu a fost vizitat sau viz[i]=1daca a
fost vizitat. Mai intai initializam tot vectorul viz cu 0.
15
Initial in coada se gaseste varful de pornire: p=1, u=1, c[p]:=x, viz[x]:=1.
Cat timp mai sunt elemente in coada(“while p<=u”):
Extragem din coada varful aflat in capatul de extragere u, si-l memoram intr-o variabila
z{z:=c[p]};
Pe linia z in a cautam vecinii lui z si ii introducem in coada.
Algoritmul de parcurgere in adancime DF (Depth First);
Metoda consta in: 1) alegem varful de pornire, 2) se alege primul vecin al sau nevizitat inca, 3) pentru acest vecin cautam primul vecin al sau
nevizitat si asa in continuare. 4) In cazul in care un varf nu mai are vecini
nevizitati atunci ne intoarcem la nodul anterior, iar pentru acel nod cautam urmatorul vecin nevizitat al sau.
Pentru graful de mai sus parcurgerea in adancime plecand de la varful 1 este: 1,2,3,4,6,7,5. Pentru a implementa vom folosi o stiva si metoda backtracking.
16
Aplicatie
Construirea matricei de adiacenta: Se considera urmatorul graf:
17
In C++ vom afisa matricea de adiacenta:
else cout<<a[i][j]<<" "; cout<<endl;}}
18
Calcularea gradelor nodurilor
cout<<" nodurile la dreapta muchiei: "<<i; cin>>y; a[x][y]=1; a[y][x]=1; }
19
for(i=1;i<=n;i++) //afisare grad nod cout<<"varful "<<i<<" are gradul "<<grad(i)<<endl; }
Parcurgerea in latime:
20
21
Metoda consta in:
-alegem varful de pornire, pentru acesta se alege primul vecin al sau nevizitat inca,pentru acest
vecin cautam primul vecin al sau nevizitat si asa in continuare. In cazul in care un varf nu mai
are vecini nevizitati atunci ne intoarcem la nodul anterior, iar pentru acel nod cautam urmatorul
vecin nevizitat al sau.
22
Pentru graful de mai sus parcurgerea in adancime plecand de la varful 1 este: 1,2,3,4,5,6,7.
Pentru a implementa vom folosi o stiva si metoda backtracking.
CONEXITATE
Prin parcurgerea in latime acelui graf am subliniat o
proprietate importanta a grafului:faptul ca in urma
parcurgerii au fost vizitate toate varfurile.
Luand oricare doua varfuri,putem gasi cel putin un traseu care porneste dintr-un varf si
ajunge in celalalt.
Luand oricare doua varfuri, ele pot fi legate printr-un lant. Dar nu toate grafurile sunt conexe. In schimb putem desprinde din el “portiuni” care, fiecare
luata separat, este un graf conex.
Exemplu:
Se numeste componenta conexa a grafului G=(X,U), un subgraf G1=(X1,U1) a lui G,
conex, cu proprietatea ca nu exista nici un lant care sa lege un varf din X1 cu un varf din
X-X1.
Fie G=(X,U) un graf neorientat, X={x1,x2,..,xn}.
23
Definiţie -lant: Se numeşte lanţ în G succesiunea de vârfuri L={xi1,xi2,...,xik} cu
proprietate că orice două noduri consecutive din lant sunt adiacente, adică (xi1,xi2),
(xi2,xi3), ..., (xik-1,xik) U
Dacă vârfurile xi1, xi2, ..., xik sunt diferite două câte două atunci lanţul se
numeşte elementar. În caz contrar, lanţul este neelementar.
ex. L1=[1, 2, 4] – lanţ elementar
L2=[1, 2, 3, 1, 2, 4] – lanţ neelementar
Definiţie : Se numeşte ciclu în G un lanţ L pentru care xi1=xik şi toate muchiile
adiacente (xi1, xi2), (xi2, xi3), ..., (xik-1, xik) sunt diferite.
Ex. C=[1, 2, 3, 1] este un ciclu
Definiţie : Se numeşte ciclu elementar un ciclu care are proprietate că oricare
două vârfuri ale sale, cu excepţia primului şi ultimului, sunt diferite două câte două.
Ex. C1=[1, 2, 3, 1] este ciclu elementar.
C2=[3, 1, 2, 4, 8, 2, 3] este un ciclu neelementar.
Definiţie : Un graf G se numeşte conex dacă pentru orice două vârfuri x şi y
diferite ale sale există un lanţ ce le leagă.
24
Definiţie : Se numeşte componentă conexă a grafului G=(X,U) un subgraf
C=(X1,U1), conex, al lui G care are proprietatea că nu există nici un lanţ care să lege un
vârf din X1 cu un vârf din X-X1.
Def. Se numeşte ciclu într-un graf, un lanţ L = (z1,z2,...,zk) cu proprietatea că z1 = zk şi
muchiile [z1,z2], [z2,z3+,…, *zk-1,zk+ sunt distincte două câte două.
Def. Dacă într-un ciclu, toate vârfurile cu excepţia primului şi a ultimului sunt distincte
două câte două, atunci ciclu se numeşte elementar. In caz contrar, el este ne-elementar.
L1 = (1,2,3,4) - lanţ elementar
L2 = (1,2,4,3,2,3,4) - lanţ ne-elementar
L3 = (2,4,3,2,1) – lanţ ne-elementar
L4 = (6,5,1,2,3,4) -lanţ elementar
25
C1 = (2,3,4,2) - ciclu elementar
C2 = (1,2,4,3,1) - ciclu elementar
C3 = (5,2,4,3,1,5) - ciclu elementar
C4 = (1,2,3,4,2,5,1) - ciclu ne-elementar
C5 = (5,2,3,4,2,1,5) - ciclu ne-elementar
Obs. In cadrul unui lanţ, muchiile se pot repeta, dar în cadrul unui ciclu ele trebuie să fie
distincte.
Def. Un graf G este conex dacă oricare ar fi două vârfuri ale sale, există un lanţ care le
leagă.
Obs. Intr-un graf conex, luând oricare două vârfuri , putem găsi cel putin un traseu(lanţ)
care porneşte dintr-un vârf şi ajunge în celălalt.
26
Def. Se numeşte componentă conexă a grafului G =(X,U), un subgraf G1=(X1,U1) a lui
G,conex, cu proprietatea că nu există nici un lanţ care să lege un vârf din X1 cu un vârf din
X-X1.
Ex.
In acest exemplu exista 3 componente conexe
- G1 =(X1,U1), cu X1=,1,2,3,4- şi U1={u1,u2,u3,u4} - G2 =(X2,U2), cu X2=,5,.6- şi U2={u5} - G3 =(X3,U3), cu X3={7- şi U1= Ø
Sa se afiseze un lant de lungime minima intre nodurile a si b:
Exista un lant de la a la b daca si numai daca o percurgere DF sau BF porneste de la a si ajunge sa viziteze nodul b.
27
28
29
Def. Se numeşte ciclu hamiltonian într-un graf, un ciclu elementar care conţine toate
vârfurile grafului.
Se numeşte graf hamiltonian un graf care conţine un ciclu hamiltonian.
Ex
Graful din acest exemplu este hamiltonian, deoarece ciclu C =[2,5,1,3,4,2] este
elementar (pleacă din vârful 2 şi se întoarce tot în 2, iar muchiile *2,5+, *5,1+, *1,3+, *3,4+,
*4,2+ sunt distincte două câte două) şi în plus conţine toate vârfurile.
Def. Se numeşte lanţ hamiltonian într-un graf, un lanţ elementar care conţine toate
vârfurile grafului.
30
Ex L = [2,5,1,3,4]
Th. Dacă într-un graf G=(X,U) cu n 3 vârfuri, gradul fiecărui vârf verifică condiţia 2
)(n
xd ,
atunci graful este hamiltonian.
Def. Se numeşte ciclu eulerian într-un graf un ciclu care conţine toate muchiile
grafului.
Def: Se numeşte graf eulerian un graf care conţine un ciclu eulerian.
Ex.
Pentru acest graf, ciclu C = *2,1,5,2,3,4,2+ este eulerian, deoarece pleacă din 2 şi se
întoarce tot în doi, iar muchiile sale consecutive, adica [2,1], [1,5], [5,2], [2,3], [3,4], [4,2]
sunt distincte două câte două şi reprezintă toate muchiile grafului.
31
Th. Un graf fără vârfuri izolate este eulerian dacă şi numai dacă este conex şi gradele
tuturor vârfurilor sunt numere pare.
Grafuri hamiltoniene si euleriene
Se numeste ciclu hamiltonian intr-un graf, un ciclu elementar
care contine toate varfurile grafului.
Un graf care contine un ciclu hamiltonian se numeste graf
hamiltonian.
Un lant elementar care contine toate varfurile grafului se
numeste lant hamiltonian.
Un graf hamiltonian are cel putin trei varfuri.
Graful complet cu n varfuri este un graf hamiltonian.
Teorema:
32
Fie G=(X,U), cu n>=3 varfuri, daca oricare ar fi x un nod al
grafului si d(x)>=n/2, atunci graful este hamiltonian.
Se numeste ciclu eulerian intr-un graf, un ciclu care contine
toate muchiile grafului.
Un graf care contine un ciclu eulerian se numeste graf
eulerian.
Un lant eulerian este un lant care contine toate muchiile
grafului.
Teorema:
Un graf fara varfuri izolate este eulerian, daca si numai daca este
conex si gradele tuturor varfurilor sunt numere pare