Indicați câte componente tare conexe are graful orientat G=(V,E)
unde V={1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
iar E={(1,2), (1,7), (1,10), (2,6), (3,2), (3,5), (3,9), (4,3), (4,6), (5,2), (6,1), (8,7), (9,6), (9,8)}
.
Varianta 1 |
5 |
Varianta 2 |
6 |
Varianta 3 |
7 |
Varianta 4 |
8 |
Fie un graf neorientat G
cu 1002
noduri numerotate cu numere naturale consecutive de la 1
la 1002
. Știind că oricare două noduri de aceeași paritate sunt adiacente, indicați cum trebuie modificat graful, astfel încât acesta să devină eulerian.
Varianta 1 |
se elimină două muchii |
Varianta 2 |
se elimină o muchie și se adaugă două muchii noi |
Varianta 3 |
se adaugă două muchii noi |
Varianta 4 |
se elimină o muchie |
Fie un arbore cu rădăcină care are 5000
de noduri iar fiecare nod are maxim 4
fii. Indicați care este înălțimea minimă a arborelui
Varianta 1 |
5 |
Varianta 2 |
6 |
Varianta 3 |
7 |
Varianta 4 |
8 |
Numărul de circuite elementare diferite (care au cel puțin un arc diferit) care trec prin nodul A
din graful orientat alăturat este?
Varianta 1 |
4 |
Varianta 2 |
5 |
Varianta 3 |
8 |
Varianta 4 |
9 |
În graful neorientat G
cu 100
de noduri, două noduri i
și j
sunt adiacente dacă |𝑖 − 𝑗| = 8
sau |𝑖 − 𝑗| = 12
. Numărul de componente conexe ale grafului este:
Varianta 1 |
2 |
Varianta 2 |
3 |
Varianta 3 |
4 |
Varianta 4 |
24 |
Secvența gradelor dintr-un graf neorientat este formată din gradele tuturor nodurilor grafului, aranjate în ordine descrescătoare. Indicați care dintre următoarele secvențe nu poate fi secvență a gradelor pentru niciun graf?
I: 7, 6, 5, 4, 4, 3, 2, 1
II: 6, 6, 6, 6, 3, 3, 2, 2
III: 7, 6, 6, 4, 4, 3, 2, 2
IV: 8, 7, 7, 6, 4, 2, 1, 1
Varianta 1 |
I și II |
Varianta 2 |
I și IV |
Varianta 3 |
II și IV |
Varianta 4 |
III și IV |
Pentru graful orientat de mai jos, indicați între care perechi de noduri există drum de lungime 5?
Varianta 1 |
A și B |
Varianta 2 |
A și C |
Varianta 3 |
A și D |
Varianta 4 |
B și C |
Fie graful orientat G=(V,E)
unde card(V)=20
iar E={(i,j)|i<j,i,j∈V}
. Numărul de componente tare conexe ale grafului G
este:
Varianta 1 |
1 |
Varianta 2 |
10 |
Varianta 3 |
15 |
Varianta 4 |
20 |
Un arbore binar complet este un arbore cu rădăcină în care fiecare nod are exact doi fii sau niciunul. Ştiind că rădăcina se găseşte pe nivelul 0
, numărul maxim de noduri de pe nivelul 5
dintr-un astfel de arbore este?
Varianta 1 |
15 |
Varianta 2 |
16 |
Varianta 3 |
31 |
Varianta 4 |
32 |
Se consideră un graf neorientat cu 10
vârfuri numerotate de la 1
la 10
, graf cu proprietatea că există muchie între vârfurile i
și j
dacă și numai dacă i
și j
sunt numere prime între ele. Care este suma gradelor vârfurilor acestui graf?
Varianta 1 |
30 |
Varianta 2 |
50 |
Varianta 3 |
60 |
Varianta 4 |
62 |