Wayground logo

Free Printable Worksheets

Font size

S
M
L
XL
Worksheets

11MAG - Graphs and network

Total questions: 140

Worksheet time: 3hrs 37mins

Name
Class
Date
1.

Is this diagram correctly labelled?

a)

Yes

b)

No

2.

What is the degree of Vertex A?

a)

2

b)

3

c)

4

d)

5

3.

What is the degree of Vertex C?

a)

2

b)

3

c)

4

d)

5

4.

What is the degree of Vertex E?

a)

2

b)

3

c)

4

d)

5

5.

Determine the adjacency matrix for this network:

a)
b)
c)
d)
6.

In a network a Walk is any route taken through a network, including routes that repeat edges and vertices. What is a Trail?

a)

A walk in which no vertices are repeated, except possibly the start and finish

b)

A walk in which no edges are repeated

7.

What is a Eulerian Path?

a)

A path in a graph that visits every edge exactly once and returns to the start.

b)

A path in a graph that visits every vertex exactly once and returns to the start.

c)

A path beginning and ending at the same vertex.

8.

What is a Hamiltonian Path?

a)

A path in a graph that visits every edge exactly once and returns to the start.

b)

A path in a graph that visits every vertex exactly once and returns to the start.

c)

A path beginning and ending at the same vertex.

9.

How do you determine whether a graph is Eulerian?

a)

All vertices are even

b)

One odd vertex

c)

Two odd vertices

d)

Three odd vertices

10.

This graph has a Hamiltonian Circuit. True or False?

a)

False

b)

True

11.

In a network a Walk is any route taken through a network, including routes that repeat edges and vertices. What is a Path?

a)

A trail in which no vertices are repeated, except possibly the start and finish

b)

A trail in which no edges are repeated

12.

In this graph, what is the smallest weight?

a)

2

b)

4

c)

5

d)

9

e)

no clear answer

13.

Start at J. Walk all 7 streets. Return to J with minimal backtracking. The numbers on each edge represent the length, in hundreds of meters, of each street. What is the shortest length to start and end at vertex J?

a)

35

b)

44

c)

43

d)

26

e)

46

14.

Construct one route through each edge exactly one time with minimal back tracking. Indicate the MINIMUM time it will take to travel this route.

a)

313

b)

320

c)

354

d)

330

15.

Which of the above graphs is/are NOT planar?

a)

G1

b)

G2

c)

G3

d)

G4

16.

State meaning of weighted graph

a)

A graph in which the edges have direction

b)

A join or relationship between nodes or corner

c)

A graph that has a data or numerical value labelled on each edge

d)

An object in a graph and also known as node

17.

Find a length of a shortest path between a -- g

a)

7

b)

10

c)

5

d)

9

18.
Circuits start and stop at 
a)
same vertex
b)
different vertices
c)

at adjacent point

d)

similar loop

19.

Is the graph is planar or not?

a)

Planar

b)

Not planar

20.

A path is .... ?

a)

An edge that starts and end at same vertex

b)

A connection between two vertices

c)

A complete graph

d)

A series of consecutive edges which has no repeated edge

21.

Count number of edges

a)

3

b)

4

c)

5

d)

6

22.

A bridge exists between two vertices. Which vertices are they?

(a)  

23.

The graph has (a)   edges.

24.

The graph has (a)   edges.

25.

What is the degree of vertex C?

(a)  

26.

What is the degree of vertex B?

(a)  

27.

The graph has (a)   edges.

28.

The graph has (a)   odd vertices.

29.

Which graph is not isomorphic to the others?

(a)  

30.

Which graph is not isomorphic to the others?

(a)  

31.

Which graph represents the following adjacency matrix?

a)
b)
c)
d)
32.

Which graph represents the following adjacency matrix?

a)
b)
c)
d)
33.

Which graph represents the following adjacency matrix?

a)
b)
c)
d)
34.

Is this graph conntected?

a)

Connected

b)

Not Connected

35.

Is this graph conntected?

a)

Connected

b)

Not Connected

36.

A bridge exists between two vertices. Which vertices are they?

(a)  

37.

The graph has (a)   edges.

38.

What is the degree of vertex F?

(a)  

39.

The graph has (a)   even vertices.

40.

A bridge exists between two vertices. Which vertices are they?

(a)  

41.

What is the sum of the degrees of the vertices of the following graph?

(a)  

42.

What is the sum of the degrees of the vertices of the following graph?

(a)  

43.

What is the sum of the degrees of the vertices of the following graph?

(a)  

44.

State the value of f

(a)  

45.

Is the graph in Planar Form?

a)

Planar Form

b)

