Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
O companie de logistică are o rețea formată din 12 centre, numerotate de la 1 la 12, între care există comunicații bidirecționale, astfel: între 1 și 2, între 1 și 3, între 2 și 3, între 2 și 4, între 3 și 5, între 4 și 5, între 4 și 6, între 5 și 6, între 6 și 7, între 7 și 8, între 7 și 9, între 8 și 9, între 9 și 10, între 10 și 11, între 10 și 12, între 11 și 12. Rețeaua este modelată ca un graf neorientat, în care nodurile reprezintă centrele, iar muchiile reprezintă comunicațiile dintre acestea. Indicați numărul minim de muchii care trebuie eliminate, astfel încât graful parțial obținut să fie format din trei componente conexe, fiecare cu câte 4 noduri.
a. 2
b. 4
c. 5
d. 7
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Figura de pe pagina 1 reprezintă nodurile 1, 2, 3, 4, 5 și 6 și muchiile {1,2}, {1,3}, {1,5}, {2,3}, {3,6}, {5,6}. Nodul 4 este izolat.
Un graf neorientat cu 6 noduri, numerotate de la 1 la 6, este reprezentat alăturat. Indicați numărul maxim de muchii care pot fi adăugate, astfel încât graful obținut să fie eulerian.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Un graf neorientat are 7 noduri și 21 de muchii. Indicați numărul minim de muchii care pot fi eliminate din acest graf, astfel încât graful parțial obținut să aibă două componente conexe, cu cel puțin două noduri fiecare.
a. 6
b. 8
c. 10
d. 12
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Un graf orientat fără circuite are 10 vârfuri. Indicați numărul maxim de arce ale grafului.
Într-un arbore cu 50 de noduri, numerotate de la 1 la 50, rădăcina este nodul numerotat cu 1, iar tatăl oricărui alt nod i al său este nodul numerotat cu [i/2]. Indicați lungimea lanțului elementar cu o extremitate în nodul 32 și cealaltă extremitate în nodul 23.
Oricare dintre cele 5 vârfuri ale unui graf orientat are proprietatea că suma dintre gradul său extern și gradul său intern este 4. Indicați lungimea maximă a unui drum elementar în acest graf.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
Într-un graf neorientat, cu 10 muchii, două noduri au gradul 0, șase noduri au grade impare, iar celelalte noduri au grade pare, nenule. Indicați numărul maxim de noduri ale grafului.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Indicați numărul maxim de vârfuri izolate pe care le poate avea un graf orientat cu 24 de vârfuri și 24 de arce poziționate adecvat.
a. 5
b. 6
c. 18
d. 21
Într-o zonă sunt 23 de obiective turistice, numerotate de la 1 la 23; zona este reprezentată ca un graf orientat în care vârfurile corespund acestor obiective, iar arcele sunt stabilite în funcție de modalitatea de deplasare între două obiective, astfel: de la fiecare obiectiv numerotat cu i (i∈[1,23]) se poate merge direct doar la obiectivul numerotat cu 2*i, dacă acesta există, sau doar la obiectivul numerotat cu i-1, în caz contrar.
Indicați numărul maxim de vârfuri ale unui drum elementar în acest graf, cu extremitatea inițială 1.
a. 5
b. 11
c. 16
d. 21
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
O companie de colectare a fructelor are 6 depozite, numerotate de la 1 la 6: depozitele 1, 3 și 5 conțin mere, depozitele 2 și 4 conțin pere, iar depozitul 6 conține piersici. Compania a construit 4 benzi de transport unidirecțional: de la depozitul 1 la depozitul 5, de la depozitul 5 la depozitul 2, de la depozitul 5 la depozitul 4 și de la depozitul 6 la depozitul 1. Dacă depozitele reprezintă vârfurile unui graf orientat, iar benzile de transport reprezintă arcele acestuia, indicați numărul minim de benzi de transport care pot fi adăugate, astfel încât graful obținut să aibă trei componente tare conexe, fiecare dintre acestea având vârfuri care corespund depozitelor cu același tip de fructe.
a. 4
b. 3
c. 2
d. 1
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Un graf neorientat are 5 noduri, numerotate de la 1 la 5, cu gradele figurate în tabelul alăturat. Indicați o pereche de valori posibile pentru x și y.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare muchie are extremități distincte și oricare două muchii diferă prin cel puțin una dintre extremități.
Într-un arbore cu 7 noduri, numerotate de la 1 la 7, nodul 1 este rădăcină și pentru orice nod numerotat cu i (i∈[1,7]), dacă se notează cu F(i) numărul de descendenți direcți („fii”) ai săi, atunci F(i)=0, dacă i este „frunză”, altfel F(i)=i+1. Indicați numărul maxim de „frați” ai nodului 7.
a. 4
b. 3
c. 2
d. 1
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
Într-un arbore cu rădăcină un nod se află pe nivelul n dacă lanțul elementar care are o extremitate în nodul respectiv și cealaltă extremitate în rădăcina arborelui are lungimea n. Pe nivelul 0 se află un singur nod (rădăcina). Un arbore cu rădăcină are 12 noduri, numerotate de la 1 la 12, și este reprezentat prin vectorul de „tați” (2,4,2,0,4,4,x,6,x,x,y,y). Indicați un set de valori pe care le pot avea x și y, știind că pe ultimul nivel există cinci noduri frunză și că un singur nod este numerotat cu o valoare egală cu numărul său de descendenți direcți („fii”) de tip „frunză”.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare muchie are extremități distincte și oricare două muchii diferă prin cel puțin una dintre extremități.
Un graf neorientat are 7 noduri, numerotate de la 1 la 7, și 8 muchii, dintre care șase sunt: [1,2], [2,4], [2,7], [3,4], [4,5], [4,6]. Știind că unul dintre lanțurile elementare care au lungimea maximă este 1, 2, 7, 5, 4, 6, indicați care ar putea fi celelalte două muchii ale grafului.
a. [1,4] și [4,7]
b. [1,4] și [5,7]
c. [2,5] și [4,7]
d. [3,6] și [5,7]
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
Într-un arbore cu rădăcină un nod se află pe nivelul x dacă lanțul elementar care are o extremitate în nodul respectiv și cealaltă extremitate în rădăcina arborelui are lungimea x. Pe nivelul 0 se află un singur nod (rădăcina).
Într-un arbore cu rădăcină toate nodurile de pe același nivel au un număr egal de „fii” și nu există două niveluri diferite cu același număr de noduri. Indicați numărul minim de noduri de pe nivelul 3.
a. 12
b. 9
c. 8
d. 5
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare muchie are extremități distincte și oricare două muchii diferă prin cel puțin una dintre extremități.
Un graf neorientat are 21 de noduri, numerotate de la 1 la 21; pentru oricare două noduri distincte ale sale, numerotate cu i, respectiv cu j, există muchia [i,j] dacă și numai dacă ultima cifră a lui i este egală cu ultima cifră a lui j. Indicați numărul valorilor nule din matricea de adiacență a grafului.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
Un graf neorientat are 7 noduri, numerotate de la 1 la 7, și 8 muchii, dintre care șase sunt: [1,2], [2,5], [2,6], [2,7], [3,7], [4,7]. Știind că unul dintre lanțurile elementare care au lungimea maximă este 3, 7, 4, 5, 2, 1, indicați care ar putea fi celelalte două muchii ale grafului.
a. [1,6] și [4,5]
b. [2,3] și [2,4]
c. [2,3] și [4,5]
d. [2,4] și [5,7]
Într-un arbore cu 7 noduri, numerotate de la 1 la 7, nodul 3 este rădăcină și pentru orice nod numerotat cu i (i∈[1,7]), dacă se notează cu F(i) numărul de descendenți direcți („fii”) ai lui, atunci F(i)=0, dacă i este „frunză”, sau F(i)=i-1, în caz contrar. Indicați numărul maxim de „frați” ai nodului 1.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Un graf orientat cu 7 vârfuri, numerotate de la 1 la 7, are arcele (1,2), (2,3), (3,1), (4,5), (4,6), (5,6), (6,7), (7,4). Indicați numărul minim de arce care pot fi adăugate și poziționate adecvat, astfel încât graful orientat obținut să fie tare conex.
a. 1
b. 2
c. 3
d. 4
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
Un graf neorientat are 25 de noduri și 5 componente conexe, fiecare dintre acestea fiind fără cicluri. Indicați numărul de muchii ale grafului.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Un graf orientat cu 6 vârfuri, numerotate de la 1 la 6, are arcele (1,3), (2,1), (2,5), (2,6), (4,3), (6,4), (6,5). Indicați numărul minim de arce care trebuie adăugate pentru ca graful obținut să aibă două componente tare conexe.
a. 1
b. 2
c. 3
d. 4
Într-un oraș sunt 5 piețe, iar una dintre acestea este conectată direct cu fiecare dintre celelalte patru prin câte o bandă de transport bidirecțională. Indicați numărul minim de benzi de transport bidirecționale care trebuie adăugate, astfel încât graful neorientat obținut, în care nodurile reprezintă piețele, iar muchiile reprezintă benzile de transport, să fie eulerian.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
Într-un oraș sunt 5 parcuri, notate cu A, B, C, D și E, care sunt conectate prin piste pentru biciclete, pe care se circulă într-un singur sens, astfel: o pistă de la parcul A către parcul B, o pistă de la parcul B către parcul E, o pistă de la parcul C către parcul D, o pistă de la parcul D către parcul C, o pistă de la parcul E către parcul A, o pistă de la parcul E către parcul C și o pistă de la parcul E către parcul D.
Indicați numărul minim de piste pentru care trebuie schimbat sensul de circulație, astfel încât graful orientat obținut, în care parcurile reprezintă vârfurile, iar pistele reprezintă arcele, să fie tare conex.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Un graf neorientat admite un ciclu eulerian, de lungime 11, precum și un ciclu hamiltonian, de lungime 7. Indicați numărul de muchii care pot fi eliminate din graf, astfel încât graful parțial obținut să fie arbore.
Într-un magazin sunt 8 raioane, distribuite în trei zone importante, în fiecare zonă fiind un număr par, nenul, de raioane. În scopul fluidificării deplasării clienților se marchează unele culoare, astfel încât fiecare culoar să conecteze două raioane, iar deplasarea pe el să se facă într-un singur sens.
Se realizează o hartă, sub forma unui graf orientat, în care vârfurile reprezintă raioanele din magazin, iar arcele reprezintă culoarele marcate. Indicați numărul maxim de culoare care se pot marca, astfel încât graful să aibă trei componente tare conexe, fiecare componentă fiind reprezentarea pe hartă a câte uneia dintre cele trei zone importante din magazin.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
Variabila a memorează un tablou bidimensional cu n linii și n coloane, numerotate începând de la 0. Știind că elementul a[2021][2022] se află pe diagonala secundară a tabloului, indicați valoarea lui n.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare muchie are extremități distincte și oricare două muchii diferă prin cel puțin una dintre extremități.
Un graf neorientat complet are 4 noduri. Indicați o valoare care NU poate fi numărul de muchii ale unui subgraf al acestui graf.
În grafurile din cerințe oricare arc/muchie are extremități distincte și oricare două arce/muchii diferă prin cel puțin una dintre extremități.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
Un graf neorientat complet are 21 de noduri. Indicați numărul de muchii ce pot fi eliminate, astfel încât graful parțial obținut să fie conex și fără cicluri.
Pentru fiecare dintre itemii de la 1 la 5, scrieți pe foaia de examen litera corespunzătoare răspunsului corect. Fiecare răspuns corect se notează cu 4 puncte.
În grafurile din cerințe oricare muchie are extremități distincte și oricare două muchii diferă prin cel puțin una dintre extremități.
Un graf neorientat are 40 de noduri și 5 componente conexe, fiecare dintre acestea fiind arbore. Indicați numărul de muchii ale grafului.
a. 33
b. 35
c. 39
d. 41
