Grafuri orientate

Se numește graf orientat perechea ordonată de mulțimi G=(X,E), unde X este o mulțime finită și nevidă numită mulțimea nodurilor, iar E este o mulțime de perechi ordonate, având ambele extremități în X, numită mulțimea arcelor grafului.

Putem considera un graf orientat asemănător unuia Graful neorientat are nodurile unite prin muchii fără direcție.neorientat, cu muchiile orientate într-o direcție. Pentru a le diferenția, numim muchiile grafului orientat arce.

La fel,

  • numărul nodurilor se notează cu n
  • numărul arcelor se notează cu m

Reprezentarea grafică a unui graf orientat

  • Nodurile se reprezintă prin puncte sau cercuri etichetate;
  • Arcele se reprezintă prin segmente orientate.
Exemplu graf orientat

Exemplul reprezentării unui graf orientat.


Terminologie

Când vorbim de grafuri orientate, e esențial să cunoaștem următoarele definiții și termeni:

1. Nod

Nodurile sunt punctele grafului orientat, alcătuind mulțimea nodurilor.
Ele sunt etichetate în general fie cu cifre, fie cu litere, pentru a putea fi diferențiate. Mulțimea de noduri se notează cu X și conține toate nodurile grafului.

Exemplu: Pentru graful descris mai sus, mulțimea nodurilor este X={1,2,3,4,5,6}.

2. Arce

Arcele sunt legături ordonate între nodurile grafului.

Extremitățile unui arc se scriu între paranteze rotunde, ordinea acestora fiind importantă în determinarea sensului arcului.

    Fie (x,y) un arc:
  • arcul pornește din x și ajunge în y;
  • x se numește extremitate inițială a arcului;
  • y se numește extremitate finală a arcului.

3. Adiacență

Două noduri x și y se numesc adiacente dacă formează un arc.

Exemplu: În graful de mai sus, nodul 2 este adiacent cu nodurile 1, 3 și 4.

4. Incidență

Două arce se numesc incidente dacă au o extremitate comună.

    Exemple (graful de mai sus):
  • arcul (6,3) este incident cu arcul (3,4) <=> 3 este vârf comun;
  • arcul (1,2) nu este incident cu arcul (5,6), deoarece nu au niciun nod în comun.

Un nod este incident cu un arc dacă este extremitate al acestuia.

    Exemple (graful de mai sus):
  • nodul 3 este incident cu arcul (1,3) și arcul (6,3);
  • nodul 1 nu este incident cu arcul (3,4), deoarece nu este extremitate al acestuia.

5. Gradul nodurilor

Gradul unui nod xreprezintă numărul de noduri adiacente cu x (sau numărul de arce incidente cu x).

    La grafuri orientate, avem două tipuri de grade:
  • Gradul interior reprezintă numărul arcelor care au extremitatea finală în nod și este notat cu d-(x);
  • Gradul exterior reprezintă numărul arcelor care au extremitatea inițială în nod și este notat cu d+(x).
    Exemple (din graful de mai sus):
  • d-(1)=1 ; d+(1)=2 ~ în nodul 1 „intră un arc și ies două”
  • d-(3)=3 ; d+(3)=1
  • d-(6)=1 ; d+(6)=1

Un nod izolat în graful orientat are ambele grade egale cu 0.


Formule grafuri orientate

Grafurile orientate au anumite proprietăți, din care se pot genera mai multe formule utile:

  • numărul maxim de arce într-un graf orientat cu n noduri este A2n    , sau n*(n-1) ;
  • suma gradelor nodurilor unui graf orientat este egală cu dublul numărului de arce, deci 2*m;
  • numărul de grafuri orientate ce se pot forma cu n vârfuri este egal cu 2A2n    , sau 2n*(n-1) ;