Grafuri orientate-Notiuni introductive

Dacă arcele unui graf au asociate sensuri de parcurgere atunci vom spune că graful G este orientat iar în caz negativ spunem că graful este neorientat. În cazul grafurilor neorientate arcul dintre nodul i şi nodul j este acelaşi cu arcul dintre nodul j şi nodul i şi se notează (i, j) iar la grafurile orientate se stabileşte pentru fiecare arc câte un sens de parcurs si deci arcul ( i, j ) nu mai este identic cu arcul ( j, i ).

În cazul grafurilor orientate gradul unui nod este dat de suma dintre semigradul exterior al nodului şi semigradul interior.

Se numeşte semigrad exterior al nodului i numărul de arce care “pleacă” din nodul i şi se notează grad⁺( i ).

Se numeşte semigrad interior al nodului i numărul de arce care “intră” din nodul i şi se notează grad^-( i ).

grad( i )= grad⁺( i )+ grad^-( i )

În cazul grafurilor orientate există următoarea relaţie:

Exemplu de graf orientat:

Exemplu:

- pentru nodul 1 gradul este 3: semigradul exterior este 2

semigradul interior este 1

- pentru nodul 3 gradul este 5: semigradul exterior este 2

semigradul interior este 3

- pentru nodul 4 gradul este 1: semigradul exterior este 0

semigradul interior este 1

- pentru nodul 6 gradul este 1: semigradul exterior este 1

semigradul interior este 0

DEF. 12.

Se numeşte graf turneu un graf orientat pentru care între oricare două vârfuri există doar un singur arc (într-un sens sau altul). Folosind acelaşi raţionament ca şi în cazul grafurilor complete, deducem că există :

grafuri turneu cu n noduri.

Grafurile turneu au următoarele proprietăţi care sunt foarte uşor de dedus:

DEFINITIE. Se numeşte graf ponderat un graf orientat sau nu în care fiecărei muchii i s-a asociat un cost dat, de obicei, o funcţie de cost f: U→R. Exemplu de graf ponderat:

DEFINITIE. Graful orientat G1=(X,U1) se numeşte graful transpus al grafului G dacă G1 se obţine din graful G prin inversarea sensului arcelor sale.

Lecţie AEL