Grafuri orientate

Un graf neorientat are 10 muchii și este conex. Numărul maxim de noduri ale sale este:

• 8

• 9

• 10

• 11

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?

• 4

• 6

• 7

• 8

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?

• 2

• 3

• 4

• 5

Într-un graf nul, toate nodurile sunt

• terminale

• nule

• izolate

• complete

• n-1

• n

• 1

• 100

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?

• 12

• 14

• 11

• 13

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?

• (1 2 3 4 5 6 7)

• (4, 5, 3, 6, 7)

• (7, 6, 3, 5, 4, 2, 1)

• (1, 3, 5, 4, 2, 3, 6)

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

• {1,4,6}

• {2}

• {3}

• {2,6}

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:

• G este graf hamiltonian şi graf eulerian

• G este graf hamiltonian, dar nu este graf eulerian;

• G nu este graf hamiltonian, dar este graf eulerian

• G nu este graf hamiltonian, nici graf eulerian

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.

• n=5,U={[1,3],[1,4],[3,4], [2,4],[4,5],[2,5]}

• n=4,U={[1,2],[1,3],[2,3],[1 ,4], [2,4],[3,4]}

• n=3,U={[1,2],[1,3],[2,3]}

• N=6,U={[1,2],[2,3],[3,4], [5,4],[6,5],[2,6]}