Graph theory

1) The path length from A to B in the following graph is:

a- 2

b- 10

c- 22

d- There is no path

2) The minimum path weight from A to B in the following graph is:

a- 2

b- 10

c- 32

d- There is no path

3) The minimum path weight from A to E in the following graph is:

a- 1

b- 7

c- 67

d- There is no path

4) The longest cycle that starts at A and ends at A in the following graph is:

a- 104

b- 122

c- 42

d- There is no cycle

5) The entry AE in the length one adjacency matrix representation of the following graph is:

a- 7

b-

c- 0

d- None of the above

6) The entry AB in the length one adjacency matrix representation of the following graph is:

a- 10

b-

c- 22

d- 0

7) The entry AD in the length two adjacency matrix representation of the following graph is:

a- 60

b-

c- 44

d- 0

8) In the following graph, which of the following paths is considered a simple path?

a- AECAD

b- AEBFC

c- ADBFD

d- There is no simple path in the graph above

9) Some of the cliques the following graph has include: (A clique is a subgraph that is complete which means each node in the subgraph is connected to every other node n the subgraph). In the following graph, the subgraph AEBD is not a clique because A and B are not connected and E and D are not connected also, otherwise if they were connected it would be a clique.

a- ADBE, EBFC, EB, F, C

b- AEC, DBF

c- AEB, EBC

d- AECFBD

10) (TSP): Apply the nearest-neighbor algorithm to the complete weighted graph G in the following figure, beginning at vertex B, what is the path and the total weight?

a- BADECB with weight 725

b- BAEDCB with weight 775

c- TSP does not work with complete graph

d- None of the answers is true