Not Planar Form

46.

Is the graph in Planar Form?

a)

Planar Form

b)

Not Planar Form

47.

Is the graph in Planar Form?

a)

Planar Form

b)

Not Planar Form

48.

Is the graph in Planar Form?

a)

Planar Form

b)

Not Planar Form

49.

Is the graph in Planar Form?

a)

Planar Form

b)

Not Planar Form

50.

State the value of f

(a)  

51.

For a planar connected graph, find f given v = 3 and e = 8

(a)  

52.

For a planar connected graph, find f given v = 1 and e = 7

(a)  

53.

For a planar connected graph, find e given f = 6 and v = 9

(a)  

54.

For a planar connected graph, find e given f = 3 and v = 10

(a)  

55.

For a planar connected graph, find v given e = 10 and f = 5

(a)  

56.

For a planar connected graph, find v given e = 8 and f = 5

(a)  

57.

Is the graph in Planar Form?

a)

Planar Form

b)

Not Planar Form

58.

Find the shortest path from Bartow to Kenton in the network shown

a)

B−S−O−K

b)

B−S−M−O−K

c)

B−S−M−K

d)

B−C−M−K

59.

Find the shortest path from Kinglake to Healesville in the network shown

a)

K-S-Y-H

b)

K-T-H

c)

K-Y-H

d)

K-T-Y-H

60.

Find the shortest path from Croghon to Stratmoore in the network shown

a)

C−B−S

b)

C−O−S

c)

C−M−S

d)

C−M−O−S

61.

Find the shortest path from A to F in the network shown

a)

A–B–E–F

b)

A–C–D–F

c)

A–B–D–F

d)

A–C–B–E–F

62.

Find the shortest path from A to D in the network shown

a)

A–B–D

b)

A–C–D

c)

A–E–D

d)

A–B–C–D

63.

Find the shortest path from A to D in the network shown

a)

A–B–D

b)

A–C–D

c)

A–E–D

d)

A–B–C–D

64.

What distance is travelled on the path A–B–E–H–I?

(a)  

65.

What distance is travelled on the circuit F-E-D-H-E-A-C-F?

(a)  

66.

How long will it take to drive from C to D via B?

(a)  

67.

How far is the drive from Nhill to Horsham via Natimuk?

(a)  

68.

Find the shortest distance between Nhill and Donald

(a)  

69.

Determine whether the graph has a Eulerian trail, a Eulerian circuit or neither

a)

Eulerian Trail

b)

Eulerian Circuit

c)

Neither

70.

Determine whether the graph has a Eulerian trail, a Eulerian circuit or neither

a)

Eulerian Trail

b)

Eulerian Circuit

c)

Neither

71.

Determine whether the graph has a Eulerian trail, a Eulerian circuit or neither

a)

Eulerian Trail

b)

Eulerian Circuit

c)

Neither

72.

Determine whether the graph has a Eulerian trail, a Eulerian circuit or neither

a)

Eulerian Trail

b)

Eulerian Circuit

c)

Neither

73.

Determine whether the graph has a Eulerian trail, a Eulerian circuit or neither

a)

Eulerian Trail

b)

Eulerian Circuit

c)

Neither

74.

Identify the walk in each of the graphs below as a trail, path, circuit or walk only

a)

Trail

b)

Path

c)

Circuit

d)

Walk Only

75.

Identify the walk in each of the graphs below as a trail, path, circuit or walk only

a)

Trail

b)

Path

c)

Circuit

d)

Walk Only

76.

Identify the walk in each of the graphs below as a trail, path, circuit or walk only

a)

Trail

b)

Path

c)

Circuit

d)

Walk Only

77.

Identify the walk in each of the graphs below as a trail, path, circuit or walk only

a)

Trail

b)

Path

c)

Circuit

d)

Walk Only

78.

Identify the walk in each of the graphs below as a trail, path, circuit or walk only

a)

Trail

b)

Path

c)

Circuit

d)

Walk Only

79.

Choose the correct term to match each definition: Lines or curves that connect vertices.

a)

Regions

b)

Vertices

c)

Edges

d)

Paths

80.

An edge that begins and ends at the same vertex.

a)

Multiple edges

b)

Vertices

c)

Loop

d)

Node

81.

Links that connect the same two vertices to one another.

a)

Multiple edges

b)

Vertices

c)

Loop

d)

Nodes

82.

When the edges have a numerical representation (to indicate length, time, capacity etc.).

a)

Multiple edges

b)

Weighted graph

c)

Complete graph

d)

Directed graph

83.

No arrows are shown on the edges.

a)

Directed graph

b)

Weighted graph

c)

Simple graph

