teorie grafuri

66
6 1 2 5 7 3 4 figura1 – reprezentare grafică Capitolul 12. Grafuri (Heading 1) 12. 1 Noţiuni teoretice (Heading 2) Grafuri neorientate Definiţie: Se numeşte graf neorientat (G) o pereche ordonată de mulţimi (X,U), unde X este o mulţime finită şi nevidă de elemente, iar U o mulţime de perechi formate cu elemente distincte din mulţimea X. G=(X,U) X={1,2,3,4,5,6,7} U={(1,2),(2,3),(3,7),(7,5),(1,6),(7,1),(2,5),(2,7)} Terminologie: Elementele mulţimii X se numesc noduri sau vârfuri. Mulţimea X se mai numeşte şi mulţimea nodurilor sau vârfurilor. Ordinul grafului reprezintă numărul de noduri ale grafului. Elementele mulţimii U se numesc muchii. Mulţimea U se mai numeşte şi mulţimea muchiilor. Numim noduri adiacente orice pereche de noduri care formează o muchie. Fiecare din cele două noduri spunem, că sunt incidente cu muchia pe care o formează. Exemplu: Nodul 1 este adiacent cu nodurile 2,6,7; nodul 5 este adiacent cu nodurile 2,7 etc. Nodurile 3,7 sunt incidente cu muchia (3,7). (fig 1) Nodurile vecine ale unui nod sunt toate nodurile adiacente cu el.

Transcript of teorie grafuri

Page 1: teorie grafuri

61

2

5

7

3

4

figura1 – reprezentare grafică

Capitolul 12. Grafuri (Heading 1)

12. 1 Noţiuni teoretice (Heading 2)

Grafuri neorientate

Definiţie: Se numeşte graf neorientat (G) o pereche ordonată de mulţimi (X,U), unde X este o mulţime finită şi nevidă de elemente, iar U o mulţime de perechi formate cu elemente distincte din mulţimea X.

G=(X,U)X={1,2,3,4,5,6,7}U={(1,2),(2,3),(3,7),(7,5),(1,6),(7,1),(2,5),(2,7)}

Terminologie:Elementele mulţimii X se numesc noduri sau vârfuri. Mulţimea X se mai numeşte şi mulţimea nodurilor sau vârfurilor.Ordinul grafului reprezintă numărul de noduri ale grafului.Elementele mulţimii U se numesc muchii. Mulţimea U se mai numeşte şi mulţimea muchiilor.Numim noduri adiacente orice pereche de noduri care formează o muchie. Fiecare din cele două noduri spunem, că sunt incidente cu muchia pe care o formează.

Exemplu: Nodul 1 este adiacent cu nodurile 2,6,7; nodul 5 este adiacent cu nodurile 2,7 etc.Nodurile 3,7 sunt incidente cu muchia (3,7). (fig 1)

Nodurile vecine ale unui nod sunt toate nodurile adiacente cu el.Se numesc muchii incidente două muchii care au o extremitate comună.

Exemplu:Muchiile (1,2) şi (2,7) sunt incidente având ca extremitate comună nodul 2. (fig 1)

Definiţie: Gradul unui nod x al grafului G este egal cu numărul muchiilor incidente cu nodul şi se notează cu d(x).

Exemplu:d(1)=3;d(2)=4;d(3)=2 etc. (fig 1)

Terminologie:Se numeşte nod terminal un nod care are gradul egal cu 1 .Se numeşte nod izolat un nod care are gradul 0.

Page 2: teorie grafuri

61

2

5

7

3

4

figura 2 – reprezentare grafică

Exemplu:Nodul 6 este nod terminal.Nodul 4 este nod izolat. (fig 1)

Teoreme:

1. Numărul total de grafuri neorientate cu n noduri este .2. Suma gradelor tuturor nodurilor unui graf nerorientat este egală cu dublul numărului de muchii.

3. Dacă graful G neorientat are n noduri, n>2, atunci cel puţin 2 noduri au acelaşi grad.4. Pentru orice graf neorientat numărul nodurilor de grad impar este par.5. Numărul minim de muchii pe care trebuie să le aibă un graf neorientat cu n noduri,

ca să nu existe noduri izolate este [

n+12 ].

Grafuri orientate

Definiţie: Se numeşte graf orientat sau digraf (G) o pereche ordonată de mulţimi (X,U), unde X este o mulţime finită şi nevidă de elemente, iar U o mulţime de perechi ordonate formate cu elemente distincte din mulţimea X.

G1=(X1,U1)X1={1,2,3,4,5,6,7}U1={(1,2),(2,3),(3,7),(5,7),(1,6),(7,1),(5,2),(2,7)}

Terminologie:Elementele mulţimii U se numesc arce. Mulţimea U se mai numeşte şi mulţimea arcelor.Numim vârfuri adiacente orice pereche de vârfuri care formează un arc. Fiecare din cele două vârfuri spunem, că sunt incidente cu arcul pe care îl formează.

Exemplu: Nodul 1 este adiacent cu nodurile 2,6,7; nodul 5 este adiacent cu nodurile 2,7 etc.Nodurile 3,7 sunt incidente cu muchia (3,7). (fig 2)

Pentru arcul (x,y) spunem că x este extremitatea iniţială iar y este extremitatea finală.

Exemplu:Arcul (5,2) are vârful 5 ca extremitate iniţială şi vârful 2 ca extremitate finală. (fig 2)

Se numesc arce incidente două arce care au o extremitate comună.

Page 3: teorie grafuri

61

2

5

4

3

figura 3

1 2

5

3

figura 4

4

Se numeşte succesor al vârfului x orice vârf la care ajunge un arc care iese din vârful x.Mulţimea succesorilor vârfului x este formată din mulţimea vârfurilor la care ajung arce care ies din vârful x şi se notează Γ+(x). Mulţimea muchiilor ce îl pe x ca extremitate iniţială se notează ω+(x).

Exemplu:Vârfurile 2 şi 7 sunt succesori ai vârfului 5.Γ+(2)={3,4}ω+(2)={(2,4),(2,3)} (fig 3)

Se numeşte predecesor al vârfului x orice vârf de la care intră un arc în vârful x.Mulţimea predecesorilor vârfului x este formată din mulţimea vârfurilor de la care ajung arce care intră în vârful x şi se notează Γ-(x).Mulţimea muchiilor ce îl pe x ca extremitate finală se notează ω-(x).

Exemplu:Vârfurile 2,3 şi 5 sunt predecesori ai vârfului 7. Γ-(6)={1}ω-(3)={(1,3),(2,3)} (fig 3)

Nod sursă al grafului este nodul care are mulţimea succesorilor formată din toate celelalte noduri mai puţin el iar mulţimea predecesorilor săi este vidă.

Exemplu:Vârful 1 din graful din figura 3 este vârf sursă.

Nod destinaţie al grafului este nodul care are mulţimea predecesorilor formată din toate celelalte noduri mai puţin el iar mulţimea succesorilor săi este vidă.

Exemplu:Vârful 5 din graful din figura 4 este vârf destinaţie.

Definiţie: Gradul intern unui nod x al grafului G este egal cu numărul arcelor care intră în nodul x şi se notează cu d-(x).Gradul extern unui nod x al grafului G este egal cu numărul arcelor care ies din nodul x şi se notează cu d+(x).

Exemplu:d+(1)=1 d-(1)=1 d+(3)=1 d-(3)=0 (fig 4); d+(5)=1 d-(5)=1 d+(4)=0 d-(4)=4 (fig 3)

Terminologie:Se numeşte nod terminal un nod care are suma gradelor egală cu 1.Se numeşte nod izolat un nod care suma gradelor egală cu 0.

Exemplu:Vârful 3 este terminal în graful din figura 4.

Page 4: teorie grafuri

6

1

2

5 3

4

figura 5

6

1

2 5

3

4

figura 6

Teoreme:

1. Numărul total de grafuri orientate care se pot forma cu n noduri este .2. Într-un graf orientat cu n vârfuri, suma gradelor interne ale tuturor nodurilor este egală cu suma gradelor exterioare ale tuturor nodurilor şi cu numărul de arce.

Metode de reprezentare:Considerăm un graf G cu n noduri numerotate de la 1 la n şi m muchii/arce.1. Matricea de adiacenţă: este o matrice cu n linii şi n coloane ale cărei elemente

sunt definite astfel

Exemplu:Pentru graful neorientat din figura 5 matricea de adiacenţă este:

Pentru graful orientat din figura 6 matricea de adiacenţă este:

2. Matricea de incidenţă: Pentru graful neorientat G este o matrice cu n linii şi m coloane ale cărei elemente sunt definite astfel:

Exemplu:Pentru graful neorientat din figura 5 matricea de incidenţă este:

m1=(1,3)m2=(1,4)m3=(1,6)m4=(4,5)

m5=(4,2)m6=(2,3)m7=(2,6)m8=(3,6)

0 0 1 1 0 10 0 1 1 0 11 1 0 0 0 11 1 0 0 1 00 0 0 1 0 01 1 1 0 0 0

0 0 0 1 0 01 0 0 0 1 00 0 0 0 1 00 0 0 0 1 10 0 0 1 0 00 0 1 1 0 0

1 1 1 0 0 0 0 00 0 0 0 1 1 1 01 0 0 0 0 1 0 10 1 0 1 1 0 0 00 0 0 1 0 0 0 00 0 1 0 0 0 1 1

Page 5: teorie grafuri

Matricea de incidenţă a unui graf orientat este o matrice cu n linii şi m coloane ale cărui elemente sunt definite astfel:

Exemplu:Pentru graful neorientat din figura 5 matricea de incidenţă este:

3. Lista muchiilor/arcelor: este formată din m elemente care conţin, fiecare, câte o pereche de noduri, x şi y care formează o muchie/arc. În implementare se pot utiliza fie o matrice de dimensiuni 2Xm sau mX2, un vector de structuri, sau liste liniare alocate dinamic ce memorează extremităţile muchiilor/arcelor.

4. Lista de adiacenţă: este formată din listele Li(1in) care conţin toţi vecinii unui nod xi dacă graful G este neorientat, respectiv toţi succesorii nodului xi dacă graful G este orientat.

Exemplu:

Grafuri speciale

Definiţie: Graful G se numeşte graf nul dacă mulţimea U este vidă, adică graful nu are muchii.Definiţie: Un graf cu n noduri se numeşte complet dacă are proprietatea că, oricare ar fi două noduri ale grafului, ele sunt adiacente.

Teoreme:

Numărul de muchii al uni graf neorientat complet este

n(n−1)2 .

m1=(1,4)m2=(2,1)m3=(2,5)m4=(3,5)m5=(4,5)

m6=(4,6)m7=(5,4)m8=(6,3)m9=(6,4)

1 -1 0 0 0 0 0 0 00 1 1 0 0 0 0 0 00 0 0 1 0 0 0 -1 0-1

0 0 0 11 -1 0

-1

0 0 -1 -1 -1 0 1 0 00 0 0 0 0 -1 0 1 1

Listele de adiacenţă pentru graful din figura 5:

Listele de adiacenţă pentru graful din figura 6:

1: 3, 4, 6 1: 42: 3, 4, 6 2: 1, 53: 1, 2, 6 3: 54: 1, 2, 5 4: 5, 65: 4 5: 46: 1, 2, 3 6: 3, 4

Page 6: teorie grafuri

7

1

2

53

4

graful iniţial

6 7

1

2

53

4

graful parţial obţinut prin eliminarea muchiilor (4,6) (2,7) (3,7) (1,7)

6

figura 7

6

1

2 5

3

4

graful iniţial

2 5

3

4

subgraful obţinut prin eliminarea vârfurilor 1 şi 6

figura 8

3

1

2

5

4

3

1

2

5

4

Numărul de grafuri orientate complete care se pot construi cu n noduri este egal cu

Grafuri derivate dintr-un graf

Definiţie: Fie graful G=(X,U) şi mulţimea VU. Graful Gp=(X,V) se numeşte graf parţial al grafului G.

Exemplu:

Definiţie: Fie graful G=(X,U). Graful Gs=(Y,V) se numeşte subgraf al grafului G dacă YU şi muchiile/arcele din mulţimea V sunt toate muchiile/arcele din mulţimea U care au ambele extremităţi în Y.

Exemplu:

Definiţie: Un graf se numeşte complementar al lui G daca are proprietatea că 2

noduri sunt adiacente în graful dacă şi numai dacă nu sunt adiacente în G.

Exemplu:Următoarele grafuri sunt complementare:

figura 9

Page 7: teorie grafuri

3

1

2

54

7

6

figura 10

6

3

5

41

2

figura 11

Teoreme:

1. Numărul de grafuri parţiale ale unui graf cu m muchii este egal cu .

2. Numărul de subgrafuri ale unui graf cu n noduri este egal cu .

Conexitate

Definiţie: Numim lanţ o succesiune de noduri care au proprietatea că, oricare ar fi două noduri succesive, ele sunt adiacente.Definiţie: Numim ciclu un lanţ în care toate muchiile/arcele sunt distincte două câte două şi primul nod coincide cu ultimul.Definiţie: Un graf fără cicluri se numeşte graf aciclic.Definiţie: Numim drum o succesiune de noduri care au proprietatea că oricare ar fi două noduri succesive ele sunt legate printr-un arc.Definiţie: Numim circuit un drum în care toate arcele sunt distincte două câte două şi ale cărui extremităţi coincid.

