Test teoria grafurilor

Numărul maxim de muchii într-un graf neorientat cu n vârfuri este:
1. n-1
2. n*(n-1)
3. (n*(n-1))/2
4. (n*(n+1))/2
Numărul maxim de arce într-un graf orientat cu n vârfuri este:
1. n*(n+1)
2. n*n-1
3. (n*(n-1))/2
4. n*(n-1)
Câte grafuri neorientate cu n vârfuri există?
1. n!
2. 2^(n*(n+1))/2
3. 2^(n*(n-1))/2
4. 2^n*(n-1)
Câte grafuri orientate cu n vârfuri există?
1. 2^n*n-1
2. 2^n*(n+1)
3. n*(n-1)
4. 2^n*(n-1)
Câte grafuri neorientate și complete cu n vârfuri există?
1. (n*(n-1))/2
2. n
3. 1
4. 2
Câte grafuri orientate și complete cu n vârfuri există?
1. 1
2. n!
3. C³_n
4. 3^(n*(n-1))/2
Numărul total de subgrafuri obținute dintr-un graf cu n vârfuri este:
1. 2ⁿ
2. 2^n-1
3. 2ⁿ-2
4. 2ⁿ-1
Numărul total de grafuri parțiale obținute dintr-un graf cu m muchii este:
1. 2^m-1
2. 2^m
3. 2^m-1
4. 2^m-2
Numărul total de grafuri turneu cu n vârfuri este:
1. 2^(n*(n-1))/2
2. 3^(n*(n-1))/2
3. 2^n*(n-1)
4. 3^n*(n-1)
Numărul maxim de muchii într-un graf cu graf aciclic cu n vârfuri este:
1. n-1
2. n
3. n²
4. n-2
Numărul maxim de muchii într-un graf cu n vârfuri și p componente conexe (unde p<n) este:
1. ((n-p)*(n-p-1))/2
2. C²_n-p+1
3. n*p
4. n-p+1
Un graf complet, hamiltonian si eulerian:
1. poate avea oricâte vârfuri
2. nu există un astfel de graf
3. poate avea 3 vârfuri
4. poate avea 4 vârfuri
Numărul de muchii ce trebuie eliminate dintr-un graf conex cu n vârfuri si m muchii pentru ca graful să devină arbore (parțial) este:
1. graful este deja arbore
2. n-m+1
3. nu se poate obține un astfel de graf
4. m-n+1
Câte vârfuri are un graf neorientat complet cu 15 muchii?
1. 6
2. 15
3. 5
4. 7
Dacă toate vârfurile unui graf conex sunt de grad par atunci:
1. este eulerian
2. este hamiltonian
3. este arbore
4. este bipartit
Elementele matricei de adiacență a unui graf neorientat cu n vârfuri:
1. au ca valoare 0, 1, -1
2. sunt simetrice față de diagonala secundară
3. sunt simetrice față de diagoanala principală
4. au suma valorilor n+1
Numărul maxim de arbori cu n vârfuri ce se pot construi este:
1. 2^n*(n-1)
2. n^n-2
3. 2^n*(n-2)
4. n^n-1
Se dă graful cu 5 vârfuri definit prin mulțimea muchiilor M={[1,2],[2,3],[3,4],[4,5]}. Care este numărul minim de muchii ce trebuie adăugate pentru ca graful să fie hamiltonian, dar nu eulerian?
1. 1
2. 3
3. 0
4. 2
Ce fel de graf este graful cu 5 vârfuri definit prin mulțimea muchiilor M={[1,2],[1,3],[2,3],[3,4],[3,5],[4,5]} ?
1. hamiltonian
2. aciclic
3. eulerian
4. arbore
Se consideră un graf cu 26 de vârfuri etichetate distinct cu literele din alfabetul englez. Se știe că orice vârf etichetat cu o vocală este adiacent cu toate vârfurile etichetate cu consoană și orice vârf etichetat cu o consoană este adiacent cu toate vârfurile etichetate cu vocală. Câte muchii are graful?
1. 21
2. 26
3. 105
4. 210
Fie un graf cu 12 vârfuri și 5 componente conexe. Care este numărul maxim de muchii pe care le poate avea graful?
1. 132
2. 28
3. 35
4. 21
Care este numărul minim de vârfuri pe care îl poate avea un graf cu 12 muchii si care conține 3 componente conexe si niciun vârf izolat:
1. 8
2. 11
3. 9
4. 10
Într-un graf neorientat cu n vârfuri (n>=3) fiecare vârf are gradul 2. Care este numărul maxim de componente conexe din care poate fi alcătuit graful?
1. 1
2. [n/3]
3. 2
4. n
Se consideră un graf conex cu n vârfuri și n-1 muchii. Care este gradul maxim al unui vârf aparținând acestui graf?
1. 3
2. 1
3. n/2
4. n-1
Care este numărul minim de muchii ale unui graf neorientat cu 24 de vârfuri astfel încât acesta să fie conex indiferent de dispunerea muchiilor?
1. 253
2. 276
3. 24
4. 254