Grafuri Neorientate
Un graf este o mulțime de obiecte, numite noduri, care sunt legate între ele printr-o mulțime de muchii, cărora li see pot atribui și direcții. Nodurile se notează, tradițional, cu numere de la 1 la n, unde n este numărul total de noduri.
Un graf este neorientat, dacă este graf, iar muchiile sale nu au o direcție.
Gradele unui varf
Gradul unui vărf este dat de numărul de muchii care se intersectează cu acesta.
- un vărf cu gradul
0se numeșteizolat - un vârf cu gradul
1se numeșteterminal
Reprezentare
Matricea de adiacență
Matricea de adiacență stabilește că între nodul i (rândul) și nodul j (coloana) există o muchie.
- matricea de adiacență a unui graf neorientat este întotdeauna simetrică față de diagonala principală
- elementele de pe diagonala principală sunt
0
Lista de adiacență
Voi menționa lista de adiacență doar ca un concept important, deoarece aceasta nu intră în materia de bac. Aceasta presupune memorarea tuturor vecinilor unui nod, pentru fiecare nod în parte. Dacă am avea un șir de n vectori din STL, pentru fiecare i de la 1 la n, vom avea un vector de noduri, care vor reprezenta vecinii nodului i. Deci, de la i la j există o muchie.
Conexitate
Lanț
Un lanț este o succesiune de vârfuri L = [x1, x2, ..., xk] cu propritatea că oricare 2 vârfuri consecutive sunt adiacente.
- vârfurile
x1șixkse numesc extremitățile lanțului - lungimea unui lanț este dată de numărul de muchii din care este format
Se numește lanț elementar, lanțul care conține numai vârfuri distince două câte două.
Se numește lanț simplu, lanțul care conține numai muchii distincte.
Ciclu
Un ciclu este un lanț simplu în care primul vârf este identic cu ultimul
- lungimea unui ciclu este dată de numărul de muchii din care este format
- lungimea minimă a unui ciclu este
3
Se numește ciclu elementar, ciclul care are toate vârfurile distince, mai puțin primul și ultimul.
Se numește ciclu hamiltonian, un ciclu elementar care conține toate vârfurile grafului, o singură dată.
Se numește ciclu eulerian, un ciclu care conține toate muchiile grafului, o singură dată.
Un graf neorientat care nu conține niciun ciclu se numește aciclic.
Graf conex
Un graf conex este un graf care pentru oricare 2 vârfuri ale sale există un lanț care să le lege. Cu alte cuvinte, un graf este conex dacă toate nodurile sale sunt conectate.
Componente conexe
Se numește componentă conexă a unui graf G = (X, U), un subgraf conex H = (Y, V), care are proprietatea că nu există niciun lanț în G care să lege un vârf din Y cu un vârf din X - Y.
- un graf este conex dacă admite o singură componentă conexă
- un graf poate admite de la 1 la n componente conexe
Tipuri de grafuri neorientate
Graf nul
Un graf este graf nul, dacă nu are nicio muchie.
Graf complet
Un graf este graf complet, dacă oricare două vârfuri distince ale sale sunt adiacente. Cu alte cuvinte dacă are numărul maxim de muchii.
- numărul de muchii ale unui graf complet cu
nnoduri estem = n * (n - 1) / 2
Graf parțial
Un graf este graf parțial al grafului G, dacă se poate obține din graful G prin eliminarea unor muchii.
Subgraf
Un graf este subgraf al grafului G, dacă se poate obține din graful G prin eliminarea unor noduri și muchiilor adiacente acestora.
Graf complementar
Un graf este complementar al grafului G cu n noduri, dacă se poate obține dintr-un graf complet cu n noduri, căruia i s-au eliminat muchiile din G.
Graf hamiltonian
Un graf hamiltonian este un graf care conține un ciclu hamiltonian.
- un graf cu
nnoduri este hamiltonian, dacăn ≥ 3, iar gradul oricărui vârf verifică inegalitatead(x) ≥ n / 2
Graf eulerian
Un graf eulerian este un graf care conține un ciclu eulerian.
- un graf este eulerian dacă și numai dacă este conex și gradele tuturor vârfurilor sale sunt pare