Se consideră graful neorientat cu 5 noduri a cărui matrice de adiacenţă are toate elementele 1, cu excepţia celor de pe diagonala principală, care sunt nule. Care este numărul minim de muchii care pot fi eliminate astfel încât graful parţial obţinut să fie format din 3 componente conexe?

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

Într-un graf nul, toate nodurile sunt

$$0\le d\left(x\right)\le$$  ? , în orice  graf neorientat de ordin n,

Matricea de adiacenţă a unui graf neorientat G are numărul valorilor de 1 egal cu jumătate

din numărul valorilor de 0. Care dintre numerele de mai jos poate fi numărul de noduri ale grafului G?

Se consideră graful neorientat cu 7 noduri, numerotate de la 1 la 7, şi muchiile[1,3],[2,3], [3,4], [3,5], [5,4], [1,2], [2,5], [2,4], [6,7], [3,6]. Care dintre următoarele succesiuni de noduri reprezintă un lanţ care trece o singură dată prin toate nodurile grafului?

Se consideră graful neorientat cu 6 noduri, definit cu ajutorul listelor de adiacenţă alăturate. Care dintre mulţimile următoare de noduri are toate elementele extremităţi ale unor lanţuri elementare de lungime 2 cu cealaltă extremitate în nodul 5?

1:4,5,6

2:5

3:4

4:1,3

5:1,2,6

6:1,5

Se consideră un graf neorientat G, cu 5 noduri, reprezentat prin matricea de adiacenţă de mai jos:

0 1 0 0 1

1 0 1 1 1

0 1 0 1 0

0 1 1 0 0

1 1 0 0 0

Afirmaţia adevărată este:

Care dintre următoarele grafuri neorientate este un graf eulerian, dar nu este hamiltonian? Grafurile sunt precizate prin n numărul de noduri și mulțimea U a muchiilor.

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, se cere să indicați cum trebuie modificat graful, astfel încât acesta să devină eulerian.

Fie un graf neorientat cu 10 noduri. Gradele vârfurilor acestuia sunt reținute în șirul: 4,2,2,3,3,3,2,4,2,3. Precizați care este numărul de muchii ce trebuie adăugate pentru ca graful să devină complet.

1.       Numărul minim de muchii care trebuie adăugate grafului din figura alăturată, astfel încât acesta să devină eulerian este:

Se consideră un graf neorientat complet cu trei noduri. Care este numărul minim de muchii care trebuie eliminate din acest graf astfel încât graful parţial rezultat să aibă două componente conexe?

Se consideră un graf neorientat conex cu şase noduri în care fiecare nod are gradul 2. Care este numărul minim de muchii care trebuie eliminate din acest graf astfel încât graful parţial rezultat să aibă două componente conexe?

Se consideră un graf neorientat cu 8 noduri, numerotate de la 1 la 8 şi muchiile: [1,4], [1,8], [2,1], [2,3], [3,1], [4,5], [4,7], [5,7], [6,5]. Precizaţi câte componente conexe va avea subgraful obţinut prin eliminarea nodului 1.

Câte grafuri neorientate, distincte, cu 8 vârfuri, se pot construi? Două grafuri se consideră distincte dacă matricele lor de adiacenţă sunt diferite.

Dacă n este un număr natural impar mai mare decât 2, atunci un graf neorientat cu n noduri, în care fiecare nod este adiacent cu exact n-1 noduri, este întotdeauna:

Pentru graful neorientat din figura de mai jos, care este numărul de muchii ale celui mai lung lanţ, format din noduri distincte, ce are ca extremităţi nodurile 1 şi 3?

Se consideră graful neorientat cu 6 noduri, definit cu ajutorul listelor de adiacenţă alăturate.

1: 4,5,6

2: 5

3: 4

4: 1,3

5: 1,2,6

6: 1,5

Care dintre mulţimile următoare de noduri are toate elementele extremităţi ale unor lanţuri elementare de lungime 2 cu cealaltă extremitate în nodul 5?

Fie graful neorientat cu 6 noduri, numerotate de la 1 la 6, şi muchiile [1,2], [1,3], [1,4], [2,3], [2,4], [3,4], [3,5], [4,5], [4,6], [5,6]. Care este numărul maxim de muchii ce pot fi eliminate astfel încât graful parţial obţinut să-şi păstreze proprietatea de graf hamiltonian?

Numărul minim de noduri cu gradul 1 pentru un graf neorientat conex cu 21 noduri şi 20 muchii este:

Se consideră graful neorientat: cu 60 de noduri şi 40 de muchii. Suma gradelor tuturor nodurilor este egală cu :