Terminologie:Lungimea unui lanţ reprezintă numărul de muchii/arce din care este formatLanţul simplu este lanţul care conţine numai muchii/arce distincte.Lanţul compus este lanţul care nu este format din muchii/arce distincte.Lanţul elementar este lanţul care conţine numai noduri distincteCiclu elementar este un ciclu în care toate nodurile sunt distincte două câte două.Lungimea unui drum este dată de numărul de arce care îl compun.Drumul simplu este drumul care conţine numai arce distincte.Drumul compus este drumul care nu este format numai din arce distincte.Drumul elementar este drumul în care nodurile sunt distincte două câte două.Circuitul elementar este circuitul în care toate nodurile sunt distincte două câte două cu excepţia primului şi a ultimului care coincid.

Exemplu:

L1=(1,5,3,2,5) – lanţL2=(6,1,3,2,5,7) – lanţ elementarC1=(7,5,2,3,4,2,7) – cicluC2=(6,3,4,1,7,6) – ciclu elementar

L1=(1,5,3,6,5,4) – lanţL2=(6,1,5,4,2) – lanţ elementarC1=(1,6,5,4,2,5,1) – cicluC2=(4,5,2,4) – ciclu elementarD1=(1,5,2,4,5,6) – drumD2=(3,6,2,4,5) – drum elementarC3=(2,4,2,5,2) – circuitC4=(4,5,3,6,2,4) – circuit elementar

Page 8: teorie grafuri

1

5

2

3

4

6

GT2

3

2

41

5

GT3

8

7

7

3

5

4

6

2

GT1

1

2

9

1

6

5

8 4

3

7

GT4

Teoreme:

1. Dacă un graf conţine un lanţ între 2 noduri x şi y atunci conţine un lanţ elementar între nodurile x şi y.

2. Dacă un graf conţine un drum între 2 noduri x şi y atunci conţine un drum elementar între nodurile x şi y.

3. Dacă un graf conţine un ciclu atunci conţine şi un ciclu elementar.4. Dacă un graf conţine un circuit atunci conţine şi un circuit elementar

Definiţie: Un graf G se numeşte graf conex dacă are proprietatea că, pentru orice pereche de noduri diferite între ele, există un lanţ care să le lege.Definiţie: Dacă un graf G nu este conex, se numeşte componentă conexă a grafului un subgraf conex al său, maximal în raport cu această proprietate (conţine numărul maxim de noduri din G care au proprietatea că sunt legate cu un lanţ).Un graf conex are o singură componentă conexă.Definiţie: Un graf orientat G se numeşte graf tare conex dacă are proprietatea că pentru orice pereche de noduri diferite între ele, există un drum care să le lege.Definiţie: Dacă un graf orientat G nu este tare conex, se numeşte componentă tare conexă a grafului, un subgraf tare conex al său, maximal în raport cu această proprietate (conţine numărul maxim de noduri din G care au proprietatea că sunt legate printr-un drum).

Exemplu:

Graful GT1 este graf conex dar nu este tare conex; Componentele tare conexe din sunt determinate de submulţimile {2}, {6}, {4,5} şi {1,3,7}Graful GT2 este tare conexGraful GT3 este conexGraful GT4 nu este conex; componentele conexe sunt determinate de submulţimile {1,2}, {3,4,5,8} şi {6,7,9}

Un graf tare conex are o singură componentă tare conexa (graful însuşi).Componenta tare conexă din care face parte un nod este dată de intersecţia dintre subgraful predecesorilor şi subgraful succesorilor acelui nod.Graful componentelor tare conexe ale unui graf care nu este tare conex G se obţine prin reducerea fiecărei componente conexe la un nod.

Page 9: teorie grafuri

7

1 2

36

GT2

2

1

6

5

4

3

7

GT1

Teoreme:

1. Numărul minim de muchii necesare ca pentru ca un graf neorientat să fie conex este n-1.2. Un graf conex cu n noduri şi n-1 muchii este aciclic şi maximal cu această proprietate.3. Dacă un graf neorientat conex are n noduri şi m muchii, numărul de muchii care trebuie eliminate, pentru a obţine un graf parţial conex aciclic este m-n+1.4. Dacă un graf are n noduri , m muchii şi p componente conexe , numărul de muchii care trebuie eliminate pentru a obţine un graf parţial aciclic (arbore) este egal cu m-n+p.5. Pentru a obţine dintr-un graf neorientat conex, 2 componente conexe, numărul minim de muchii care trebuie eliminate este cel mult egal cu gradul minim din graf.6. Numărul maxim de muchii dintr-un graf neorientat cu n noduri şi p componente

conexe este

(n−p )∗(n−p+1)2 .

Grafuri speciale

Definiţie: Graful G se numeşte graf bipartit dacă există 2 mulţimi nevide de noduri A

şi B care au următoarele proprietăţi: şi şi orice muchie (arc) din mulţimea U are o extremitate în mulţimea de noduri A şi o altă extremitate în mulţimea de noduri B.Definiţie: Graful bipartit G se numeşte graf bipartit complet dacă pentru orice nod

care aparţine lui A şi orice nod care aparţine lui B - există o muchie (un arc)

formată din cele 2 noduri care aparţine mulţimii U ( ).

Exemplu:

Graful GT1 este graf bipartit. A={1,3,5} B={2,4,6,7}Graful GT2 este bipartit complet. A={1,2} B={3,6,7}

Definiţie:. Numim lanţ hamiltonian un lanţ elementar ce conţine toate nodurile grafului.Definiţie:. Numim ciclu hamiltonian un ciclu elementar ce conţine toate nodurile grafului.Definiţie: Un graf ce conţine un ciclu hamiltonian se numeşte graf hamiltonian.Definiţie: Numim ciclu eulerian un ciclu ce conţine toate muchiile grafului.Definiţie: Un graf ce conţine un ciclu eulerian se numeşte graf eulerian.Definiţie: Un graf orientat în care, între oricare 2 noduri există un singur arc şi numai unul, se numeşte graf turneu.

Page 10: teorie grafuri

2

1

65

43

7

GT1

1

5

2

4

3

GT2

2

6

2

1

3

GT3

5

7

n=0

n=1

n=2

1

5

2

4

3

6

A1

3

2

4

6

75 1

A2

figura 12

5

1

4

2

3 6

A3

Exemplu:

Graful GT1 este hamiltonian dar nu este eulerian.Graful GT2 este hamiltonian şi eulerian.Graful GT3 este eulerian dar nu şi hamiltonian.

Teoreme:1. Un graf cu mai mult de 2 noduri este hamiltonian dacă gradul fiecărui nod este

.2. Un graf ce nu conţine grafuri izolate este eulerian dacă şi numai dacă este conex şi gradele tuturor nodurilor sunt pare.

3. Numărul de cicluri hamiltoniene dintr-un graf complet cu n noduri este .4. Orice graf turneu conţine un drum elementar care trece prin toate nodurile grafului.5. Pentru orice graf turneu, există un nod x, astfel încât toate nodurile y x sunt accesibile din x pe un drum care conţine un arc sau două arce.

Arbori

Definiţie: Un arbore liber este un graf neorientat conex şi fără cicluri. Definiţie: Se numeşte arbore cu rădăcină un arbore în care există un nod privilegiat numit nod rădăcină.

Definiţie: Se numeşte arborescenţă sau structură arborescentă un arbore cu rădăcină în care s-a stabilit nodul rădăcină.Definiţie: Un arbore poziţional este un arbore cu rădăcină în care este precizată poziţia fiecărui fiu.Definiţie: Se numeşte arbore binar strict un arbore care are proprietatea că fiecare nod, cu excepţia nodurilor terminale, are exact 2 descendenţi.

Page 11: teorie grafuri

Definiţie: Se numeşte arbore binar echilibrat un arbore binar care are proprietatea că diferenţa dintre înălţimile celor doi subarbori ai oricărui nod este cel mult 1.Definiţie: Se numeşte arbore binar complet un arbore binar strict care are toate nodurile terminale pe acelaşi nivel.

Exemplu:Arborele A2 din figura 12 este arbore binar strict şi complet.Arborii A2 şi A3 din aceeaşi figură sunt echilibraţi.

Terminologie:Nodul rădăcină mai este numit şi vârf.Într-un nod intră o singură muchie care îl leagă de un alt nod numit părinte sau predecesor.Dintr-un nod pot să iasă niciuna, una sau mai multe muchii care îl leagă de alte noduri numite fii sau succesor.Nodurile fără succesori se numesc frunze sau noduri terminale.Două noduri care descind din acelaşi nod tată se numesc noduri frate.Ordinul unui nod este dat de numărul de descendenţi direcţi.Nodurile sunt organizate pe niveluri. Rădăcina se găseşte pe nivelul 0, descendenţii ei pe nivelul 1, descendenţii acestora pe nivelul 2 etc.Înălţimea unui arbore este dată de numărul maxim dintre nivelurile nodurilor terminale(este egală cu lungimea celui mai lung lanţ de la rădăcină până la un vârf terminal).

Exemplu:Rădăcinile arborilor A1, A2, A3 sunt în ordine 5, 2, 1.Predecesorul nodului 4 din A3 este 2.Succesorii lui 5 din A1 sunt 1, 6, 4.Nodurile 5, 7, 1 , 4 sunt frunze în A2.Ordinul nodului 2 în A3 este 2.Toţi arborii din figura 12 au înălţimea 2.

Teoreme:1. Orice arbore cu n noduri are (n-1) muchii.2. Un arbore binar strict care are n noduri terminale are în total (2*n-1) noduri.3. Un arbore binar complet care are n noduri terminale are în total (2*n-1) noduri.

Vectorul de taţi

Este o modalitate de reprezentare a arborilor cu ajutorul unui tablou unidimensional definit după cum urmează:

