Network in Graph Theory

Which of the statements below is not true

• V = {P, Q, R, S, T, U}

• E = {(R,S), (S,T), (T,U), (U,P), (P,Q)}

• d(R) = 3

• sum of degree = 18

Which of the following statements in not true?

• V={ P, Q, R, S, T, U}

• E= {(P,P), (P,R), (R,S), (S,T), (T,S), (R,Q), (Q,P)}

• d(P) = 3

• sum of degree = 14

Which of the following statements in not true?

• V = { P, Q, R, S, T}

• E = { (P,Q), (Q,R), (S,R), (S,T), (T,T), (P,S), (S,P)}

• d_in (T) = 2

• sum of degree = 14

The directed graph on the right shows the

roads connecting Lani’s house at A to the

school at E. Suggest the shortest route

that Lani can choose to cycle to school.

• A > C > D > E

• A > B > C > E

• A > D > E

• A > B > E

The directed weighted graph on the right shows

the prices of tickets and the travel times for some

choices of flights of a private airline. Vertex S is the

destination of the flight from vertex P. Vertex Q and

vertex R are the transit airports. The transit time at

each of the airports is 45 minutes. Which one is the most economical route?

• P > Q > R > S

• P > R > S

• P > Q > S

• P > S

The directed weighted graph on the right shows

the prices of tickets and the travel times for some

choices of flights of a private airline. Vertex S is the

destination of the flight from vertex P. Vertex Q and

vertex R are the transit airports. The transit time at

each of the airports is 45 minutes. Which route takes the shortest time?

• P > Q > R > S

• P > R > S

• P > Q > S

• P > S

The following undirected graph shows six houses in a village. A salesperson needs to visit all

the houses starting from house A and finishing at house F. Calculate the shortest distance in km.

• 3.05

• 3.08

• 3.30

• 3.68