Cuprins / Clasa a XI-a / Grafuri orientate

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.
  • 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.
graf orientat

Terminologie

1. Nod

Nodurile sunt punctele unui graf și alcătuiesc mulțimea nodurilor.
  Ele se numerotează fie cu cifre, fie cu litere, pentru a putea fi diferențiate. Mulțimea nodurilor se notează cu X și conține toate nodurile unui graf.

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 unei muchii se scriu între paranteze rotunde, iar fiind vorba despre grafuri orientate, ordinea lor va conta.

    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: Nodul 2 este adiacent cu nodurile 1, 3 și 4

4. Incidență

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

    Exemple:
  • 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:
  • 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

Se numește gradul unui vârf x, numărul de vârfuri adiacente cu x (sau numărul de muchii incidente cu x).

    Există două tipuri de grade pentru un vârf x:
  • Gradul interior al lui x este egal cu numărul arcelor care au extremitatea finală în x și este notat cu d-(x);
  • Gradul exterior a lui x este egal cu numărul arcelor care au extremitatea inițială în x și este notat cu d+(x).
    Exemple:
  • d-(1)=1 ; d+(1)=2
  • d-(3)=3 ; d+(3)=1
  • d-(6)=1 ; d+(6)=1

Proprietăți ale grafurilor orientate

  • numărul maxim de arce dintr-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;
  • numărul de grafuri orientate cu n vârfuri este egal cu 2A2n    , sau 2n*(n-1) ;