d)

Undirected graph

84.

An undirected and unweighted graph with no multiple edges.

a)

Undirected graph

b)

Unweighted graph

c)

Incomplete graph

d)

Simple graph

85.

A sequence of vertices for which each vertex in the sequence is joined to the next vertex in the sequence by an edge.

a)

Walk

b)

Closed walk

c)

Path

d)

Trail

86.

A walk that doesn’t finish at the starting vertex.

a)

Walk

b)

Closed walk

c)

Open walk

d)

Trail

87.

A walk that has no repeat use of edges or vertices (except perhaps to end at the starting vertex).

a)

Path

b)

Closed walk

c)

Open walk

d)

Trail

88.

Every path is a trail.

a)

TRUE

b)

FALSE

89.

A walk that has no repeated edges (but can

revisit vertices).

a)

Path

b)

Trail

c)

Eulerian trail

d)

Hamiltonian circuit

90.

Every vertex in this network is (blank) to every other vertex.

a)

adjacent

b)

connected

c)

planar

d)

disconnected

91.

Two vertices are called (blank) if they are attached directly by at least one edge.

a)

adjacent

b)

connected

c)

planar

d)

complete

92.

If it is possible to create a walk from one vertex to any other vertex, the network must be ...

a)

connected

b)

planar

c)

complete

d)

disjoint

93.

Every vertex is connected to every other vertex by a single edge.

a)

Connected graph

b)

Planar graph

c)

Complete graph

d)

Disjoint graph

94.

If a (blank) is removed, it will leave the graph disconnected.

a)

node

b)

region

c)

bridge

d)

loop

95.

A graph that can be drawn in 2D without crossing of edges.

a)

bipartite

b)

connected

c)

complete

d)

planar

96.

A connected graph that does not contain a cycle.

a)

path

b)

walk

c)

circuit

d)

tree

97.

A graph in which the vertices can be split into two groups such that every edge joins a vertex from one group to a vertex from the other group.

a)

bipartite

b)

connected

c)

complete

d)

planar

98.

If a network can be drawn without taking the pen off the page and without going over the same edge twice it is ...

a)

Eulerian

b)

Hamiltonian

c)

traversable

d)

semi-Hamiltonian

99.

Which of the following best describes an Eulerian graph?

a)

Covers every edge once and starts and ends at same vertex.

b)

Includes every vertex exactly once and starts and finishes at same vertex.

c)

Includes every vertex exactly once. Starts and finishes at different vertex.

d)

Covers every edge once and starts and ends at different vertex.

100.

Which of the following best describes a Hamiltonian trail?

a)

Covers every edge once and starts and ends at same vertex.

b)

Includes every vertex exactly once and starts and finishes at same vertex.

c)

Includes every vertex exactly once. Starts and finishes at different vertex.

d)

Covers every edge once and starts and ends at different vertex.

101.

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.

a)

3.05

b)

3.08

c)

3.30

d)

3.68

102.

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)

A > C > D > E

b)

A > B > C > E

c)

A > D > E

d)

A > B > E

103.

You are required to construct a graph with 20 edges and each vertex with a degree of 4. How many vertices do you need to have on the graph?

a)

8

b)

10

c)

12

d)

15

104.

Which set represents the vertices of the graph?

a)

{1,2}, {2,3}. {2,4}, {4,5}, {4,6}

b)

{1, 2, 3, 4, 5, 6,}

c)

{1, 2, 3, 4, 5, 6, 7}

d)

{1,2}, {2,3}. {2,4}, {4,5}, {4,6}, {6,7}

105.

What is the degree of vertex 4?

a)

3

b)

4

c)

5

d)

7

106.

Which vocabulary term is illustrated through the diagram?

a)

Minimal Spanning Tree

b)

Four Color Theorem

c)

Cycle

d)

Vertices

107.

What is the weight of the shortest path from A to F?

a)

5

b)

7

c)

9

d)

11

108.

Which vertices are adjacent to E?

a)

B and C

b)

B, C, D, and A

c)

B

d)

A, B, C, D, F, G

109.

Which describes the edges of the graph?

a)

{A,B}, {A,C}, {A, E}, {B,C}, {B,E}

b)

A, B, C, D, E

c)

{A,B}, {A,C}, {A, E}, {B,C}, {B,E}, {C,D}

d)

{A,B}, {A,C}, {A, E}

110.

Every path is a trail.

a)

TRUE

b)

FALSE

111.

A walk that has no repeated edges (but can

revisit vertices).

a)

Path

b)

Trail

c)

Eulerian trail

d)

Hamiltonian circuit

112.

Two vertices are called __________ if they are attached directly by at least one edge.

