topic badge

4.01 Introduction to graphs and networks

Worksheet
Graphs and networks
1

State the number of vertices and edges for the following networks:

a
b
2

State whether the following networks are non-valid:

a
b
c
d
e
f
g
h
3

Is the number of edges greater than the number of vertices in the given network?

4

For each of the given networks, list the pairs of vertices that have an edge between them:

a
b
5

Consider the given graph:

a

State the number of edges connected to vertex A.

b

List the vertices adjacent to vertex E.

c

Name the vertex that is directly connected to all other vertices.

d

Name the vertex that is not directly connected to vertex A.

6

State whether the following networks demonstrate the statement "One pair of vertices has more than one edge between them":

a
b
c
d
7

State whether the following statements are true or false in relation to all networks:

a

There is always at least one vertex.

b

There is always at least one edge.

c

All vertices must be connected to every other vertex by edges.

d

An edge can start and end at the same vertex.

e

Edges always start and end at vertices.

f

An edge can connect three vertices together.

8

State whether the following networks are directed or undirected:

a
b
c
d
e
f
g
h
i
j
k
l
9

Determine whether the following situations would be best represented by a directed or undirected network:

a

The countries that border each other

b

The results of an elimination-style sports tournament

c

The animal food chain

d

Your parents and their ancestors

e

Ways to get from one classroom to another at school

f

How parts of the body are connected

Weighted networks
10

Consider the following networks:

a
i

State the weight of the edge from S to Q.

ii

Calculate the weight of the entire network.

b
i

State the weight of the edge connecting Q and S.

ii

Calculate the weight of the entire network.

11

Consider the graph:

a

State the number of arcs that begin at vertex Z.

b

State the weight of the arc BC.

12

Consider the graph:

a

State the number of arcs that end at vertex T.

b

Calculate the total weight of all arcs that end at vertex V.

Parts of networks
13

Define the following in terms of graph theory:

a

A loop

b
A simple network
14

How many loops are in the following networks:

a
b
c
d
15

For each of the given networks, state which of the highlighted edges are bridges:

a
b
c
16

What degree does a loop have?

17

Consider the following networks:

a
i

State the degree of vertex C.

ii

State the degree of vertex D.

b
i

State the degree of vertex X.

ii

State the degree of vertex C.

Sign up to access Worksheet
Get full access to our content with a Mathspace account

Outcomes

4.2.1.1

understand the meanings of the terms graph, edge, vertex, loop, degree of a vertex, subgraph, simple graph, complete graph, bipartite graph, directed graph (digraph), arc, weighted graph and network

What is Mathspace

About Mathspace