Clase de grafuri

Clase de grafuri

O clasa de grafuri este alcatuita din gafuri cu proprietati particulare.

Definitie: Se spune ca digraful G = ( N, A) este simetric daca oricare ar fi (x, y) A implica (y, x) A.

Cu alte cuvinte, digraful G = ( N, A) este simetric daca orice pereche de noduri adiacente este legata prin arce in ambele sensuri.

Definitie: Se spune ca digraful G = ( N, A) este antisimetric daca oricare ar fi (x, y) A implica (y, x)A.

Deci, digraful G = ( N, A) este antisimetric daca orice pereche de noduri adiacente este legata cel mult printr-un singur arc.

Exemplu: Digraful reprezentat in figura 1.5(a) este simetric si digraful reprezentat in figura 1.5(b) este antisimetric.

 

Definitie: Se spune ca digraful G = ( N, A) este pseudosimetric daca ρ (x) = ρ (x) pentru fiecare nod xN.

Orice digraf simetric este si pseudosimetric. Reciproca nu este adevarata.

Exemplu: Digraful reprezentat in figura 1.5(a) este simetric deci este si pseudosimetric, iar cel reprezentat in figura 1.5(b) este antisimetric, dar nu este pseudosimetric. Digraful reprezentat in figura 1.6(a) este pseudosimetric, dar nu este simetric si nici antisimetric, iar cel reprezentat in figura 1.6(b) este antisimetric si pseudosimetric.

Definitie: Se spune ca graful G = ( N, A) este nesimetric daca exista un arc (x, y) A pentru care (y, x)A.

Cu alte cuvinte, digraful G = ( N, A) este nesimetric daca nu este simetric. Orice graf antisimetric este nesimetric. Reciproca nu este adevarata. Orice graf pseudosimetric care nu este simetric este nesimetric. Reciproca nu este adevarata.

Definitie: Se spune ca digraful G = ( N, A) este complet daca oricare ar fi (x, y) A implica (y, x) A.

Un graf simplu neorientat G = ( N, A) cu n noduri care este complet se noteaza cu Kn si are n(n-1)/2 muchii.

Exemplu: Digraful din figura 1.5(b) este antisimetric deci este nesimetric si digrafurile reprezentate in figura 1.6 sunt pseudosimetrice care nu sunt simetrice, deci sunt nesimetrice. Digraful din figura 1.7(a) este nesimetric, dar nu este nici antisimetric si nici pseudosimetric.

Digraful reprezentat in figura b) este complet. Graful K este reprezentat in figura b).

Definitie: Se spune ca graful G = (N, A) este graf turneu daca este antisimetric si complet.

Denumirea de graf turneu se justifica prin faptul ca un astfel de graf poate reprezenta un turneu sportive in care fiecare jucator (echipa) joaca cate un meci cu toti (toate) ceilalti (celelalte) jucatori (echipe).

Definitie: Se spune ca digraful G = ( N, A) este tranzitiv daca oricare ar fi (x, y) A si (y, z) A implica (x, z) A.

Exemplu: Digraful reprezentat in figura 1.5(b) este un graf turneu si de asemenea este tranzitiv.

Definitie: Se spune ca digraful G = ( N, A) este o clica daca este simetric si complet.

Denumirea de clica se justifica prin faptul ca un digraf simetric si complet poate reprezenta o coalitie sociologica, politica etc. Notiunea de clica are sens si pentru grafuri neorientate, astfel graful Kn este o clica.

Definitie: Se spune ca digraful G = ( N, A) este bipartit daca multimea nodurilor N admite o partitie in doua submultimi N si N (N , N , N N , N N =N ), astfel incat orice arc (x, y) A are una dintre exremitati in N , iar cealalta extremitate in N

Un digraf bipartit se noteaza G = (N , N , A) si se caracterizeaza prin inexistanta ciclurilor care contin un numar impar de arce. Un graf neorientat bipartit si complet G = (N , N , A) cu | N | = n si | N | = n se noteaza Kn n

Exemplu: Digraful reprezentat in figura 1.8(a) este o clica. In figura b) este reprezentat graful K

Definitie: Se spune ca digraful G = ( N, A) este planar daca avem posibilitatea sa-l reprezentam pe un plan astfel incat oricare doua arce sa se intalneasca eventual numai in extremitatile lor.

Analog se defineste un graf simplu neorientat planar. Arcele (muchiile) unui graf planar G = ( N, A) determina contururi care marginesc regiuni numite fete. Exista o singura regiune din plan fara contur numita fata nemarginita.

Exemplu: Digraful reprezentat in figura 1.5(b) este planar, deoarece poate fi reprezentat ca in figura 1.9. Fetele 1, 2, 3 sunt fetele marginite, iar fata 4 este fata nemarginita. Exemple de graufuri neplanare minimale sunt K5 si K

O alta clasa de grafuri este alcatuita din grafuri associate ale unui graf dat.

Definitie: Se spune ca digraful = ( ) este complementul digrafului G = ( N, A) daca = N si

Analog se defineste complementarul unui graf simplu neorientat. Operatia de complementare este involutiva, adica complementarul complementarului este graful unitial.

Exemplu: Digraful reprezentat in figura 1.10(b) este complementarul digrafului reprezentat in figura 1.10(a).

Definitie: Se spune ca digraful G ¹ = ( N ¹, A ¹) este inversul digrafului G = ( N, A) daca N ¹ = N si A ¹ se obtine din A prin inversarea sensului arcelor.

Operatia de inversare este involutiva, adica inversul inversului este graful initial ( (G ¹ ¹ = G ). Graful autoreciproc (G ¹ = G) este simetric.

Exemplu: Digraful reprezentat in figura 1.11(b) este inversul digrafului reprezentat in figura 1.11(a).