t i={ 0 , i este radacina

x , x predecesorul lui i

Page 12: teorie grafuri

8

6

2

1

3

GT1

5

7

Exemplu:

Vectorii de taţi ai arborilor din figura 12 sunt în ordine:T1=(5,4,4,5,0,5)T2=(6,0,2,6,3,2,3)T3=(0,1,5,2,1,2)

12. 2 Algoritmi de prelucrare a grafurilor

Parcurgerea în lăţime BFAlgoritmul se poate aplica atât grafurilor neorientate caz în care se obţine componenta conexă a nodului de plecare cât şi grafurilor orientate caz în care se obţine lista nodurilor accesibile prin drum din vârful de plecare.Algoritmul utilizează matricea de adiacenţă, o coadă şi un vector viz de dimensiune egala cu numărul de noduri ale grafului prelucrat iniţializat cu 0. Fiecare nod ce va fi adăugat în coadă este marcat în vectorul viz cu valoarea 1. Se porneşte parcurgerea de la orice nod al grafului G, nod ce este adăugat în coada iniţial vidă. Se adaugă în coadă toţi vecinii/succesorii primului vârf. Pentru fiecare vârf adăugat se repetă procedeul: se adaugă în coadă vecinii/succesorii nevizitaţi. Parcurgerea se opreşte atunci când sau prelucrat toate vârfurile ce au fost adăugate în coadă.În cazul grafurilor neorientate dacă graful este conex se obţine o coadă ce memoreaza toate nodurile din graf.

Exemplu:Presupunem nod de start pentru GT1 vârful 1

Paşii parcurgerii Noduri adăugateVizităm nodul de start 1 1Vizităm vecinii lui 1 2,5Pentru 2 şi 5 vizităm adiacenţii nevizitaţi încă

Vecinii lui 2 sunt 5 zi 7, nevizitat 7 Vecinii lui 5 sunt 1,2,7, existenţi deja

în coadă7

nu se adaugă nimicSe vizitează adiacenţii lui 7 care sunt 2,5,3,6 3,6Se vizitează adiacenţii lui 3 nu se adaugă nimicSe vizitează vecinii lui 6 8Se vizitează 8 nu se adaugă nimic

Se finalizează parcurgerea

Presupunem nod de start pentru graful GT2 vârful 7

Page 13: teorie grafuri

2

6

8

1

3

GT2

5

7

Paşii parcurgerii Noduri adăugateVizităm nodul de start 7 7Vizităm succesorii lui 7 3,5

Paşii parcurgerii Noduri adăugatePentru 3 şi 5 vizităm succesorii nevizitaţi încă

3 nu are succesori Succesorii lui 5 sunt 1 şi 8

nu se adaugă nimic1,8

Se vizitează succesorul 8 al lui 1 nu se adaugă nimic8 îl are ca succesor pe 3 vizitat anterior nu se adaugă nimic

Se finalizează parcurgerea

Să urmărim „evoluţia” cozii pentru graful GT1 de mai sus; capetele se identifică prin p şi u(poziţia primului respectiv ultimului element) :

pu1

p u1 2 5

p u1 2 5 7

pu

1 2 5 7p u

1 2 5 7 3 6pu

1 2 5 7 3 6pu

1 2 3 7 3 6 8

Algoritmul BF:Matricea de adiacenţă a şi numărul de vârfuri n sunt declarate ca variabile globale.

Implementare C++ Implementare Pascal

void BFS(int S, int c[ ]) /* S = nodul start. c – coada */{ int i, x, y,p,u,viz[MAX_N];/*MAX_N constantă – numărul maxim de noduri*/ p = u = 0; // initializare coada for(i=0;i<=n;i++) viz[i]=0; //nici un nod vizitat c[p] = S; /* se introduce nodul start in coada */ viz[S]=1;/*se marcheaza ca vizitat nodul S*/ while(p<=u) /* cat timp coada este nevida*/ {x = c[p++]; /* extrag un element din

procedure BFS(S:integer; var c:vector);var i, x, y, p, u; viz:vector;begin p:=1; u:=1; for i:=1 to n do viz[i]:=0;c[p]=S;viz[S]:=1;while p<=u do begin x=c[p];

Page 14: teorie grafuri

1

2

53

4

GT1

6

4

2 1

3

GT2

coada*/ for(y = 1; y<=n; y++) // se cauta adiacentii/succesorii if(a[x][y] && !viz[y]) /* daca am muchia (x,y) si y nu a fost vizitat*/

{viz[y] =1; //vizitez y c[++u] = y; /* se introduce y in coada*/}

}}

inc(p); for y:=1 to n do if (a[x, y]=1) and (viz[y]=0) then begin viz[y]=1; inc(u); c[u]=y; end; end;end;

Dacă se doreşte aflarea componentelor conexe vectorul viz se iniţializează cu 0 în afara funcţiei BFS. Funcţia BFS se apelează pentru fiecare vârf rămas nevizitat după parcurgerile anterioare.Pentru a obţine în cazul grafurilor orientate componentele conexe se modifică condiţia din instrucţiunea IF astfel:

(a[x][y] || a[y][x]) && !viz[y] //implementare C++ ((a[x, y]=1) or (a[y,x]=1)) and (viz[y]=0) {implementare Pascal}

Algoritmul Roy-WarshallEste un algoritm ce prelucrează matricea de adiacenţă a grafurilor transformând matricea iniţială în matricea lanţurilor/drumurilor în urma unor prelucrări succesive conform următorului principiu: există lanţ/drum de la i la j dacă există (i, j) muchie în graf sau există k aşa încât există lanţ/drum de la i la k şi de la k la j. Un element aij

devine 1 dacă există k aşa încât aik=1 şi akj=1.

Exemplu:Pentru graful GT1 matricea de adiacenţă evolueaza de la forma la

Pentru graful GT2 matricea de adiacenţă evoluează în patru etape astfel:

Matricea de adiacenţă a şi numărul de vârfuri n sunt declarate ca variabile globale.

Implementare C++ Implementare Pascal

void roy_warshall(int md[][100])/*md matricea lanturilor drumurilor*/

procedure roy_warshall (var md:matrice);var i:integer;

0 0 1 1 0 10 0 1 1 0 01 1 0 0 0 01 1 0 0 0 00 0 0 0 0 01 0 0 0 0 0

1 1 1 1 0 11 1 1 1 0 11 1 1 1 0 11 1 1 1 0 10 0 0 0 0 01 1 1 1 0 1

0 1 1 0 0 1 1 0 0 1 1 1 1 1 1 1

0 0 1 1 ... 0 0 1 1...

0 0 1 1 ... 1 1 1 1

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 01 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1

Page 15: teorie grafuri

{ int i,j,k; for(i=1;i<=n;i++) for(j=1;j<=n;j++) md[i][j]=a[i][j];/*se copie elementele din a in md; se poate prelucra si direct a dar se pierde matricea de adiacenta*/ for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(md[i][j]= =0 && i!=k && j!=k) md[i][j]=md[i][k]*md[k][j];}

j:integer; k:integer;begin for i:=1 to n do for j:=1 to n do md[i,j]:=a[i,j];

for k:=1 to n do for i:=1 to n do for j:=1 to n do if((md[i,j]=0) and (i<>k) and (j<>k)) then md[i,j]:=md[i,k]*md[k,j];end;

Algoritmul se poate utiliza şi pentru determinarea componentelor conexe/tare conexe. În cazul grafurilor neorientate dacă mdlj=1atunci j este în componenta conexă ce îl conţine pe l. Pentru grafurile orientate dacă mdlj=mdjl=1 atunci j este în aceeaşi componentă tare conexă cu l.

Algoritmul Roy-Floyd

Fie f :U →ℜ , unde U este mulţimea muchiilor/arcelor unui graf numită funcţie de cost sau pondere. Valorile funcţiei de cost pot reprezenta costurile de deplasare între două punce dacă graful memorează o reţea stradală, timpul de transfer al pachetelor de date într-o reţea de calculatoare între două noduri ale reţelei sau costurile de producţie pentru a trece un produs dintr-o fază de prelucrare în alta. Un graf G ce are asociată o astfel de funcţie se numeşte graf ponderat.Se defineşte matricea costurilor astfel:

mc ij={ 0 , daca i= j

f (( i , j)) , daca ( i , j)∈U

±∞ , daca ( i , j)∉U

Algoritmul Roy-Floyd utilizat pentru a afla costul lanţurilor/drumurilor minime/

maxime într-un graf sau lungimea lor dacă f (m)=1 ,∀m∈U . Este asemenător cu Roy-Warshall folosind următoarea idee: dacă există k aşa încât drumul minim/maxim de la un vârf i la un vârf j are un cost mai mare/mai mic decât decât suma costurilor drumurilor de la i la k însumat cu costul drumului de la k la j atunci mcij=mcik+mckj. În implementare valoarea ±∞ se înlocuieşte cu o constantă predefinită(ex: ±MAXINT, ±MAXLONG) sau definită în program.Matricea costurilor mc şi numărul de vârfuri n sunt declarate ca variabile globale. Uzual graful se memorează prin intermediul unui vector de înregistrări ce memorează extremităţile muchiilor şi ponderea lor matricea mc construindu-se pe baza informaţiilor din vector.

Implementare C++ Implementare Pascal

void roy_floyd( ){ int i,j,k;

procedure roy_floyd;var i:integer;

Page 16: teorie grafuri

for(k=1;k<=n;k++) for(i=1;i<=n;i++) for(j=1;j<=n;j++) if(md[i][j]< = md[i][k]+md[k][j]) md[i][j]=md[i][k]+md[k][j];}

j:integer; k:integer;beginfor k:=1 to n do for i:=1 to n do for j:=1 to n do if md[i,j]<=md[i,k]+md[k,j] then md[i,j]:=md[i,k]+md[k,j];end;

Algoritmul DijkstraAlgoritmul utilizează un tablou d, d[i] fiind lungimea celui mai scurt drum de la nodul sursă la nodul i la un moment dat şi un vector viz ce reţine informaţii despre mulţimea nodurilor vizitate. Iniţial, d[i]=mc[sursa,i], viz[i]=0 cu excepţia viz[sursă]=1. Algoritmul se execută în n-1paşi. La fiecare pas se calculează distanţa minimă de la sursă până la un nod nevizitat reţinând valoarea nodului respectiv. Fie x nodul astfel determinat. Nodul x este marcat prin viz[x]=1 şi pe masură ce se găsesc noduri y astfel incat d[y]>d[x]+mc[x,y], d[y] este redus. La terminarea algoritmului, d[i] va contine lungimea drumului minim de la origine la i.

Matricea costurilor mc definită astfel:

mc ij={f (( i , j)) , daca ( i , j)∈U

0 , in rest şi numărul de vârfuri n sunt declarate ca variabile globale.

Implementare C++ Implementare Pascal

void dijkstra(int S){ int d[MAX_N], i, j; int viz[MAX_N]; /* viz[i] = daca a fost vizitat sau nu*/for(i=1;i<=n;i++) {viz[i]=0; d[i]=mc[S][i]?mc[S][i]:inf;}viz[S] = 1;int min, pmin = 0;for ( i = 1; i <= n-1; i++ ) {min = inf;//constanta predefinita for (j = 1; j <= n; j++) //extrag minimul din d[] if ( d[j] < min && !viz[j] ) {min = d[j]; pmin = j; } viz[pmin] = 1; for(j = 1; j<=n; j++) /* actualizez drumul pana la vecinii minimului*/ if(mc[pmin][j]) /* daca am muchie (pmin,j), de cost mc[pmin][j]*/

procedure dijkstra(S:integer);var d,viz:vector; i,j,min,pmin:integer;begin for i:=1 to n do begin viz[i]:=0; if mc[S,i]<>0 then d[i]:=mc[S,i] else d[i]:=inf; end;viz[S]:=1;for i:=1 to n-1 do begin min:=inf; for j:=1 to n do if ((d[j]<min) and (viz[j]=0)) then begin min:=d[j]; pmin:=j; end; viz[pmin]:=1;

Page 17: teorie grafuri

6

1

2

5

4

3

9

7 8

4

5

3

8 8

3

98

7

9

7

5

842

72

86

3

GT1

{if ( d[ j ] > d[pmin] + mc[pmin][j] ) /* daca pot ajunge in j pe un drum mai bun*/ d[ j ] = d[pmin] + mc[pmin][j]; } }cout<<"Dijkstra : Distantele de la noul sursa ”<<S<<” la varfurile grafului, in ordine, sunt: ";for(i=1;i<=n;i++) cout<<d[i];}

for j:=1 to n do if mc[pmin,j]<>0 then if d[j]>d[pmin]+mc[pmin,j] then d[j]:=d[pmin]+mc[pmin,j]; end;write(‘Dijkstra : Distantele de la noul sursa ‘,S,’ la varfurile grafului, in ordine, sunt:’);for i:=1 to n do write(d[i],’ ‘);end;

Exemplu:Pentru graful GT1 alăturat evoluţia vectorilor d şi viz este următoarea (considerăm 1 nod sursă):

d 0 4 ∞ ∞ ∞ 3 ∞ ∞ 5viz 1 0 0 0 0 0 0 0 0pmin=6;min=3d 0 4 ∞ ∞ ∞ 3 8 ∞ 5v 1 0 0 0 0 1 0 0 0pmin=2;min=4d 0 4 11 13 ∞ 3 8 ∞ 5v 1 1 0 0 0 1 0 0 0pmin=9;min=5d 0 4 7 12 8 3 7 ∞ 5v 1 1 0 0 0 1 0 0 1pmin=3;min=7d 0 4 7 12 8 3 7 16 5v 1 1 1 0 0 1 0 0 1pmin=7;min=7d 0 4 7 12 8 3 7 15 5v 1 1 1 0 0 1 1 0 1

La următorii paşi pmin va lua valorile 5,4,8 dar nu se mai produc modificări asupra vectorului d. Configuraţia finală a lui d este cea obţinută după prelucrarea cu pmin=7.

Algoritmul lui PrimEste un algoritm care returneaza un arbore de acoperire minim pentru un graf ponderat. Un arbore de acoperire de cost minim este un subgraf alcătuit din toate nodurile grafului iniţial dar nu din toate arcele, ci doar din atâtea arce cât să nu apară cicluri iar costul total al muchiilor alese este minim.Algoritmul poate fi stilizat astfel:

Iniţial, toate nodurile grafului se consideră nevizitate Se porneşte de la un nod oarecare al grafului care se marchează ca vizitat În permanenţă vor fi menţinute două mulţimi:

o Mulţimea V a nodurilor vizitate (iniţial, V va contine doar nodul de start)

o Mulţimea X\V a nodurilor nevizitate (X este mulţimea tuturor nodurilor)

Page 18: teorie grafuri

La fiecare pas se alege acel nod din mulţimea X\V care este legat prin arc de cost minim de oricare din nodurile din mulţimea V

Nodul ales va fi scos din multimea X\V şi trecut în mulţimea V Algoritmul continua pana cand V = X(sau la alegerea a n-1 muchii, unde n este

cardinalul lui X)În implementare se utilizează matricea costurilor definită după modelul următor:

mc ij={f (( i , j)) , daca ( i , j)∈U

0 , in rest unde f este funcţia de cost asociată grafului şi doi vectori: s ce reţine vârfurile selectate şi t ce memorează vectorul de taţi al arborelui parţial de cost minim. Matricea şi cele două tablouri sunt utilizate în implementare ca variabile globale.

Implementare C++ Implementare Pascal

void prim( ){ int rad,i,j,min;cout<<”radacina:”cin>>rad;/*se poate introduce orice nod*/for(i=1;i<=n;i++) s[i]=rad;s[rad]=0;for(i=1;i<=n;i++) t[i]=0;/*se initializeaza vectorii t si s*/cost=0; //costul total;variabila globalafor(k=1;k<=n-1;k++)//se aleg n-1 muchii{min=inf; for(i=1;i<=n;i++) if (s[i]) if(mc[s[i]][i]<min && mc[s[i]][i]) {min=mc[s[i]][i]; j=i; }/*se calculeaza in min costul minim al unei muchii cu un capat ales; j extremitatea nemarcata a muchiei alese*/ t[j]=s[j];/*se marcheaza predecesorul lui j*/ cost+=mc[j][s[j]];//actualizare cost s[j]=0;//se marcheaza varful ales for(i=1;i<=n;i++) if (s[i]) if (!mc[i][s[i]] || mc[i][s[i]]>mc[i][j]) if (mc[i][j]) s[i]=j;/*se actualizeaza s pentru alegerile viitoare*/ }}

procedure prim;var rad,i,j,min:integer;beginwrite(‘radacina:’);readln(rad); for i:=1 to n do s[i]:=rad;s[rad]:=0;for i:=1 to n do t[i]:=0;cost:=0;for k:=1 to n-1 do begin min:=inf; for i:=1 to n do if (s[i]<>0) then if (mc[s[i],i]<min)and(mc[s[i],i]<>0) then begin min:=mc[s[i],i]; j:=i; end; t[j]:=s[j]; cost:=cost+mc[j,s[j]]; s[j]:=0; for i:=1 to n do if (s[i]<>0) then if (mc[i,s[i]]=0)or(mc[i,s[i]]>mc[i,j]) then if mc[i,j]<>0 then s[i]:=j; end;end;

Page 19: teorie grafuri

3

1

2

4

7

5

6 8

2

9

4

3

22

1

4

7

GT1

3

5

6

Exemplu:Pentru graful alăturat evoluţia tablourilor s şi t considerând rădăcină nodul 1 este următoarea:

s 0 1 1 1 1 1 1 1t 0 0 0 0 0 0 0 0min=2;j=2; se alege muchia (1,2)s 0 0 1 1 2 1 1 1t 0 1 0 0 0 0 0 0min=3;j=4; se alege muchia (1,4)s 0 0 1 0 2 1 4 4t 0 1 0 1 0 0 0 0min=1;j=8; se alege muchia (4,8) s 0 0 1 0 2 8 4 0t 0 1 0 1 0 0 0 4min=2;j=7; se alege muchia (4,7)s 0 0 1 0 2 8 0 0t 0 1 0 1 0 0 4 4min=4;j=5; se alege muchia (2,5)s 0 0 5 0 0 8 0 0t 0 1 0 1 2 0 4 4

12. 3 Teste grilă

Bacalaureat 2007

Varianta 11. Se consideră un graf neorientat cu nodurile 1, 2, 3, 4, 5, 6, 7, 8 şi muchiile: [1,3] ,[1,7], [2,6], [3,7], [5,2], [5,6], [8,4]. Câte componente conexe are graful?

a. 2 b. 3 c. 8 d. 12. Care dintre următoarele matrice este matricea de adiacentă a unui arbore cu 4 noduri?

a. 0 1 0 1 b. 0 0 1 0 c. 0 1 1 1 d. 0 0 1 00 0 1 0 0 0 0 1 1 0 1 0 0 0 0 11 0 0 0 1 0 0 0 1 1 0 0 1 0 0 11 0 1 0 0 1 0 0 1 0 0 0 0 1 1 0

Varianta 23. Se consideră un graf orientat cu 6 noduri numerotate cu 1, 2, .. . , 6 şi cu mulţimea arcelor formată doar din arcele: • de la fiecare nod numerotat cu un număr neprim i (i>1) la toate nodurile numerotate cu numere ce aparţin mulţimii divizorilor proprii ai lui i (divizori diferii de 1 şi de i); • de la nodul numerotat cu 1la nodul numerotat cu 2; • de la fiecare nod numerotat cu un număr prim i la nodul numerotat cu i+1. Stabiliţi care este numărul de circuite elementare distincte conţinute de graful din enunţ. (Două circuite sunt distincte dacă diferă prin cel puţin un arc).

a. 1 b. 2 c. 3 d. 0

min=4;j=6; se alege muchia (6,8)

s 0 0 6 0 0 0 0 0

t 0 1 0 1 2 8 4 4

min=3;j=3; se alege muchia (3,6)

s 0 0 0 0 0 0 0 0

t 0 1 6 1 2 8 4 4

Page 20: teorie grafuri

4. Câte grafuri orientate, distincte, cu 4 vârfuri se pot construi? Două grafuri se consideră distincte dacă matricele lor de adiacenţă sunt diferite. a.4 b.26 c.64 d.4

a. 46 b. 26 c. 64 d. 4 Varianta 35. Se consideră un graf orientat cu 6 noduri numerotate cu 1, 2, . . . , 6 şi cu mulţimea arcelor formată doar din arcele: • de la fiecare nod numerotat cu număr neprim i (i>1) la toate nodurile numerotate cu numere ce aparţin mulţimii divizorilor proprii ai lui i (vizori diferiţi de 1 i i); • de la nodul numerotat cu 1 la nodul numerotat cu 2; • de la fiecare nod numerotat cu un număr prim i la nodul numerotat cu i+1. Stabiliţi câte noduri din graf au suma dintre gradul intern şi cel extern egală cu 3.

a. 1 b. 6 c. 2 d. 0

6. Se consideră un graf neorientat dat prin matricea de adiacenţă alăturată. Câte cicluri elementare distincte şi de lungime 3 există în graful din enunţ? (Două cicluri elementare sunt distincte dacă diferă prin cel puţin o muchie).

Varianta 47. Se consideră un graf neorientat cu nodurile: 1,2,3,4,5,6,7,8 şi muchiile: [1,3], [1,7], [2,6], [3,7] , [5,2], [5,6], [8,4]. Care este numărul minim de muchii ce pot fi adăugate astfel încât graful să devină conex?

a. 2 b. 0 c. 3 d. 48. Un graf orientat are 8 arce şi fiecare nod al grafului are gradul interior un număr nenul. Doar două dintre noduri au gradul interior un număr par, restul nodurilor având gradele interioare numere impare. Care este numărul maxim de noduri pe care poate să le aibă graful?

a. 7 b. 8 c. 5 d. 6

Varianta 59. Un graf orientat are 8 arce şi fiecare nod al grafului are gradul exterior un număr nenul. Doar două dintre noduri gradul exterior un număr impar, restul având gradele exterioare numere pare. Care este numărul maxim de noduri pe care le poate avea graful?

a. 4 b. 8 c. 3 d. 510. Se consideră un graf neorientat cu nodurile: 1,2,3,4,5,6,7,8 şi muchiile [1,2], [1,5], [2,8], [3,7], [4,5], [5,7], [6,4], [7,6], [8,3], [8,7]. Care este numărul minim de muchii ce pot fi eliminate astfel încât graful obţinut să aibă trei componente conexe?

a. 3 b. 4 c. 2 d. 5

Varianta 6

0 0 1 0 0 0 0 00 0 0 1 1 1 1 11 0 0 0 0 0 0 00 1 0 0 0 0 0 00 1 0 0 0 0 0 00 1 0 0 0 0 0 00 1 0 0 0 0 0 00 1 0 0 0 0 0 0a. 4 b. 0

c. 2 d. 3

Page 21: teorie grafuri

11. Care este numărul maxim de muchii pe care le poate avea un graf neorientat eulerian cu 10 noduri?

a. 10 b. 50 c. 40 d. 45

12. Câte dintre nodurile grafului orientat cu 6 noduri şi cu matricea de adiacenţă alăturată au gradul interior egal cu gradul exterior?

Varianta 713. Considerăm un arbore G cu 7 noduri care are matricea de adiacenţă alăturată. Stabiţi care dintre următorii vectori este un vector de taţi al arborelui dat:

14. Se consideră un graf neorientat G cu 5 noduri dat prin matricea de adiacenţă alăturată. Stabiliţi care dintre următoarele propoziţii este adevărată:

a. este graf hamiltonian şi graf eulerian b. G este graf hamiltonian, dar nu este graf eulerian c. G nu este nici graf hamiltonian, nici graf eulerian d. G nu este graf hamiltonian, dar este graf eulerian

Varianta 815. Considerând graful orientat G cu 6 noduri reprezentat prin intermediul listelor de adiacenţă alăturate, stabiliţi câte dintre vârfurile sale au gradul intern egal cu gradul extern:

1: 52: -3: 2 4 4: 2 3 5: 2 4 6: 1 2 3 4 5 a. 4 b. 1 c. 3 d. 2

16. Fie G un graf neorientat conex cu 20 de noduri şi 99 de muchii. Numărul maxim de muchii ce pot fi eliminate astfel încât graful să rămână conex este:

a. 50 b. 80 c. 79 d. 8117. Fie G = (V. E) un arbore în care V = { 1, 2, … , n}. Ştiind că şi G’ = (V U {n+ 1}, E’) este deasemenea un arbore, stabiliţi care dintre următoarele propoziţii este adevărată (notaţia |M| reprezintă numărul elementelor unei mulţimi M):

0 1 0 0 0 01 0 1 0 0 10 0 0 1 0 10 1 1 0 1 00 0 0 1 0 11 0 1 1 0 0

a. 2 b. 1c. 4 d. 3

a. (0, 1, 1, 1, 3, 5, 5) b. (0, 1, 3, 1, 1, 5, 5)c. (0, 1, 5, 5, 3, 3, 5) d. (0, 1, 1, 1, 5, 3, 3)

0 1 1 1 0 0 01 0 0 0 0 0 01 0 0 0 1 0 01 0 0 0 0 0 00 0 1 0 0 1 10 0 0 0 1 0 00 0 0 0 1 0 0

0 1 0 0 11 0 1 1 10 1 0 1 00 1 1 0 01 1 0 0 0

Page 22: teorie grafuri

2

3

46 7

15

a. |E’| = |E| b. |E’| = |E| + l c. |E’| = |E| -l d. |E’| = |E| + 2Varianta 918. Fie graful orientat G = (V. E) unde mulţimea nodurilor este V = {1, 2, 3, 4, 5, 6, 7), iar mulţimea arcelor este E = {[1, 2] , [1, 6], [2, 5], [2, 6], [3, 4], [4, 3], [6, 2], [6, 5], [3, 7], [4, 7]}. Numărul nodurilor grafului G care au gradul exterior egal cu 0 este:

a. 1 b. 3 c. 0 d. 219. Fie G un graf neorientat conex cu 100 de noduri şi 2007 muchii. Numărul de muchii care trebuie eliminate din G astfel încât acesta să devină arbore este:

a. 1237 b. 1907 c. 1007 d. 190820. Fie G = (V, E) un graf neorientat în care mulţimea nodurilor este V ={1, 2, ..., 20}, iar mulţimea muchiilor este E ={ (i, j) ∈ VxV | i mod 3 = j mod 3} (prin a mod b am notat restul împărţirii lui a la b). Numărul componentelor conexe ale grafului G este:

a. 4 b. 3 c. 2 d. 1

Varianta 1021. Fie arborele G = (V, E) în care mulţimea vârfurilor este V ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, iar mulţimea muchiilor este E ={ [1, 3], [1, 4], [2, 1], [2, 5], [3, 7] , [4, 8], [4,9] [5, 6] , [9, l0]}.Considerând vârful 1 rădăcina arborelui, vectorul de taţi corespunzător arborelui G este:

22. Fie G = (V, E) un graf orientat în care mulţimea nodurilor este V ={1, 2, ..., 10}, iar mulţimea arcelor este E ={ (i, j ) ∈ VxV | i ≠ j şi j mod i=0} (prin a mod b am notat restul împărţirii lui a la b).Stabiliţi care dintre următoarele afirmaţii este adevărată:

a. Pentru oricare pereche de noduri i şi j (i ≠ j) exista cel puţin un drum de la i la j şi cel puţin un drum de la j la i b. pentru orice nod al grafului G suma dintre gradul interior şi gradul exterior este nenulă c. toate vârfurile grafului G au gradul interior egal cu gradul exterior d. graful G conţine circuite

Varianta 1123. Pentru arborele cu rădăcină din figura alăturată vectorul de „taţi” este:

a. 0 5 7 4 0 1 3b. 0 5 7 0 4 3 3c. 2 0 2 5 5 3 3d. 2 0 2 5 2 3 3

a. T = (0, 1, 1, 3, 1, 5, 3, 4, 9, 4) b. T = (0, 1, 1, 1, 3, 5, 3, 4, 4, 4)c. T = (0, 1, 1, 1, 5, 2, 4, 3, 4, 9) d. T = (0, 1, 1, 1, 2, 5, 3, 4, 4, 9)

Page 23: teorie grafuri

24. Se consideră graful orientat dat prin matricea de adiacenţă alăturată. Care este lungimea maximă a unui drum elementar de la vârful 1 până la vârful 5?

Varianta 1225. Pentru care dintre următorii arbori cu rădăcină, memoraţi cu ajutorul vectorilor de taţi, nodurile 4, 6 şi 9 sunt singurii descendenţi direcţi ai nodului 3?

26. Un graf orientat este reprezentat prin matricea de adiacenţă dată alăturat. Precizaţi care sunt nodurile pentru care gradul interior este mai mare decât gradul exterior.

a. 2, 4, 5b. 2, 4, 5, 6c. 1, 4, 5d. 1, 3, 6

27. Într-un arbore binar (un arbore binar este un arbore în care fiecare nod are cel mult doi descendenţi direcţi), un lanţ care uneşte rădăcina cu oricare din nodurile frunză, conţine cel mult n - 1 muchii. Care este numărul maxim de noduri dintr-un astfel de arbore?

a. 2 n - 1 b. n c. 2n d. 2 n – 1

Varianta 13

28. Se consideră un graf neorientat cu 9 noduri şi muchiile [1, 5], [1, 7], [1, 8], [1, 9], [2, 6], [3, 4], [3, 7], [3, 8], [4, 7], [4, 9], [5, 8], [7, 9]. Pentru acest graf numărul de cicluri distincte de lungime 3 este:

a. 6 b. 24 c. 10 d. 429. Se consideră arborele cu rădăcină dat prin vectorul de taţi t = (5, 7, 5, 7 , 7, 9, 0, 9, 4, 3, 5, 11, 4, 4, 4). Câte lanţuri elementare de lungime 2, care pornesc din rădăcină există?

a. 7 b. 11 c. 4 d. 1430. Care dintre următoarele grafuri este un graf eulerian, dar nu este hamiltonian? Grafurile sunt precizate prin numărul n de noduri şi mulţimea U a muchiilor.

a. n = 3, U = {[1, 2], [1, 3], [2, 3]} b. n = 4, U ={ [1, 2], [1, 3] , [1, 4], [2, 3], [2, 4], [3, 4] }c. n = 5, U = { [1, 3], [1, 4] , [3, 4], [2, 4] , [4, 5], [2, 5] } d. nici unul din grafurile anterioare.Varianta 1431. Care este numărul maxim de componente conexe pe care le poate avea un graf neorientat cu 6 noduri şi 5 muchii?

a. 4 b. 2 c. 1 d. 3

0 1 1 0 0 00 0 0 1 1 10 0 0 0 0 00 0 1 0 0 10 0 1 0 0 00 1 0 0 1 0a. 4 b. 3 c. 1 d. 2

a. tata = (3, 3, 4, 0, 2, 3, 4, 4, 4) b. tata = (6, 4, 9, 0, 3, 3, 3, 3, 3)c. tata = (2, 0, 2, 3, 2, 3, 4, 4, 3) d. tata = (0, 3, 1, 3, 2, 3, 4, 4, 3)

0 1 1 0 0 00 0 1 1 0 11 1 0 1 0 00 0 0 0 1 00 1 0 0 0 00 1 0 0 1 0

Page 24: teorie grafuri

32. Care dintre următorii vectori poate reprezenta vectorul de taţi al unui arbore cu rădăcină?

33. Fie graful orientat cu 5 vârfuri şi următoarele arce: [1, 2] , [1, 4], [3, 1], [3, 2], [4,5], [4, 2], [5, 1]. Câte circuite conţine acest graf?

a. 3 b. 4 c. 2 d. 1

Varianta 1534. Fie graful neorientat cu 5 noduri şi cu următoarele muchii: [1, 2], [1, 3], [3, 4], [3,5], [4, 5]. Care este numărul minim de muchii ce trebuie adăugate grafului astfel încât, în graful obţinut toate nodurile să aibă acelaşi grad?

35. Se consideră arborele cu 14 noduri având următoarele muchii: [3, 4], [4, 14], [14,13], [4, 5], [1, 5], [5, 7] , [2, 7] , [6, 7] , [6, 9] , [8, 9] , [9, 12] , [11, 12], [10,12]. Care dintre vectorii următori reprezintă vectorul de taţi al arborelui dat? a. (5, 7, 4, 5, 0, 7, 5, 9, 6, 12, 12, 11, 14, 4) b. (5, 7, 4, 0, 4, 7, 5, 9, 6, 0, 12, 9, 14, 4)c. (0, 7, 4, 5, 1, 7, 5, 9, 6, 11, 12, 9, 14, 4) d. (5, 7, 4, 5, 7, 9, 6, 9, 12, 12, 12, 0, 14, 4)

36. Numărul de grafuri orientate cu n vârfuri este:

a. 2 n b. 2 n(n-1)

c. 2

n(n−1 )2 d. 2n

Varianta 1637. Un graf neorientat cu n noduri, cu n număr impar mai mare decât 2, în care fiecare nod are gradul n - 1, este întotdeauna:

38.

Lungimea unui drum elementar într-un graf orientat cu n vârfuri poate fi:

Varianta 1739. Un graf neorientat este eulerian dacă: a. este conex şi conţine cel puţin un ciclu elementar. b. conţine un singur ciclu elementar. c. este conex şi suma elementelor de pe fiecare coloană a matricei de adiacenţă este număr par. d. conţine cel puţin un ciclu hamiltonian40. Care este gradul maxim posibil al unui nod dintr-un arbore cu n noduri?

Varianta 18

a. (5, 7, 1, 1, 0, 7, 7, 12, 1, 12, 4, 7) b. (5, 7, 1, 1, 0, 7, 0, 12, 1, 12, 4, 7)c. (5, 7, 1, 1, 0, 7, 5, 12, 1, 12, 4, 7) d. (0, 7, 1, 1, 8, 7, 5, 12, 1, 12, 4, 7)

a. 4 b. 5 c. 6 d. 3

a. graf acidic (graf care nu conţine nici un ciclu) b. arbore c. graf neconex d. graf eulerian

a. ∞ b. n + 1 c. n d. n – 1

a. n - 1 b. n / 2 c. 2 d. n

Page 25: teorie grafuri

41. Suma gradelor interne ale tuturor vârfurilor unui graf orientat este întotdeauna egală cu: a. numărul valorilor de 1 aflate sub diagonala principală în matricea de adiacenţă b. suma tuturor valorilor aflate deasupra diagonalei principale în matricea de adiacenţă c. produsul gradelor externe ale tuturor vârfurilor grafului d. suma gradelor externe ale tuturor vârfurilor grafului

42. Care este numărul minim de muchii care pot fi eliminate din graful neorientat, dat prin listele de adiacenţă alăturate, astfel încât graful să devină eulerian?

1: (2, 3, 5) a. 12: (1, 4) b. 23: (1, 4, 5) c. 34: (2, 3, 5) d. 05: (1, 3, 4)

Varianta 1943. Graful neorientat reprezentat pun listele de adiacenţă alăturate se transformă în graf orientat astfel: fiecare muchie [i, j], cu i<j, devine arcul (i, j). În graful orientat astfel obţinut lungimea celui mai scurt drum de la vârful 1 la vârful 5 este:

1: (2, 3) a. 42: (1, 3, 5) b. 13: (1, 2, 4) c. 24: (3, 5) d. 35: (2, 4)

44. Într-un arbore cu exact 8 noduri rădăcina, reprezentată de nodul 1, se află pe nivelul 1 şi fiecare nod al arborelui are cel mult 2 descendenţi direcţi. Care este înălţimea minimă posibilă pentru un astfel de arbore? (Înălţimea unui arbore = numărul maxim de muchii de la rădăcină la un vârf terminal)

Varianta 2045. Într-un graf neorientat cu 6 noduri oricare două noduri x, y sunt adiacente dacă şi numai dacă x%2 = = y%2. Care este numărul de componente conexe din graf?

46. Un graf neorientat este graf complet dacă şi numai dacă oricare două noduri sunt adiacente. Care este numărul de muchii care trebuie eliminate dintr-un graf neorientat complet cu 8 noduri, astfel încât graful parţial obţinut să fie arbore?

Teste grilă(diverse)

47. Se consideră un graf neorientat cu 6 noduri şi 10 muchii. Care dintre următoarele şiruri de numere pot fi gradele nodurilor grafului ?

a. (2,2,2,2,2,2) b. (2,4,1,3,6,4) c. (4,4,1,3,4,4) d. (2,2,1,1,2,2)

a. 4 b. 3 c. 2 d. 1

a. 1 b. 6 c. 3 d. 2

a. 8 b. 21 c. 16 d. 20

Page 26: teorie grafuri

61

2

5

4

3

51

4

23

62

1 3

48. Se consideră graful neorientat din figura alăturată. Care este numărul minim de muchii care se pot elimina din graf astfel încât graful parţial obţinut să aibă exact 2 componente conexe?

a. 2 b. 6 c. 7 d. 1

49. Se consideră un graf neorientat complet cu 10 noduri . Câte lanţuri elementare de lungime 4 există între nodul 1 şi nodul 4? Lungimea unui lanţ este egală cu numărul de muchii din care este compus lanţul. Două lanţuri sunt distincte dacă diferă prin cel puţin o muchie. Dacă vârfurile unui lanţ sunt distincte două câte două, atunci lanţul se numeşte elementar.

a. 1000 b. 336 c. 50 d. 72

50. Care dintre următoarele afirmaţii este adevărată pentru orice graf neorientat cu 6 noduri şi 7 muchii?

a. graful este conexc. graful are gradele tuturor nodurilor

numere pareb. graful are cel puţin un ciclu d. graful nu poate avea noduri de grad 0

51. Dacă G este un graf neorientat cu 10 noduri şi 12 muchii care este numărul maxim de componente conexe pe care îl poate avea graful ?

a. 10 b. 5 c. 1 d. 2

52. Fie n un număr natural, n>4. Orice graf neorientat cu n noduri şi n muchii :

a. are cel puţin un ciclu c. este aciclic

b. este arbore d. are gradele tuturor nodurilor numere impare

53. Dacă G este un graf neorientat cu 10 noduri şi două componente conexe atunci graful are cel mult:

a. 20 de muchii b. 10 muchii c. 36 de muchii d. 21 de muchii

54. Care este numărul minim de muchii pe care le poate avea un graf neorientat G dacă graful din figura 1 este un subgraf a lui G, iar graful din figura 2 este un graf parţial al lui G?

Page 27: teorie grafuri

1

2 3 4

5

6

789

10

6

1 2

3

45

figura 1 figura 2a. 4 b. 5 c. 6 d. 7

55. Care dintre următoarele afirmaţii referitoare la graful neorientat reprezentat în figura alăturată, este adevărată:

a. numărul nodurilor de grad par este mai mare decât numărul nodurilor de grad impar

c. cel mai mic lanţ elementar are lungimea 8

b. dacă se elimină orice două muchii din graf se obţin două componente conexe

d. graful conţine un singur ciclu

56. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile: (1,2), (1,6), (2,3), (2,5), (3,4), (3,6), (4,5), (5,6).Care este numărul maxim de muchii care pot fi eliminate din graf pentru a obţine un graf parţial care să fie conex?

a. 3 b. 1 c. 5 d. 2

57. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile: (1,2), (1,4), (1,6), (2,4), (3,4), (3,5), (5,6). Care este numărul minim de muchii care pot fi eliminate din graf pentru a obţine un graf parţial care sa nu fie conex?

a. 1 b. 0 c. 3 d. 2

58. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile: (1,2), (1,4), (1,5), (1,6), (2,3), (2,4), (3,4), (4,5). Care dintre următoarele afirmaţii este adevărată pentru acest graf:

a. este hamiltonian c. este complet b. este eulerian d. nu este nici hamiltonian nici eulerian

59. Fie G un graf neorientat cu 6 noduri numerotate de la 1 la 6 dat prin matricea de adiacenţă alăturată. Care dintre următoarele afirmaţii este adevărată referitor la acest graf.

a. este hamiltonianc. are toate gradele nodurilor numere impare

b. este conex d. este arboreCare este numărul minim de noduri ce trebuie eliminate din

graful alăturat astfel încât subgraful obţinut să nu fie conex?

0 1 0 0 0 11 0 0 1 1 00 0 0 1 0 00 1 1 0 0 00 1 0 0 0 11 0 0 0 1 0

Page 28: teorie grafuri

1 2

36

54

a. 0 b. 1 c. 2 d. 3

60. Fie G un graf neorientat cu 6 noduri numerotate de la 1 la 6 dat prin matricea de adiacenţă alăturată. Care este nodul de grad maxim?

a. 4 b. 5 c. 2 d. 3

61. Care este numărul de circuite distincte ale unui graf orientat cu 6 noduri numerotate de la 1 la 6, dat prin matricea de adiacenţă alăturată ? Două circuite sunt distincte dacă diferă prin cel puţin un arc.

a. 0 b. 1 c. 2 d. 3

62. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi 8 arce. Care dintre următoarele şiruri de numere pot reprezenta gradele exterioare ale vârfurilor grafului?a. (1,1,1,1,1,1) b. (0,1,0,6,0,1) c. (1,1,0,2,2,0) d. (3,1,1,1,2,0)

63. Se consideră graful orientat din figura alăturată. Câte dintre vârfurile grafului au gradul exterior egal cu gradul interior?a. 0 b. 1 c. 2 d. 3

64. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,3), (1,5), (1,6), (2,4), (3,2), (5,4), (5,6), (6,2). Care este vârful accesibil din toate celelalte vârfuri ale grafului prin intremediul unor drumuri elementare?

a. 3 b. 4 c. 5 d. 2

65. Se consideră un graf orientat G cu n vârfuri numerotate de la 1 la n reprezentat prin matricea de adiacenţă. Suma valorilor de pe o coloană oarecare x a matricei are semnificaţia:

a. numărul arcelor care au ca extremitate finală vârful x

c. numărul drumurilor elementare ce conţin vârful x

b. numărul arcelor care au ca extremitate iniţială vârful x

d. numărul drumurilor elementare ce pornesc din vârful x

0 0 0 1 1 10 0 1 0 1 00 1 0 0 1 01 0 0 0 0 01 1 1 0 0 11 0 0 0 1 0

0 1 0 0 0 00 0 1 0 1 01 0 0 1 0 00 0 0 0 0 00 0 1 1 0 11 0 0 0 0 0

Page 29: teorie grafuri

4 2 5

1 3 6 7

1

2 3

54 6 7

66. Se consideră un graf orientat G cu 6 vârfuri numerotate de la 1 la 6 dat prin matricea de adiacenţă alăturată. Câte dintre vârfurile grafului au proprietate că diferenţa absolută a gradelor intern şi extern este egală cu 2 ?

a. 0 b. 1 c. 2 d. 3

67. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,4), (1,5), (2,5), (3,1), (3,4), (5,4), (5,3), (6,1), (6,2). Câte vârfuri ale grafului au gradul interior egal cu gradul exterior?

a. 2 b. 5 c. 1 d. 3

68. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,2), (1,4), (1,6), (2,5), (3,2), (4,1), (4,3). Care este lungimea maximă a unui drum de la nodul 1 la nodul 5 format doar din arce distincte?

a. 6 b. 2 c. 1 d. 5

69. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele (1,3), (1,5), (2,1), (2,4), (3,2), (4,3), (5,3), (5,4), (6,1), (6,5). Câte vârfuri ale grafului au gradul extern număr impar?

a. 2 b. 4 c. 1 d. 0

70. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele (1,3), (1,5), (2,1), (2,4), (3,2), (4,3), (5,3), (5,4), (6,1), (6,5). Care dintre următoarele vârfuri au gradul extern egal cu gradul intern?

71. Câte dintre nodurile arborelui din figura alăturată pot fi considerate ca fiind rădăcină astfel încât fiecare nod să aibă cel mult doi descendenţi direcţi (fii)?

a. 4 b. 2 c. 5 d. 1

72. Se consideră un arbore G, cu rădăcină cu 7 noduri, numerotate de la 1 la 7, memorat cu ajutorul vectorului de taţi T=(3,1,0,1,1,4,4). Care din următoarele afirmaţii este adevărată?

a. G este conex şi prin adăugarea unei muchii oarecare la G, graful obţinut nu mai este conex

c. nodurile 2,4, şi 5 sunt noduri fraţi

b. nodul 1 este nodul rădăcină d. arborele G are 5 frunze

73. Care este vectorul „de taţi” asociat arborelui cu rădăcină din figura alăturată ?

a. 2 şi 6 b. 1 şi 5 c. 3 şi 5 d. 1 şi 4

Page 30: teorie grafuri

74. Se consideră un arbore cu rădăcină

cu 10 noduri numerotate de la 1 la 10. Care poate fi vectorul de taţi ai acestui arbore ştiind că nodurile 1,2,3,…,9 au exact cate un descendent direct?

a. (1,2,3,4,5,6,7,8,9) c. (0,1,2,3,4,5,6,7,8,9,10)b. (1,2,3,4,5,6,7,8,9,10) d. (0,1,2,3,4,5,6,7,8,9)

75. Se consideră un arbore cu rădăcină cu 10 noduri, numerotate de la 1 la 10, memorat cu ajutorul vectorului de taţi T=(0,1,1,2,3,3,3,5,5,2). Care dintre nodurile arborelui au exact doi descendenţi direcţi?

a. 8,9 b. 1, 8,9,10 c. 1,2,5 d. 6,7

76. Se consideră un arbore cu rădăcină cu 10 noduri, numerotate de la 1 la 10, memorat cu ajutorul vectorului de taţi T=(5,3,0,2,3,7,5,7,7,1). Mulţimea tuturor nodurilor de tip frunză este:

a. {6,8,9} b. {4,6,8,9,10} c. {4} d. {1,4,7}

77. Se consideră un arbore cu rădăcină cu 10 noduri, numerotate de la 1 la 10, memorat cu ajutorul vectorului de taţi T=(3,10,0,8,1,1,3,5,7,3). Care este lungimea celui mai lung lanţ format din noduri distincte cu o extremitate în rădăcină?

a. 5 b. 6 c. 2 d. 4

78. Câte valori nule pot apare într-un vector cu legături de tip „tată”, asociat unui arbore cu rădăcină ce conţine 10 noduri?

a. niciuna b. 9 c. 10 d. exact una

79. Care este numărul maxim de valori egale care pot apare într-un vector cu legături de tip „tată”, asociat unui arbore cu rădăcină ce conţine 10 noduri?

a. niciuna b. 9 c. 10 d. exact una

12. 4 Teste

1. Care este numărul maxim de muchii pe care îl poate avea un graf neorientat cu 6 noduri şi 4 componente conexe?

2. Care este numărul maxim de muchii pe care-l poate avea un graf neorientat cu 10 noduri care nu este conex?

a. (0,1,1,1,3,3,3,6,6,7) c. (1,1,1,2,3,3,3,6,6,7)b. (0,1,1,2,3,3,3,6,6,7) d. (1,0,1,2,3,3,3,6,6,7)

Page 31: teorie grafuri

3. Se consideră un graf neorientat dat prin listele de adiacenţă alăturate. Care este numărul maxim de muchii care pot fi eliminate din graf astfel încât graful rezultat să rămână conex?

4. Se consideră un graf neorientat cu 10 noduri numerotate de la 1 la 10 şi muchiile: (1,8), (1,10), (2,3), (2,5), (3,4), (3,5), (6,7), (7,9), (7,10), (9,10).Care este numărul minim de muchii care trebuie adăugate grafului pentru a deveni eulerian?

5. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile (1,2), (1,5), (3,6) ,(3,5), (4,5). Câte componente conexe are G şi care este indicele nodului care trebuie eliminat din graf astfel încât subgraful obţinut să aibă un număr maxim de componente conexe?

6. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile: (1,2), (1,4), (1,5), (1,6), (2,3), (3,4), (4,5), (5,6). Care este numărul minim de muchii care trebuie eliminate din graf astfel încât graful parţial obţinut să nu conţină nici un ciclu.

7. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile (1,3), (1,6), (1,5), (2,3), (2,5), (3,4), (4,5), (4,6). Care este numărul minim de muchii care trebuie eliminate din graf astfel încât graful parţial obţinut să aibă exact două componente conexe?

8. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile: (1,2), (1,4), (1,5), (1,6), (2,4), (2,6), (3,4), (3,5), (4,5). Câte muchii trebuie adăugate la acest graf astfel încât acesta să devină complet?

9. Care este numărul maxim de noduri de grad 1 pentru un graf neorientat conex cu 10 noduri şi 12 muchii?

10. Care este numărul minim de muchii ale unui graf neorientat, conex, cu 50 de noduri ?

11. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile: (1,2), (1,5), (1,6), (2,5), (2,6), (3,4), (4,5), (5,6), (3,6). Care este numărul maxim de muchii care pot fi eliminate din graf astfel încât graful parţial obţinut să-şi păstreze proprietatea de graf hamiltonian?

12. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile (1,2), (1,6), (2,3), (2,5), (3,4), (3,5), (4,5), (5,6). Care este numărul minim de muchii care trebuie adăugate grafului pentru ca acesta să devină eulerian?

13. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile: (1,2), (1,5), (1,6), (1,4), (3,4), (5,6). Care este numărul nodurilor de grad par?

14. Scrieţi o matrice de adiacenţă corespunzătoare unui graf neorientat cu 6 noduri în care toate nodurile au gradul 1 şi care are trei componente conexe.

15. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile: (1,2), (1,6), (2,3), (3,5), (2,6), (4,2), (4,6), (5,6). Câte lanţuri distincte de lungime 3 există de la nodul 1 la nodul 5. Care sunt acestea?

16. Se consideră un graf neorientat cu 10 noduri şi 10 muchii. Care este numărul maxim de noduri de grad 0 ?

1 2 6

2 1 3 6

3 2 4 5 6

4 3 5

5 3 4 6

6 1 2 3 5

Page 32: teorie grafuri

17. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile: (1,2), (1,4), (1,5), (1,6), (2,3), (2,4), (2,5), (3,6), (4,5). Care este numărul de muchii ce trebuie eliminate din graf astfel încât graful parţial obţinut să fie arbore?

18. Se consideră un graf neorientat cu 6 noduri şi 4 muchii. Care este numărul maxim de noduri de grad 1 care pot exista în graf?

19. Considerăm un graf neorientat cu 6 noduri şi 3 muchii, format din 3 componente conexe. Ştiind că doar două noduri au gradul 1, scrieţi o matrice de adiacenţă asociată unui astfel de graf.

20. Care este numărul minim de muchii care trebuie eliminate dintr-un graf neorientat complet cu 10 noduri astfel încât graful parţial obţinut să fie eulerian?

21. Se consideră un graf orientat G cu 6 vârfuri numerotate de la 1 la 6 dat prin listele de adiacenţă alăturate. Construiţi matricea de adiacenţă corespunzătoare grafului orientat G1

cu 6 vârfuri numerotate de la 1 la 6 în care există arc între vârfurile distincte i şi j dacă şi numai dacă în graful G există cel puţin un drum între nodurile i şi j.

22. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,3), (1,5), (2,4), (2,1), (3,2), (4,3), (5,3), (5,4), (6,1), (6,5). Câte dintre vârfurile grafului au gradul interior mai mare decât gradul exterior?

23. Într-un graf orientat G cu 6 vârfuri numerotate de la 1 la 6, există arc de la i la j dacă şi numai dacă i<j şi j-i>2. Câte dintre vârfurile grafului au gradul interior mai mare decât gradul exterior ?

24. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,3), (1,5), (2,4), (2,1), (3,2), (4,3), (5,3), (5,4), (6,1), (6,5). Câte dintre vârfurile grafului au gradul interior egal cu gradul exterior?

25. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,3), (1,5), (2,5), (4,1), (4,6), (5,2), (6,1). Care este numărul minim de arce care trebuie adăugate grafului astfel încât pentru orice două vârfuri distincte, x şi y din graf să existe cel puţin un drum de la x la y.

26. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,4), (1,6), (2,1), (2,4), (4,3), (4,5), (5,2), (6,4). ). Care este numărul minim de arce care trebuie adăugate grafului astfel încât pentru orice două vârfuri distincte, x şi y din mulţimea {1,2,3,4} să existe cel puţin un drum de la x la y.

27. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,4), (2,4), (2,6), (3,2), (4,5), (5,1). Care este numărul minim de arce care trebuie adăugate grafului astfel încât toate vârfurile să aibă gradul interior egal cu gradul exterior?

28. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,4), (1,6), (2,1), (2,3), (3,1), (4,5), (5,2), (6,5). Care este numărul minim de arce care trebuie eliminate din graf astfel încât graful parţial obţinut să nu mai conţină circuite?

29. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,5), (2,5), (3,2), (4,6), (5,1), (5,4), (6,2). Care este numărul vârfurilor care au proprietatea că au gradul exterior egal cu gradul interior?

1: 22: 43: 24:5: 3 46: 5

Page 33: teorie grafuri

30. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,4), (2,1), (2,5), (2,6), (2,3), (3,5), (4,2), (4,5), (6,5). Care este lungimea maximă a unui drum de la nodul 2 la nodul 5 format doar din arce distincte?

31. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 dat prin matricea de adiacenţă alăturată. Determinaţi un drum de lungime maximă de la vârful 1 la vârful 4.

32. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 dat prin matricea de adiacenţă alăturată. Scrieţi arcele din care este alcătuit un drum de la vârful 1 la vârful 6 şi care trece prin cel puţin 4 vârfuri(inclusiv 1 şi 6).

33. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,2), (1,6), (2,3), (4,2), (4,5), (5,6), (6,4). Care este lungimea maximă a unui circuit elementar care se poate obţine în graf după adăugarea unui singur arc?

34. Se consideră un graf neorientat cu 6 noduri numerotate de la 1 la 6 şi muchiile : (1,2), (1,4), (2,3), (2,5), (2,6), (3,4), (4,5), (4,6). Transformaţi acest graf într-un graf orientat prin înlocuirea fiecărei muchii cu exact un arc, astfel încât în graful orientat rezultat să existe cel puţin un drum de la orice nod x la orice nod y. Scrieţi reprezentarea prin matricea de adiacenţă a grafului orientat pe care l-aţi construit,.

35. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,6), (1,5), (1,2), (2,3), (3,5), (4,1), (5,4). Care sunt vârfurile accesibile din toate celelalte vârfuri ale grafului prin intermediul unor drumuri elementare.

36. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,4), (2,3), (3,2), (3,6), (4,1), (5,3), (5,6), (6,5). Câte componente tare conexe are graful dat?

37. Se consideră un graf orientat cu 6 vârfuri numerotate de la 1 la 6 şi arcele : (1,2), (2,5), (2,6), (3,2), (4,1), (5,4), (6,3). Care sunt vârfurile care fac parte din circuite de lungimi pare?

38. Câte muchii are un arbore cu 10 noduri?39. Se consideră un arbore cu rădăcină, cu 5 noduri, numerotate de la 1 la 5, dat

prin muchiile [1,5], [2,5], [3,5], [5,4]. Care sunt nodurile care pot fi desemnate ca rădăcină astfel încât fiecare arbore cu rădăcină obţinut să aibă exact 3 frunze ?

40. Se consideră un arbore cu rădăcină cu 10 noduri, numerotate de la 1 la 10, memorat cu ajutorul vectorului de taţi T=(4,3,4,0,4,2,3,2,2,2). Care este nodul care trebuie ales ca rădăcină astfel încât vectorul de taţi corespunzător arborelui rezultat să conţină 5 elemente egale ?

41. Se consideră un arbore cu rădăcină cu 10 noduri, numerotate de la 1 la 10, memorat cu ajutorul vectorului de taţi T=(4,3,4,0,4,2,3,2,2,2). Care este nodul cu cei mai mulţi descendenţi direcţi?

