Test

1. G=(V, E) is a connected undirected graph with 20 nodes and 99 edges. The maximum number of edges that can be removed so that the graph remains connected is:

50 80 79 81

2. What is the maximum number of isolated vertices that an undirected graph with 8 nodes and 12 edges can have?

1 3 0 2

3. The unoriented graph G={(1,2),(1,3),(2,3),(4,5),(4,1),(2,5)} is:

Hamiltonian Eulerian Tree Acyclic

4. It is considerded the unoriented graph G={(1,2),(1,3),(2,3),(3,4),(6,5),(4,6),(4,5)}. What is the smallest number of edges that must be added to the graph for it to become Eulerian?

1 4 3 2

5. The number of subgraphs of an undirected graph with n vertices and m edges is 2^m. The statement is:

True False

6. Which node from the unoriented graph G={(1,6),(2,6),(6,4),(4,3),(3,5)} can be chosen as a root, so as to form a tree whose root has 3 direct descendants?

3 4 6 1

7. How many siblings has node 1 din arborele cu rădăcină cu 7 noduri, numerotate de la 1 la 7, având următorul vector de tați: (5,1,5,1,0,7,5)?

1 3 2 0

8. What is the maximum possible degree and what is the minimum possible degree for a node in an n-node graph that is a tree?

n-1 and 0 n-1 and 1 n and 0 n and 1

9. The minimum number of edges that can be removed such that the graph G={(1,2),(1,4),(2,4),(4,3),(3,1),(3,5), (5,6),(3,6)} to become a tree is:

0 1 2 3

10. An undirected and connected graph has n nodes and n-1 edges. What is the minimum number of edges that must be added in order to obtain a cycle?

1 (n²-3n-2)/2 (n²-n)/2 0