Grafuri Orientate
Un graf este orientat, dacă este graf, iar muchiile sale au o orientare.
Gradele unui vârf
Nodurile unui graf orientat au două tipuri de grade, exterior și interior.
- se numește grad exterior numărul arcelor care ies din nod
- se numește grad interior numărul arcelor care intră în nod
Reprezentare
Matricea de adiacență
Matricea de adiacență stabilește că între nodul i (rândul) și nodul j (coloana) există o muchie orientată de la i la j.
- 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 nodurile unite de nodul i, cu direcția de la i la j.
Conexitate
Lanț
Un lanț (drum) este o succesiune de vârfuri L = [x1, x2, ..., xk] cu propritatea că oricare 2 vârfuri i și j, consecutive, sunt adiacente și au o muchie orientată de la i la j.
- vârfurile
x1șixkse numesc extremitățile lanțului - lungimea unui lanț este dată de numărul de arce 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 arce distincte.
Circuit
Un circuit este un lanț simplu în care primul vârf este identic cu ultimul
- lungimea unui circuit este dată de numărul de arce din care este format
- lungimea minimă a unui circuit este
3
Se numește circuit elementar, circuit care are toate vârfurile distince, mai puțin primul și ultimul.
Se numește circuit hamiltonian, un circuit elementar care conține toate vârfurile grafului.
Se numește circuit eulerian, un circuit care conține toate muchiile grafului.
Graf tare conex
Un graf tare conex este un graf care pentru oricare 2 vârfuri distincte ale sale există cel puțin un drum care să le lege. Cu alte cuvinte, putem ajunge din orice nod în orice alt nod.
Componente tare conexe
Se numește componentă tare conexă a unui graf, un subgraf tare conex căruia dacă i-am mai adăuga un nod, n-ar mai fi tare conex.
- un graf este tare conex dacă admite o singură componentă tare conexă
Tipuri de grafuri orientate
Graf parțial
Un graf este graf parțial al grafului G, dacă se poate obține din graful G prin eliminarea unor arce.
Subgraf
Un graf este subgraf al grafului G, dacă se poate obține din graful G prin eliminarea unor noduri și arcelor adiacente acestora.
Graf complet
Un graf este graf complet, dacă oricare două vârfuri distince ale sale sunt adiacente.
- numărul de grafuri orientate cu
nnoduri este3 ^ (n * (n - 1) / 2))
Graf turneu
Un graf este graf turneu, dacă între oricare două vârfuri distincte, i și j, există un singur arc, (i, j) sau (j, i).
Graf hamiltonian
Un graf hamiltonian este un graf care conține un circuit hamiltonian.
Graf eulerian
Un graf eulerian este un graf care conține un circuit eulerian.