0 1 0 1 0 00 0 0 0 0 10 0 0 1 0 00 0 0 0 1 00 0 1 0 0 10 0 1 1 0 0

0 1 0 1 0 00 0 0 0 0 10 0 0 1 0 00 0 0 0 1 00 0 1 0 0 10 0 1 1 0 0

Page 34: teorie grafuri

42. Se consideră un arbore cu rădăcină cu 10 noduri, numerotate de la 1 la 10, memorat cu ajutorul vectorului de taţi T=(4,3,4,0,4,7,3,7,7,7). Care sunt frunzele arborelui?

43. Dacă G este un arbore cu rădăcină cu 50 de noduri, care este numărul maxim de frunze pe care le poate avea?

44. Se consideră un arbore cu rădăcină cu 50 de noduri numerotate de la 1 la 50. Dacă nodul 10 are exact 10 fraţi şi nodul 1 este tatăl nodului 10, câţi fii are nodul 1?

45. Care este numărul total de noduri ale unui arbore cu 50 de muchii ?46. Se consideră un arbore cu rădăcină, cu 10 noduri, numerotate de la 1 la 10, dat

prin muchiile [1,2], [1,3], [1,5],[1,9], [3,6], [3,7], [4,5], [5,10], [8,9]. Care este vectorul de taţi pentru acest arbore dacă se alege ca rădăcină nodul 5 ?

47. Se consideră un arbore cu 5 noduri numerotate de la 1 la 5, reprezentat prin matricea de adiacenţă alăturată. Scrieţi toate nodurile care pot fi alese ca rădăcină a arborelui astfel încât acesta să aibă un număr minim de frunze.

48. Se consideră un arbore cu 6 noduri numerotate de la 1 la 6 , reprezentat prin matricea de adiacenţă alăturată. Scrieţi toate nodurile care pot fi alese ca rădăcină a arborelui astfel încât acesta să aibă un număr par de frunze.

49. Scrieţi matricea de adiacenţă a arborelui cu rădăcină cu 5 noduri, numerotate de la 1 la 5, dat prin vectorul de taţi (5,3,5,3,0).

50. Se consideră un arbore cu rădăcină cu 10 noduri, numerotate de la 1 la 10, memorat cu ajutorul vectorului de taţi T=(0,1,1,2,3,3,3,6,6,7). Care este numărul total de fii ai nodului 3 ?

12. 5 Probleme rezolvate 1. Să se verifice dacă valorile g1,g2,.....,gn pot reprezenta gradele vârfurilor unui graf

neorientat cu n noduri.Implementare C++ Implementare Pascal

#include<iostream.h>

int n,g[11],s=0,vi=0;

void citire(){int i; for(i=1;i<=n;i++) {cout<<"g["<<i<<"]="; cin>>g[i]; s+=g[i]; if(g[i]==0)vi++; }}

program p1;type vector=array[1..11] of integer;var n,s,vi:integer; g:vector;procedure citire;var i:integer;begin for i:=1 to n do begin write(‘g[‘,i,’]=’); readln(g[i]); s:=s+g[i];

0 1 1 0 01 0 0 0 01 0 0 1 00 0 1 0 10 0 0 1 0

0 1 1 1 0 01 0 0 0 0 01 0 0 0 0 01 0 0 0 1 10 0 0 1 0 00 0 0 1 0 0

Page 35: teorie grafuri

int verificare(){if(s%2!=0||s>n*(n-1)) return 0; else {for(int i=1;i<=n;i++) if(g[i]>=n-vi) return 0; return 1; }}

void main(){cout<<"n="; cin>>n; citire(); if(verificare()) cout<<"valorile pot reprezenta gradele unui graf"; else cout<<"nu pot reprezenta gradele unui graf";}

if g[i]=0 then v[i]:=v[i]+1; end;end;function verificare:boolean;var i:integer;begin verificare:=true; if (s mod 2<>0)or(s>n*(n-1)) then verificare:=false else for i:=1 to n do if g[i]>=n-vi then verificare:=false;end;begin s:=0; vi:=0; write(‘n=’);readln(n); citire; if verificare then writeln(‘valorile pot reprezenta gradele unui graf’) else writeln(‘valorile nu pot reprezenta gradele unui graf’);end.

2. Să se verifice dacă un graf neorientat cu n noduri, dat prin matricea de adiacenţă este complet.

Implementare C++ Implementare Pascal

#include<iostream.h>

int n,a[11][11];

void citire(){int i,j; for(i=1;i<n;i++) for(j=i+1;j<=n;j++) {cout<<"a["<<i<<"]["<<j<<"]="; cin>>a[i][j]; a[j][i]=a[i][j];}}

int complet(){int i,j; for(i=1;i<n;i++) for(j=i+1;j<=n;j++) if(a[i][j]==0) return 0; return 1;}

void main(){cout<<"n="; cin>>n;

program p2;type matrice=array[1..11,1..11] of integer;var n:integer; a:matrice;procedure citire;var i,j:integer;begin for i:=1 to n-1 do for j:=i+1 to n do begin write(‘a[‘,i,’,’,j,’]=’); readln(a[i,j]); a[j,i]:=a[i,j]; end;end;function complet:boolean;var i,j:integer;begin complet:=true; for i:=1 to n-1 do for j:=i+1 to n do if a[i,j]=0 then complet:=false end;

Page 36: teorie grafuri

citire(); if(complet()) cout<<"graful dat prin matricea de adiacenta este complet"; else cout<<"nu este complet";}

begin write(‘n=’); readln(n); citire; if complet then writeln(‘graful dat prin matricea de adiacenta este complet’) else writeln(‘nu este complet’) ;end.

3. Să se genereze toate grafurile neorientate cu n noduri(se generează matricele de adiacenţă)

Implementare C++ Implementare Pascal

#include<iostream.h>

int n,a[11][11];long nrsol;

void afisare(){int i,j; nrsol++; cout<<"Solutia "<<nrsol<<endl; for(i=1;i<=n;i++) {for(j=1;j<=n;j++) cout<<a[i][j]<<' '; cout<<endl; }}

void generare(int i,int j){if(i==n)afisare(); else if(j>n) generare(i+1,i+2); else {a[i][j]=a[j][i]=0; generare(i,j+1); a[i][j]=a[j][i]=1; generare(i,j+1); }}

void main(){cout<<"n=";cin>>n;generare(1,2);}

program p3 ;type matrice=array[1..11,1..11] of integer;var n:integer; a:matrice; nrsol:longint;procedure afisare;var i,j:integer;begin nrsol:=nrsol+1; writeln(‘Solutia ‘,nrsol); for i:=1 to n do begin for j:=1 to n do write(a[i,j],’ ‘); writeln; end;end;procedure generare(i,j :integer);begin if i=n then afisare else if j>n then generare(i+1,i+2) else begin a[i,j]:=0; a[j,i]:=0; generare(i,j+1); a[i,j]:=1; a[j,i]:=1; generare(i,j+1); end;end;begin write(‘n=’); readln(n); generare(1,2);end.

4. Să se verifice dacă un graf neorientat cu n noduri dat prin matricea de adiacenţă este bipartit şi în caz afirmativ şă se afişeze mulţimile de noduri corespunzătoare.

Implementare C++ Implementare Pascal

Page 37: teorie grafuri

#include<iostream.h>int a[10][10],i,j,n,p;int x[20],nrsol;

void citire(){int i,j;for(i=1;i<n;i++) for(j=i+1;j<=n;j++) {cout<<"a["<<i<<"]["<<j<<"]="; cin>>a[i][j]; a[j][i]=a[i][j]; }}

void init(int k){x[k]=-1;}

int succesor(int k){return x[k]<1;}

int solutie(int k){return k==n;}

int valid(int k){int i; for(i=1;i<k;i++) if(a[i][k]==1&&x[i]==x[k]) return 0; return 1;}

void tipar(int k){int i,j; nrsol++; cout<<"X1:"; for(i=1;i<=n;i++) if (x[i]==1) cout <<i<<' '; cout<<" X2:"; for(i=1;i<=n;i++) if (x[i]==0) cout <<i<<' '; cout<<"\n";}

void back(){int k=2; x[1]=1; init(k); while(k>0) if(succesor(k)) {x[k]++; if (valid(k)) if(solutie(k)) tipar(k); else init(++k); } else k--;}

program p4;type matrice=array[1..11,1..11] of integer; vector=array[1..11] of integer;var i,j,n,p:integer; a:matrice; nrsol:longint; x:vector;procedure citire;var i,j:integer;begin for i:=1 to n-1 do for j:=i+1 to n do begin write(‘a[‘,i,’,’,j,’]=’); readln(a[i,j]); a[j,i]:=a[i,j]; end;end;procedure init(k:integer);begin x[k]:=-1;end;function succesor(k:integer): boolean;begin succesor:=x[k]<1;end;function solutie(k:integer): boolean;begin solutie:=k=n;end;

function valid(k:integer):boolean;var i:integer;begin valid:=true; for i:=1 to k-1 do if (a[i,k]=1)and(x[i]=x[k])then valid:=false;end;procedure tipar(k:integer);var i,j:integer;begin nrsol:=nrsol+1; writeln(‘Solutia ‘,nrsol); write(‘X1:’); for i:=1 to n do if x[i]=1 then write(i,’ ‘); writeln; write(‘X2:’); for i:=1 to n do if x[i]=0 then write(i,’ ‘); writeln;

Page 38: teorie grafuri

41

7

5

6 10

2

38

9

void main(){cout<<"dati nr de varfuri"; cin>>n; citire(); back();}

end;procedure back( );var k :integer ;begin k=2; x[1]=1; init(k); while k>0 if succesor(k) then begin x[k]:=x[k]+1; if valid(k) then if solutie(k) then tipar(k) else begin k:=k+1; init(k); end; end  else k:=k-1;end;begin write(‘n=’); readln(n); citire; back;end.

5. Se consideră un graf neorientat cu n noduri dat prin matricea de adiacenţă. Să se genereze şi să se afişeze toate componentele conexe ale grafului.

Algoritmul utilizează parcurgerea BF utilizând vectorul viz ca variabilă globală. În plus nodurile se marchează diferenţiat prin numărul componentei conexe căreia îi aparţin. Acest lucru poate fi util în alte probleme în care se prelucrează grafuri neconexe, probleme în care este utilă meorarea componentelor conexe. Programul de mai jos afişează componentele după fiecare parcurgere, dar ele se pot afişa şi la final prin prelucrarea lui viz.

Exemplu:Un vector viz de forma:

1 2 2 1 1 3 1 2 2 31 2 3 4 5 6 7 8 9 10

poate fi obţinut după parcurgerea în lăţime a unui graf ca cel de mai jos:

Implementare C++ Implementare Pascal

#include<iostream.h> program p5;

Page 39: teorie grafuri

int a[10][10],n,m,p1,p,u ;int coada[10],viz[10],nrcomp;

void citire(){int i,x,y; cout<<"dati n si m"; cin>>n>>m; for(i=1;i<=m;i++) {cout<<"dati extremitatile muchiei "; cin>>x>>y; a[y][x]=a[x][y]=1; }}

void parcurgere(int p1){int i,j,l1; p=u=1; coada[p]=p1; viz[p1]=nrcomp; while(p<=u) {l1=coada[p]; for(i=1;i<=n;i++) if(a[l1][i]&&!viz[i]) {viz[i]=nrcomp; u++; coada[u]=i;} p++;}}

void main(){int i,k; citire(); nrcomp=0; for(k=1;k<=n;k++) if(viz[k]==0) {nrcomp++; parcurgere(k); cout<<"componenta "<<nrcomp<<": "; for(i=1;i<=u;i++) cout<<coada[i]<<" ";

cout<<endl; }}

type vector=array[1..11] of integer; matrice=array[1..11,1..11] of integer;var n,m,p1,p,u,nrcomp,i,k:integer; coada,viz:vector; a:matrice;procedure citire;var i,x,y:integer;begin write(‘nr de noduri:’); readln(n); write(‘nr de muchii:’);readln(m); for i:=1 to m do begin write(‘introduceti capetele muchiei ’,i,’:’); readln(x,y); a[x,y]:=1; a[y,x]:=1; end;end;procedure parcurgere(p1:integer);var i,j,l1:integer;begin p:=1; u:=1; coada[p]:=p1; viz[p1]:=nrcomp; while p<=u do begin l1:=coada[p]; for i:=1 to n do if (a[l1,i]=1)and(viz[i]=0) then begin viz[i]:=nrcomp; u:=u+1; coada[u]:=i; end; p:=p+1; end;end;begin citire; nrcomp:=0; for k:=1 to n do if viz[i]=0 then begin nrcomp:=nrcomp+1; parcurgere(k); write(‘componenta ‘,nrcomp,’:’); for i:=1 to u do write(coada[i],’ ‘); writeln; end;

Page 40: teorie grafuri

end.

6. Se consideră un graf neorientat cu n noduri dat prin matricea de adiacenţă. Afişaţi toate ciclurile euleriene ale grafului.

Implementare C++ Implementare Pascal

#include<iostream.h>int a[10][10],n,m=0,x[20];

void citire(){int i,j;cout<<"dati n";cin>>n;for(i=1;i<n;i++)for(j=i+1;j<=n;j++) {cout<<"a["<<i<<"]["<<j<<"]=";

cin>>a[i][j]; a[j][i]=a[i][j]; m+=a[i][j]; }

}

