Mathematics Form 4 Chapter 5 [Network in Graph Theory]

State the number of vertices.

• 14

• 3.5

• 7

• 5

State the number of edges.

• 18

• 7

• 9

• 6

Determine the sum of degrees.

• 16

• 8

• 4

• 13

Determine the n(E) for this graph with multiple edges and loops.

• 8

• 20

• 5

• 10

Determine n(E).

• 7

• 12

• 14

• 6

Which of the statements below is not true?

(2 answer)

• 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

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 (cheapest) 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

A simple graph has no loops. What other property must a simple graph have?

• It must be directed.

• It must be undirected.

• It must have at least one vertex.

• It must have no multiple edges.