Informatica, Grafuri 11C

DEFINITIE:
Graful G se numeste nul daca multimea U este vida,adica daca nu are nici o muchie.

Un graf G se numeste complet daca are proprietatea ca oricare doua noduri ale sale sunt adiacente.
TEOREMA:

Numarul de muchii intrun graf complet cu n noduri este n(n-1)/2

DEFINITIE:
Se numeste graf partial a lui G=(X,U

) graful Gp =(X,V) undeV<=U(din graful G elimin muchii)

DEFINITIE: Se numeste subgraf al grafului G=(X,U) graful Gs=(Y,V) unde y este inclus sau egal in x si toate muchiile sin multimea V apartin si multimii U care au ambele extremitati in multimea Y(adica se obtin din G prin eliminarea unor noduri si a tuturor muchiilor incidente cu aceasta.)

Se numeste graf complementar a lui G, graful Gc care are proprietatea ca 2 noduri sunt adiacente in graful complementar nu sunt adiacente in G.

TEOREME: Numarul grafurilor partiale ale unui graf cu n muchii este 2 la m. Numarul de subgrafuri ale unui graf cu n noduri este 2 la n -1.

CONEXITATE

Un graf G este conex daca are propritatea ca orice pereche de noduri distincte,exista un lant care le leaga.
Daca un graf G nu e conex se numeste componenta conexa a grafului un subgraf conex al sau maximal in raport cu aceasta proprietate(contine numar maxim de noduri din gr care au proprietatea ca sunt legate de un lant)
TEOREME:
1.numarul minim de muchii necesare ca un graf sa fie conex este n-1(n-nr. De noduri)

2.Un graf conex cu n-1 muchii si n noduri este aciclic si maximal in rap . cu aceastra propietate

3.daca un graf neorientat conex are n noduri si m muchii,nr. de muchii care trebuie eliminate pentru a obtine u graf partial conex acyclic este m-n+1
4.daca un graf are n noduri si m muchii si p componente conexe nr. De muchii care trebuie eliminate pentru a obtine un graf partial acyclic(arbore) este = m-n+p
5.Pentru a obtine dintr-un graf neorientat conex doua componente conexe nr minim de muchii este=cu gradul minim din graf.
6.numarul maxim de muchii dintr-un graf neorientat cu n noduri si p componente conexe este (n-p)(n-p+1)/2.