NEW
Font size
WorksheetsNetwork in Graph Theory
Total questions: 25
Worksheet time: 13mins
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 the sum of degrees.
4
8
16
32
Determine n(E).
7
12
14
6
State Σ d(v)
4
8
16
32
State Σd(V) .
5
7
10
14
Determine n(V).
4
8
5
10
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
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
Choose the correct term to match each definition: Lines or curves that connect vertices.
Regions
Vertices
Edges
Paths
An edge that begins and ends at the same vertex.
Multiple edges
Vertices
Loop
Node
Links that connect the same two vertices to one another.
Multiple edges
Vertices
Loop
Nodes
When the edges have a numerical representation (to indicate length, time, capacity etc.).
Multiple edges
Weighted graph
Complete graph
Directed graph
No arrows are shown on the edges.
Directed graph
Weighted graph
Simple graph
Undirected graph
An undirected and unweighted graph with no multiple edges.
Undirected graph
Unweighted graph
Incomplete graph
Simple graph
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
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.
Which one is NOT a subgraph of the above graph?
Determine the number of vertices and sum of degrees.
8,16
8,8
6,4
8,13
When the edges have a numerical representation (to indicate length, time, capacity etc.).
Multiple edges
Weighted graph
Complete graph
Directed graph
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