void init(int k){x[k]=0;}int succesor(int k){return x[k]<n;}int valid(int k){int i;//if(k==1) return 1; if(a[x[k-1]][x[k]]==0) return 0;for(i=2;i<=k-1;i++) if(x[k]==x[i]&&x[k-1]==x[i-1]||x[k]==x[i-1]&&x[k-1]==x[i]) return 0;return 1;}

int solutie(int k){return k==m&&a[x[1]][x[m]];}

void tipar(int k){int i;for(i=1;i<=k;i++) cout<<x[i]<<" ";cout<<x[1];cout<<endl;}

void back(){int k=2;x[1]=1;init(k);while(k>1) if(succesor(k)){x[k]++;

if(valid(k)) if(solutie(k)) tipar(k);

else init(++k);}

else k--;}

program p4;type matrice=array[1..11,1..11] of integer; vector=array[1..11] of integer;var n,m:integer; a:matrice; x:vector;procedure citire;var i,j:integer;begin write(‘n=’); readln(n); for i:=1 to n-1 do for j:=i+1 to n do begin write(‘a[‘,i,’,’,j,’]=’); readln(a[i,j]); a[j,i]:=a[i,j]; m:=m+a[i][j]; end;end;procedure init(k:integer);begin x[k]:=0;end;function succesor(k:integer): boolean;begin succesor:=x[k]<n;end;function solutie(k:integer): boolean;beginsolutie:=(k=m)and(a[x[1],x[m]]<>0;end;

function valid(k:integer):boolean;var i:integer;begin valid:=true; if(a[x[k-1],x[k]]=0) then valid:=false; for i:=2 to k-1 do if (x[k]=x[i]and x[k-1]=x[i-1]) or(x[k]=x[i-1]and x[k-1]=x[i])then valid:=false;end;procedure tipar(k:integer);var i:integer;

Page 41: teorie grafuri

void main(){citire();back();}

begin for i:=1 to k do write(x[i],’ ‘); writeln;end;procedure back;var k :integer ;begin k=2; x[1]=1; init(k); while k>1 if succesor(k) then begin x[k]:=x[k]+1; if valid(k) then if solutie(k) then tipar(k) else begin k:=k+1; init(k); end; end  else k:=k-1;end;begin m :=0; citire; back;end.

12. 6 Probleme propuse

12.4 Probleme (Heading 2)

7. Fie G un graf orientat citit de la tastatură prin numărul de vârfuri, numărul de muchii şi extremităţile lor. Afişaţi pentru fiecare vârf gradele exterioare, mulţimile Γ, respectiv ω.

8. Fie G1 şi G2 două grafuri neorientate date prin matricile de adiacenţă. Verificaţi dacă sunt complementare. În cazul în care nu sunt afişaţi o listă de muchii ce trebuie adăugate/şterse din G2 aşa încât g2 să devină complementul lui G1.

9. Două grafuri G1=(X1,U1) şi G2=(X2,U2) se numesc izomorfe dacă există o funcţie bijectivă f:X1X2 cu proprietatea că pentru orice a,bX1 (a,b)U1 dacă şi numai dacă (f(a),f(b))U2. Fiind date două grafuri neorientate prin numărul de vârfuri şi muchiile lor precum şi valorile f(x)∀ xX1 scrieţi un subprogram care verifică dacă f este funcţie de izomorfism ; în caz contar verificaţi existenţa unei funcţii aşa încât G1 şi G2 să fie izomorfe.

10. Se dau două grafuri neorientate G1 şi G2 cu n noduri prin matricile lor de adiacenţă a şi b. Să se verifice dacă al G2 este graf parţial al lui G1.

11. Se consideră un graf neorientat cu n noduri dat prin matricea de adiacenţă. Să se genereze toate lanţurile elementare de lungime l care pleacă din nodul 1.

Page 42: teorie grafuri

12. Se consideră un graf neorientat cu n noduri dat prin muchiile sale. Să se parcurgă graful în lăţime pornind de la un nod dat p1.

13. Să se verifice dacă un graf neorientat cu n noduri dat prin matricea de adiacenţă este conex

14. Se consideră un graf neorientat cu n noduri dat prin matricea de adiacenţă în fişierul „matr.txt”. Să se verifice dacă o secvenţă dată de vârfuri reprezintă un ciclu elementar.

15. Pentru un graf neorientat dat să se afişeze, dacă există, toate drumurile de lungime minimă între vârfurile x şi y ce trec prin varful k ori prin varful z.(toate celelalte vârfuri fiind distincte). Graful este dat prin matricea de adiacenţă.

16. Se consideră un graf neorientat cu n noduri dat prin matricea de adiacenţă în fişierul „eulerian.txt”. Să se verifice dacă o secvenţă de p noduri dată de la tastatură reprezintă un ciclu eulerian al grafului.

17. Să se verifice dacă un graf neorientat cu n noduri dat prin matricea de adiacenţă este eulerian.

18. Se consideră un graf neorientat cu n noduri dat prin matricea de adiacenţă. Să se genereze toate lanţurile hamiltonene între nodurile c1 şi c2.

19. Se consideră un graf neorientat complet cu n noduri. Să se genereze ciclurile hamiltonene ale grafului precum şi numărul acestora.

20. Se consideră un graf neorientat cu n noduri dat prin matricea de adiacenţă în fişierul „secvenţă.txt”. Să se verifice dacă o secvenţă de p noduri dată de la tastatură reprezintă un ciclu hamiltonian al grafului.

21. Se consideră un graf neorientat cu n noduri dat prin matricea de adiacenţă. Să se afişeze componentele conexe cu număr maxim de vârfuri.

22. Se consideră un graf orientat cu n noduri dat prin matricea de adiacenţă în fişierul „matr.txt”. Să se genereze toate lanţurile hamiltoniene ale grafului.

23. Se consideră un graf orientat cu n noduri dat prin vectorul de arce în fişierul „arce.txt”. Să se afişeze componentele tare conexe.

24. Conform studiului făcut de Stanley Milgram de la Universitatea Harvard în 1967 este general acceptat astăzi că numărul mediu al cunoştinţelor intermediare care conectează oricare doi indivizi din lume este un număr mic. În terminologia de specialitate această proprietate a reţelelor sociale este numită efect „small world”(SW). Studii ulterioare au arătat că în Statele Unite gradul de interconectare

are o valoare medie ¿6 (oricare două persoane se pot cunoaşte prin intermediul unui număr mediu de 4-5 cunoştinţe). Fişierul oras.txt conţine pe primul rând un număr n(numărul de locuitori) şi pe următoarele rânduri câte o pereche de numere <n, semnificând relaţii de cunoaştere între două persoane. Verificaţi dacă legăturile sociale din oraş se încadrează în modelul small world.

25. Gigel îşi serbează mâine ziua de naştere şi are mai multi invitaţi la petrecere. Cei n invitaţi nu se cunosc toţi.Gigel vrea să îi aşeze la o masă rotundă astfel încât oricare doi vecini de la masă să se cunoască. Se ştie că dacă x îl cunoaşte pe y atunci şi y îl cunoaste pe x. Alegeţi un model convenabil de citire a datelor de intrare şi scrieţi un program care afişează toate posibilităţile de aşezare la masă(dacă există). În cazul în care nu se pot aşeza pe baza relaţiilor existente afişaţi câte prezentări trebuie să facă Gigel pentru ca problema să prezinte cel puţin o soluţie.

Page 43: teorie grafuri

26. Romeo si Julieta vor să se întâlnească pe drumul lor zilnic. Şiind că ei pleacă în acelaşi timp de acasă, merg cu aceeşi viteză şi fiecare alege drumul minim pentru a ajunge la destinaţia sa şi de asemenea prim intersecţiile prin care trece Romeo lasă un trandafir, iar prin intersecţiile prin care trece Julieta la câte un bileţel parfumat, să se verifice dacă pot ajunge simultan în acelaşi punct de întâlnire şi pe drumul parcurs câţi trandafiri respectiv câte bileţele adună fiecare.Se cunosc:

- numărul de intersecţii n şi numărul de străzi m;- punctul de plecare şi de sosire pentru fiecare dintre cei doi(Ji,Jf,Ri,Rf);- toate cele m străzi, cu intersecţiile ce le delimitează şi timpul necesar parcugerii lor;

27. Într-un laborator de informatică există n calculatoare şi p imprimante, unde valorile lui n si p sunt citite de la tastatură. Inginerul de sistem care administrează laboratorul doreşte să stabilească nişte legături între calculatoare şi imprimante, astfel încât oricare p calculatoare doresc să scrie simultan la imprimante, acest lucru să fie posibil.

a. să se afişeze numărul minim de legături necesare;b. să se scrie pe fiecare linie i a fisierului text “laborator.txt” numărul de

ordine al imprimantelor la care este conectat calculatorul Ci;

28. Fie G=(X,U) şiX'⊆X , cu proprietatea că ∀( x , y )∈ X ' xX ' atunci( x , y )∉U .

Mulţimea X’ numeşte mulţime interior stabilă. Cardinalul maxim al mulţimilor interior stabile se numeşte număr de stabilitate internă. Fie G un graf memorat în fişierul Matrice.txt(pe prima linie numărul de vârfuri iar pe următoarele matricea de adiacenţă). Să se afişeze numărul de stabilitate internă şi o mulţime interior stabilă de cardinal maxim (nodurile vor fi numerotate de la 1 la n).

12. 7 Răspunsuri

12. 3 Teste grilă (Heading 3)

1 b 11 c 21 d 31 d 41 d 51 b 61 b71

b

2 d 12 a 22 b 32 c 42 b 52 a 62 d72

c

3 a 13 a 23 d 33 d 43 c 53 c 63 d73

c

4 a 14 d 24 a 34 b 44 b 54 c 64 c74

b

5 c 15 c 25 c 35 d 45 d 55 a 65 b75

d

6 b 16 b 26 a 36 b 46 b 56 a 66 a76

c

7 a 17 b 27 a 37 d 47 c  57 d 67 c77

b

8 d 18 d 28 d 38 d 48  a 58 d 68 d78

d

9 d 19 d 29 a 39 c 49  b 59 b 69 a 7 d

Page 44: teorie grafuri

9

10 a 20 b 30 c 40 a 50  b 60 b 70 a80

b

12. 4 Teste (Heading 3)

1. 3 muchii.2. Graful are 2 componente conexe cu un număr maxim de muchii egal cu 36.3. 4 muchii. Se vor elimina de exemplu muchiile (1,2), (2,6), (3,6), (3,5).4. 3 muchii. Se vor adăuga de exemplu muchiile (7,8), (6,4), (10,3) .5. Graful are o componentă conexă şi se va elimina nodul 5.6. 3 muchii, de exemplu : (1,4), (1,5), (2,3).7. 2 muchii, de exemplu: (2,5) şi (2,3).8. 6 muchii deoarece un graf complet cu 6 noduri are 15 muchii.9. 6 noduri.10. 49 muchii.11. 3 muchii de exemplu (1,6), (5,6), (2,5).12. 2 muchii de exemplu (6,2) şi (3,6).13. 4 noduri : 1,4,5,6.14. Un exemplu de matrice, dar nu unicul este

15. 3 lanţuri: (1,2,4,5), (1,2,6,5), (1,2,3,5).16. 5 noduri de grad 0.17. 4 muchii.18. 4 noduri.19. Un exemplu de matrice, dar nu unicul este

20. 5 muchii pentru ca gradele tuturor nodurilor să devină pare. De exemplu (1,2), (3,4), (5,6), (7,8), (9,10).

21.

22. 2 vârfuri: 3 şi 4.

0 1 0 0 0 01 0 0 0 0 00 0 0 1 0 00 0 1 0 0 00 0 0 0 0 10 0 0 0 1 0

0 1 1 0 0 01 0 0 0 0 01 0 0 1 0 00 0 1 0 0 00 0 0 0 0 00 0 0 0 0 0

0 1 0 1 0 00 0 0 1 0 00 1 0 1 0 00 0 0 0 0 00 1 1 1 0 00 1 1 1 1 0

Page 45: teorie grafuri

1

2

34

5

6

23. 3 vârfuri: 4, 5 şi 6.24. 2 vârfuri: 1 şi 5.25. 2 arce: (5,4) şi (3,4).26. 1 arc: (3,2).27. 2 arce: (4,2) şi (6,3).28. 1 arc: (5,2). 29. 4 vârfuri: 1,4,5,6.30. 5 pentru drumul: (2,1,4,2,3,5).31. (1,2,6,3,4)32. (1,4),(4,5),(5,6)33. 5 prin adăugarea arcului (3,1) se va forma circuitul elementar (1,6,4,2,3,1).34.

35. 636. 2 componente.37. 1,2,4,5.38. 9 muchii39. 1,2,3,440. 241. 742. 1,5,6,7,8,9,1043. 4944. 1145. 5146. (5,1,1,5,0,3,3,9,1,5)47. 2 şi 548. 1 şi 449.

50. 3 fii: 5,6 şi 7

0 0 0 1 0 01 0 1 0 0 00 0 0 1 0 00 0 0 0 1 10 1 0 0 0 00 1 0 0 0 0

0 0 0 0 10 0 1 0 00 1 0 1 10 0 1 0 01 0 1 0 0