FORMULE

GRAFURI

CUPRINS

Grafuri neorientate

Grafuri orientate

Grafuri speciale

Arbori

*GRAFURI NEORIENTATE*

Numrul total de grafuri neorientate cu n noduri este

*Se numete graf neorientat (G) o pereche ordonat de mulimi (X,U), unde X este o mulime finit i nevid de elemente, iar U o mulime de perechi formate cu elemente distincte din mulimea X.

Suma gradelor tuturor nodurilor unui graf nerorientat este egal cu dublul numrului de muchii.

*Gradul unui nod x al grafului G este egal cu numrul muchiilor incidente cu nodul i se noteaz cu d(x).

Dac graful G neorientat are n noduri, n>2, atunci cel puin 2 noduri au acelai grad.

Pentru orice graf neorientat numrul nodurilor de grad impar este par.

Numrul minim de muchii pe care trebuie s le aib un graf neorientat cu n noduri, ca s nu existe noduri izolate este

LANT

CICLU

Lungimea maxim a unui lan este infinit.

Lungimea maxim a unui ciclu este m(numrul

de muchii).

*Numim lan o succesiune de noduri care au proprietatea c, oricare ar fi dou noduri succesive, ele sunt adiacente.

*Numim ciclu un lan n care toate muchiile/arcele sunt distincte dou cte dou i primul nod coincide cu ultimul.

GRAF PARTIAL

Numrul de grafuri pariale ale unui graf cu

m muchii este egal cu

*Fie graful G=(X,U) i mulimea VU. Graful Gp=(X,V) se numete graf parial al grafului G.

SUBGRAF

Numrul de subgrafuri ale unui graf cu n

noduri este egal cu

*Fie graful G=(X,U). Graful Gs=(Y,V) se numete

subgraf al grafului G dac YU i

muchiile/arcele din mulimea V sunt toate

muchiile/arcele din mulimea U care au ambele

extremiti n Y.

*GRAF ORIENTAT*

Numrul total de grafuri orientate care se pot

forma cu n noduri este

* Se numete graf orientat sau digraf (G) o pereche ordonat de mulimi (X,U), unde X este o mulime finit i nevid de elemente, iar U o mulime de perechi ordonate formate cu elemente distincte din mulimea X.

ntr-un graf orientat cu n vrfuri, suma gradelor interne ale tuturor nodurilor este egal cu suma gradelor exterioare ale tuturor nodurilor i cu numrul de arce.

*Elementele mulimii U se numesc arce.

*Gradul intern unui nod x al grafului G este egal

cu numrul arcelor care intr n nodul x i se noteaz cu d-(x).

*Gradul extern unui nod x al grafului G este egal

cu numrul arcelor care ies din nodul x i se noteaz cu d+(x).

GRAFURI COMPLETE

Numrul de muchii al uni graf neorientat

complet este

*Un graf cu n noduri se numete complet dac are proprietatea c, oricare ar fi dou noduri ale grafului, ele sunt adiacente.

Numrul de grafuri orientate complete care

se pot construi cu n noduri este egal cu .

LANT ELEMENTAR

DRUM ELEMENTAR

Dac un graf conine un lan ntre 2 noduri x i y atunci conine un lan elementar ntre nodurile x i y.

Lungimea maxim a unui lan elementar este n-1 respectiv n pentru ciclu elementar.

*Lanul elementar este lanul care conine numai noduri distincte.

Dac un graf conine un drum ntre 2 noduri x i y atunci conine un drum elementar ntre nodurile x i y.

* Numim drum o succesiune de noduri care au proprietatea c oricare ar fi dou noduri succesive ele sunt legate printr-un arc.

* Drumul elementar este drumul n care nodurile sunt distincte dou cte dou.

Dac un graf conine un ciclu atunci conine i un ciclu elementar.

Dac un graf conine un circuit atunci conine i un circuit elementar.

*Numim circuit un drum n care toate arcele sunt distincte dou cte dou i ale crui extremiti coincid.

* Circuitul elementar este circuitul n care toate nodurile sunt distincte dou cte dou cu excepia primului i a ultimului care coincid.

CONEXITATE

Numrul minim de muchii necesare ca pentru ca un graf neorientat s fie conex este n-1.

* Un graf G se numete graf conex dac are proprietatea c, pentru orice pereche de noduri diferite ntre ele, exist un lan care s le lege.

Un graf conex cu n noduri i n-1 muchii este aciclic i maximal cu aceast proprietate.

Dac un graf neorientat conex are n noduri i m muchii, numrul de muchii care trebuie eliminate, pentru a obine un graf parial conex aciclic este m-n+1.

Dac un graf are n noduri , m muchii i p componente conexe , numrul de muchii care trebuie eliminate pentru a obine un graf parial aciclic (arbore) este egal cu m-n+p.

Pentru a obine dintr-un graf neorientat conex, 2 componente conexe, numrul minim de muchii care trebuie eliminate este cel mult egal cu

gradul minim din graf.

Numrul maxim de muchii dintr-un graf neorientat cu n noduri i p componente conexe este

*GRAFURI SPECIALE*

GRAF HAMILTONIAN

Un graf cu mai mult de 2 noduri este hamiltonian

dac gradul fiecrui nod este

* Numim lan hamiltonian un lan elementar ce conine toate nodurile grafului.

*Numim ciclu hamiltonian un ciclu elementar ce

conine toate nodurile grafului.

*Un graf ce conine un ciclu hamiltonian se numete graf hamiltonian.

Numrul de cicluri hamiltoniene dintr-un graf

complet cu n noduri este

GRAF EULERIAN

Un graf ce nu conine grafuri izolate este eulerian dac i numai dac este conex i gradele tuturor nodurilor sunt pare.

*Numim ciclu eulerian un ciclu ce conine toate muchiile grafului.

*Un graf ce conine un ciclu eulerian se numete graf eulerian.

GRAF TURNEU

Orice graf turneu conine un drum elementar care trece prin toate nodurile grafului.

*Un graf orientat n care, ntre oricare 2 noduri exist un singur arc i numai unul, se numete graf turneu.

Pentru orice graf turneu, exist un nod x, astfel nct toate nodurile y x sunt accesibile din x pe un drum care conine un arc sau dou arce.

*ARBORI*

Orice arbore cu n noduri are (n-1) muchii.

*Se numete arbore cu rdcin un arbore n care exist un nod privilegiat numit nod rdcin.

Un arbore binar strict care are n noduri

terminale are n total (2*n-1) noduri.

*Se numete arbore binar strict un arbore care are proprietatea c fiecare nod, cu excepia nodurilor terminale, are exact 2 descendeni.

*Nodurile fr succesori se numesc frunze sau noduri terminale.

Un arbore binar complet care are n noduri

terminale are n total (2*n-1) noduri.

*Se numete arbore binar complet un arbore binar strict care are toate nodurile

terminale pe acelai nivel.

Proiect realizat de:Blaj Mdlina

Clasa a XI-a B

Prof. coordonator:

Gavril Florin