Grafuri neorientate
Se numește graf neorientat o pereche ordonată de mulțimi G=(V, M)
- V este o mulțime finită și nevidă de elemente numite noduri sau vârfurile grafului;
- M este o mulțime finită de submulțimi cu 2 elemente din V, numite muchii (perechile de noduri din mulțimea M sunt neordonate)
Perechea neordonată formată din vârfurile x și y se notează (x,y); vârfurile x și y se numesc extremitățile muchiei (x,y).
Un vecin al unui vârf x este orice vârf y, cu proprietatea că există muchia (x,y).
Adiacență
Dacă există o muchie între extremitățile x și y, atunci nodurile x și y sunt adiacente.
Incidență
Două muchii sunt incidente dacă au o extremitate comună. Un vârf este incident cu o muchie dacă vârful este extremitate a acelei muchii.
Exemplu (Figura 1):
G=(V,M)
|V|=7
M={(1,2), (1,4), (1,7), (2,3), (3,6), (3,7), (6,7), (6,1)}
Muchia (3,6) este incidentă la nodurile 3 și 6.
Nodurile 3 și 6 se numesc noduri adiacente.
Vârful 3 este incident cu muchia (3,6).
Gradul unui nod
Se numește grad al unui nod din graf numărul de muchii incidente cu vârful respectiv. Gradul vârfului x de notează cu d(x).
De exemplu, pentru graful neorientat ilustrat în figura 1:
d(1)=4, d(2)=2, d(3)=3, d(4)=1, d(5)=0, d(6)=3, d(7)=3
Se numește nod izolat, nodul care are gradul 0.
Se numește nod terminal, nodul care are gradul 1.
De exemplu, în graful neorientat din figura 1, nodul 5 este izolat, iar nodul 4 este terminal.
Observație:
Suma gradelor vârfurilor unui graf neorientat este egală cu dublul numărului de muchii din graf.
Lanț, ciclu
Se numește lanț o succesiune de noduri cu proprietatea că primul nod este diferit de ultimul și între oricare 2 noduri succesive din lanț există muchie.
Primul și ultimul nod se numesc extremitățile lanțului.
- Un lanț este numit elementar dacă el nu conține de mai multe ori același nod.
Ex. din figura 1: [1,7,6,3]
- Un lanț este simplu dacă el nu conține de mai multe ori aceeași muchie, dar poate să treacă de mai multe ori prin același nod.
Ex. din figura 1: [1,7,6,1,2,3]
- Un lanț este numit compus dacă se trece de mai multe ori prin una sau mai multe muchii.
Ex. din figura 1: [1,7,6,1,6,3]
Numărul k-1 se numește lungimea lanțului și este numărul de muchii din care este format.
Se numește ciclu o succesiune de noduri cu proprietatea că ultimul nod este același precum primul și între oricare 2 noduri succesive din lanț există muchie.
Dacă toate vârfurile sunt distincte, mai puțin primul și ultimul, se numește ciclu elementar.
Ex. din figura 1: [1,2,3,7,1]
Lungimea unui ciclu este egală cu numărul de muchii din ciclu, lungimea minimă fiind 3.
Grafuri asociate cu un graf dat
- Un graf parțial al unui graf G se obține eliminând muchii din graful G.
- Un subgraf al unui graf G se obține eliminând vârfuri din graful G, împreună cu toate muchiile incidente cu acestea.
Graf hamiltonian
- Se numește graf hamiltonian, graful care conține un ciclu hamiltonian.
- Se numește ciclu hamiltonian, ciclul elementar care trece prin toate nodurile grafului.
Condiția suficientă ca un graf să fie hamiltonian este ca gradul unui nod să fie mai mare sau egal decât jumătate din numărul de noduri.
Exemplu: Graful ilustrat în figura 2 este hamiltonian.
Cicluri hamiltoniene: [1,2,3,4,5,6,7,1], [1,2,4,3,5,6,7,1]
Graf eulerian
- Se numește graf eulerian, graful care conține un ciclu eulerian.
- Se numește ciclu eulerian, ciclul simplu care străbate toate muchiile grafului.
Condiția necesară ca un graf să fie eulerian este ca gradul fiecărui nod să fie număr par și să nu existe noduri izolate.
Exemplu: Graful ilustrat în figura 3 este eulerian.
Ciclu eulerian: [1,3,4,5,6,3,2,1]
Graf nul
Se numește graf nul, graful a cărui mulțime de muchii este vidă.
Graf regulat
Se numește graf regulat, graful ale cărui vârfuri au același grad.
Graf complet
Un graf neorientat se numește complet dacă oricare două vârfuri din graf sunt adiacente (graful în care există muchia (x,y), oricare ar fi x≠y din mulțimea nodurilor).
Exemplu: Grafurile neorientate complete cu n=3, 4, 5 vârfuri.
Graf conex. Componente conexe
- Se numește graf conex, graful în care există cel puțin un lanț între oricare două noduri ale sale (dacă admite o singură componentă conexă).
- Se numește componentă conexă, subgraful maximal în raport cu proprietatea de conexitate.
- Un graf este biconex dacă este conex şi pentru orice vârf eliminat, subgraful generat își păstrează proprietatea de conexitate.
Exemple:
Graful ilustrat în figura 4 este conex.
Graful ilustrat în figura 5 este format din trei componente conexe:
{1,2,3,5,7,10}
{4,8,9}
{6}
Graf bipartit
Un graf G=(V, M) se numește graf bipartit dacă există două mulțimi nevide A și B astfel încât V=A∪B, A∩B=∅ și orice muchie m a lui G are o extremitate în A, iar cealaltă în B. Mulțimile A și B formează o partiție a lui M.
Moduri de reprezentare a grafurilor neorientate
1. Matricea de adiacență
Matricea de adiacență, asociată grafului G, este o matrice pătratică de ordinul n, cu elementele definite astfel: a[i][j]=1, dacă [i,j] aparține de M sau a[i][j]=0, dacă [i,j] nu aparține de M.
Observații:
- matricea de adiacență este simetrică față de diagonala principală;
- elementele de pe diagonala principală sunt 0;
- gradul unui vârf x este egal cu numărul de elemente 1 de pe linia (sau coloana) x;
- suma tuturor elementelor din matricea de adiacență a unui graf neorientat este egală cu dublul numărului de muchii din graf.
2. Liste de adiacență
Pentru un graf neorientat cu G=(V,M) se va memora numărul de vârfuri n și apoi, pentru fiecare vârf x, lista vârfurilor adiacente cu x, adică a vârfurilor y cu proprietatea că există muchia [x,y].
3. Lista de muchii
Lista de muchii a unui graf neorientat reprezintă o mulțime ce conține toate muchiile din graf.
M = {(1,2), (1,3), (1,4), (3,4), (2,3)}
