Definitie:
Se numeste graf orientat sau digraf (G) o pereche ordonata de multimi (X,U), unde X este o multime finita si nevida de elemente , iar U o multime de perechi ordonate formate cu elemente distincte din multimea X.
Elementele multimii U se numesc arce. Multimea U se mai n umeste si multimea arcelor.
Numim varfuri adiacente orice pereche de varfuri care formeaza un arc .Fiecare din cele doua varafuri spunem ca sunt incidente cu arcul pe care il formeaza.
Pentru arcul (x,y) spunem ca x este extremitatea initiala iar y este extremitatea finala.
Se numesc arce incidente doua arce care au o extremitate comuna.
- Se numeste succesor al varfului x oirce varf la care ajunge un arc care iese din varful x
- Se numeste predecesor al varfului x orice varf la care intra un arc in varful x
- Se numeste nod sursa al grafului, nodul care are multimea succesorilor formata din toate celelalte noduri mai putin el, iar multimea predecesorilor este vida.
- Nodul destinatie al unui graf este nodul care are multimea predecesorilor formata din toate celelalte noduri mai putin el ia rmultimea succesorilor este vida.
Gradul intern unui nod x al grafului G este egal cu numarul arcelor care intra in nodul x si se noteaza cu d-(x). Grdaul extern unui nod x al grafului G este egal cu numarul arcelor care ies din nodul X si se noteaza cu d+(x).
Terminologie:
Se numeste nod terminal un nod care are suma gradelor egala cu 1.
Se numeste nod izolat un nod cera are suma gradelor egal.
Teorema :Intr-un garf orientat cu n varfuri , suma gradelor interne ale tuturor nodurilor este egala cu suma gradelor exterioare ale tuturor nodurilor si cu numarul dse arce.
Grafuri speciale:
- Graful G se numeste graf nul daca multimea U este vida , adica graful nu are muchii;
- Un garf cu n noduri se nu8meste complet daca are proprietatea ca oricare ar fi doua noduri ale grafului ele sunt adiacente;
- Numim lant o succesiune de noduri care au proprietatea ca oricare ar fi doua noduri succesive , ele sunt adiacente.
- Numim ciclu un lant in care toate muchiile/arcele sunt distincte doua cate doua si primul nod coincide cu ultimul
- Un graf fara cicluyri se numeste graf aciclic.
- Numim drum o succesiune de noduri care au proprietatea ca oricare ar fi doua noduri succesive ele sunt legate printr-un arc.
- Numim circuit ,un drum in care toate arcele sunt distincte doua cate doua si ale carui extremitati coincid.
Tremonologie:
Lungimea unui lant reprezinta numarul de muchii/arce din care este format
Lantul simplu este lantul care contine numai muchii/arce distincte
Lantul compus este lantul care nu este format din muchii/arce distincte
Lantul elementar este lantul care contine numai noduri distincte .
Ciclu elementar este un ciclu in care toate nodurile sunt distincte doua cate doua (cu exeptia primului si ultimului nod).
Lungimea unui drum este data de numarul de arce pe acre il compun.
Drumul simplu este drumul care contine numai arce distincte.
Drumul compus este drumul care nu este format numai din arce distincte.
Drumul elementar este drumul in care nodurile sunt distincte dpua cate doua.
Circuitul elementar este circuitul in care toate nodurile sunt distincte doua cate doua cu exceptia primultui si a ulitmului care coincid.
Teoreme:
- Daca un garf contine un lant intre doua noduri x si y atunci contine un lant elementar intre nodurile x si y
- Daca un garf contine un drum intre doua noduri x si y atunci contine un drum elementar intre nodurile x si y
- Daca un graf contine un ciclu atunci contine si un ciclu elementar
- Daca un graf contine un circuit atunci contine si un circuit elementar.
Un graf G se numeste graf conex daca are proprietatea ca pentru orice pereche de de noduri diferite intre ele exista un lant care sa le lege.
Un graf conex are o singura componenta conexa.
Un graf orientat G se numeste graf tare conex daca are proprietatea ca pentur orice pereche de noduri x si y , diferite inter ele , exista un drum de la nodul x spre nodul y si exista drum de la nodul y la nodulx.
Daca un graf orintat g nu este tare conex se numeste componenta tare conexa a grafului, un subgraf tar3e conex al sau,maximal in raport cu aceasta proprietate (contine numarul maxim de noduri din g care au proprietatea ca sunt legate printr-un drum in ambele sensuri).
Teoreme:
- Numarul minim de muchii necesare ca pentru un graf neorientat sa fie conex este n-1
- Un garf conex cu n noduri si n-1 muchii este aciclic si maximal cu aceasta proprietate .
- Daca un graf neorientat conex are n noduri si m muchii , numarul de muchii care trebuie eliminate pentru a obtine un graf partial conex aciclic este m-n+1 .
- Daca un graf are n noduri , m muchii si p componente conexe, numarul de muchii care trebuie eliminate pentru a obtine un graf partial aciclic(arbore) este egal cu m-n+p
- Pentru a obtine dintr-un graf neorientat conex , 2 componente conexe, nuamrul minim de muchii care trebuie eliminate este cel mult egal cu gradul minim din graf.
- Numarul maxim de muchii dintr-un graf neorientat cu n noduri si p componente conexe este: (n-p)*(n-p+1)/2.
Definitii:
- Numim lant hamiltonian un lant elememntar ce contine toate nodurile grafului .
- Numi ciclu hamiltoniann un ciclu elementar ce contine toate nodurile grafului.
- Un graf ce contine un ciclu hamiltonian se numeste graf hamiltonian.
- Numim ciclu eulerian un ciclu ce contine toate muchiile grafului.
- Un graf ce contine un ciclu eulerian se numeste graf eulerian .
- Un graf orientat in care, intre oricare doua noduri exista un singur arc si numai unul se numeste graf turneu
- Un graf cu mai mult de 2 noduri este hamiltonian daca gradul fiecarui nod este >=n/2.
- Un graf ce nu contine grafuri izolate este eulerian daca si numai daca este conex si gradele tuturor nodurilor sunt pare.
- Numarul de cicluri hamiltoniene dintr-un graf complet cu n noduri este (n-1)!/2.
- Orice graf turneu contine un drum elementar care trece prinj toate nodurile grafului.
- Pentru orice graf turneu, exista un nod x , astfel incat toate nodurile y!=x sunt accesibile din x pe un drum care contine un arc sau doua arce.
Liste
Crearea unei liste:
int main()
{struct nod
{int x;
nod *urm;} *p,*u,*l;
int n,i;
cout<<"n="; cin>>n;
p=new nod;
cin>>p->x;
u=p;
u->urm=NULL;
for(i=2; i<=n; i++)
{l=new nod;
cin>>l->x;
u->urm=l;
u-l;
u->urm=NULL;}
Afisarea listei:
while(l!=NULL)
{cout<
l=l->urm;}
Adaugarea unui nod in fata listei:
for(i=1;i<=n;i++)
l=new nod;
l->urm=p;
p=l;
p->x=p->urm->x;
Adaugarea unui nod in interior:
(parcurgem lista pana la nodul dorit)
q=new nod ;
q->urm=l->urm;
l->urm=q;
q->x=q->urm=x;
Stergera:
while(i<=k && p!=NULL)
{l=p;
p=p->urm;
i++;
delete l;}
Variante bac liste simplu inlantuite:
Varianta 41
2. Fiecare nod al unei liste simplu înlănţuite, cu cel puţin 4 noduri, reţine in câmpul urm
adresa nodului următor din listă sau NULL dacă nu are un nod următor. Ştiind că variabila p
reţine adresa primului nod din listă, variabila q reţine adresa celui de-al doilea nod din listă,
iar variabila r reţine adresa celui de-al treilea nod din listă, care este secvenţa prin care se
interschimbă al doilea cu al treilea element din lista iniţială? (4p.)
a. p->urm=r;
q->urm=r->urm;
r->urm=q;
b. p->urm=r;
r->urm=q->urm;
q->urm=r->urm;
c. r->urm=q->urm;
q->urm=r->urm;
p->urm=r;
d. q->urm=r->urm;
p->urm=r;
r->urm=q->urm;
Varianta a) a problemei este cea corecta deoarece rezulta ca :
p->urm = q iar q=r ;
q->urm = r iar r =r->urm ;
in final r->urm = q deci din cele trei relatii deducem ca q=r si r=q ( interschimbarea are loc )
Varianta 42
2. Într-o listă simplu înlănţuită alocată dinamic, cu cel puţin două noduri, fiecare nod reţine în
câmpul urm adresa nodului următor din listă sau NULL dacă nu are un nod următor. Ştiind
că variabila p reţine adresa primului nod din listă, iar variabila q este de acelaşi tip cu p,
care este secvenţa ce realizează eliminarea celui de-al doilea nod din listă? (4p.)
a.) q=p->urm;
p->urm=p->urm->urm;
delete q;
free(q);
b.) p->urm=p->urm->urm;
delete p;
free(p);
c.) q=p->urm;
q->urm=p->urm->urm;
delete q;
free(q);
d.) q=p->urm;
q->urm=p->urm->urm;
delete q;
free(q);
Varianta a) este cea corecta deoarece variabila q retine adresa primului nod iar dupa executarea seceventei q=q->urm se elimina al doilea nod din lista cu functia delete q dupa care se eleibereaza nodul respectiv.
Varianta 44
2. Într-o listă simplu înlănţuită cu cel puţin 4 elemente, fiecare nod reţine in câmpul urm
adresa nodului următor din listă sau NULL dacă nu are un nod următor. Ştiind că iniţial
variabila p reţine adresa primului nod din listă, după executarea cărei secvenţe p va reţine
adresa ultimului nod din listă? (4p.)
a. while(p->urm!=NULL) p=p->urm;
b. while(p!=NULL) p=p->urm;
c. p=p->urm;
d. p=p->p->urm;
Varianta b) este corecta deoarece cat timp avem noduri in lista nodul p va prelua adresa nodului urmator pana la nodul final .