a)

adjacent

b)

connected

c)

planar

d)

complete

113.

If it is possible to create a walk from one vertex to any other vertex, the network must be ...

a)

connected

b)

planar

c)

complete

d)

disjoint

114.

If a __________ is removed, it will leave the graph disconnected.

a)

node

b)

region

c)

bridge

d)

loop

115.

If a network can be drawn without taking the pen off the page and without going over the same edge twice it is ...

a)

Eulerian

b)

Hamiltonian

c)

traversable

d)

semi-Hamiltonian

116.

A loop has a degree of 2.

a)

True

b)

False

117.

The number of edges will always equal half the number of degrees.

a)

True

b)

False

118.

How many edges does a graph with a sum of degrees = 30 have?

a)

15

b)

17.5

c)

30

d)

60

119.

Identify the number of edges that connect vertex A and vertex C

a)

0

b)

1

c)

2

d)

3

120.

True or False.


Graphs & networks are essentially the same thing.

a)

True

b)

False

121.

In a graph modelling social relationship, a person is represented as ______________ while friendship is represented as ______________.

a)

vertex, edge

b)

edge, vertex

c)

vertex, dot

d)

circle, entity

122.

If a path is closed, it is called a...?

a)

Cycle

b)

Circuit

c)

Closed path

d)

Trail

123.

A closed trail is called...?

a)

Cycle

b)

Circuit

c)

Closed trail

d)

Path

124.

By looking at the pattern of the numbers in the table, determine the number of edges for a complete graph to be drawn from 9 nodes given.

a)

28

b)

36

c)

45

d)

55

125.

If the number of edges of a complete graph can be drawn from n nodes given is 91. What is the value of n?

a)

12

b)

13

c)

14

d)

15

126.

You are required to construct a graph with 20 edges and each vertex with a degree of 4. How many vertices do you need to have on the graph?

a)

8

b)

10

c)

12

d)

15

127.

The graph shown contains NO cycles.

a)

True

b)

False

128.

The graph shown contains NO cycles.

a)

True

b)

False

129.

Which of the following statements are TRUE about a minimal spanning tree?

a)

Each branch has a weight.

b)

Contains no cycles.

c)

All vertices are connected.

d)

The path results in the minimum total weight.

130.

Create a minimal spanning tree, then find the minimum total cost.

a)

30

b)

39

c)

47

d)

50

131.

Create a minimal spanning tree, then find the minimum total cost.

a)

20

b)

21

c)

22

d)

23

132.
The number of vertices in a tree with 12 edges is 
a)
10
b)
11
c)
12
d)
13
133.

Using Kruskal’s algorithm, which edge should you choose second?

a)

AE

b)

BD

c)

DE

d)

AB

134.

Using Kruskal’s algorithm, which edge should you choose fourth?

a)

AB

b)

BC

c)

BD

d)

DE

135.

Find the minimum spanning tree (MST) using Kruskal’s algorithm and provide the overall weight.

a)

20

b)

25

c)

28

d)

30

136.

Find the minimum spanning tree (MST) using Kruskal’s algorithm and provide the overall weight.

a)

20

b)

25

c)

28

d)

30

137.

A cycle is...

a)

A path that starts and ends at different vertices.

b)

A path that starts and ends at the same vertex where backtracking is allowed.

c)

A path that starts and ends at the same vertex and uses every edge exactly once.

d)

A path that starts and ends at the same vertex and does not use any edge more than once.

138.

Create a minimal spanning tree, then find the minimum total cost.

a)

20

b)

21

c)

22

d)

23

139.

Create a minimal spanning tree, then find the minimum total cost.

a)

21

b)

22

c)

23

d)

24

140.

Create a minimal spanning tree, then find the minimum total cost.

a)

32

b)

33

c)

34

d)

35

Similar Resources on Wayground

Simplifying Polynomials

141 questions

Simplifying Polynomials

quiz

Worksheet

•

9th - 12th Grade

Mastery Goal 11, Domain and Range

144 questions

Mastery Goal 11, Domain and Range

quiz

Worksheet

•

9th - 12th Grade

Day 6, Period 2, Makeup

142 questions

Day 6, Period 2, Makeup

quiz

Worksheet

•

9th - 12th Grade

Precalculus Final Study

145 questions

Precalculus Final Study

quiz

Worksheet

•

9th - 12th Grade

Algebra 2 Spring 25 Review

145 questions

Algebra 2 Spring 25 Review

quiz

Worksheet

•

9th - 12th Grade

Unit 5 Review

145 questions

Unit 5 Review

quiz

Worksheet

•

9th - 12th Grade