 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

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.

Loops, multiple edges and simple 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

Explain what we need change to make the following network simple:

16

State whether the following networks are simple:

a
b
c
d
e
f
17

The social network Bleeter allows people to share content (in the form of "Bleets") online.

Before anyone can share anything, two people must first make a connection, so one person "follows" the other. Whenever a person creates a Bleet, it is shared with everyone who follows them. These people are called "followers".

The given network represents the connections among a group of six users of Bleeter. An arrow from one vertex to another means that the first person follows the second. So DF follows BK.

a

What kind of network, directed or undirected, represents the connections people form on Bleeter?

b

Which user has the most followers?

c

Which user follows the most people?

d

18

Consider the table below:

a

For each number of vertices in the first row of the table, draw a simple network and then fill in the number of edges in the resulting network in the second row of the table:

b

Determine the rule that calculates the number of edges, E, given the number of vertices, V, for a simple network.

c

Hence calculate the number of edges required for a simple network with 10 vertices.

Connected graphs and bridges
19

Define the following in terms of graph theory:

a

A connected graph

b

A bridge

20

Consider the following graph:

a

Which vertex is isolated?

b

How many edges are there?

c

How many vertices are there?

d

Which vertex is the loop connected to?

e

f

21

Determine whether the following statements are true or false in relation to undirected connected graphs:

a

There is an isolated vertex.

b

There are no loops.

c

Each vertex is linked to another vertex only through one edge.

d

Every vertex is reachable via some path from every other vertex.

22

State whether the following graphs are connected:

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

Consider the given disconnected network:

a

In order to make the network connected, an edge from vertex P chould be drawn to which other vertices?

b

If edge WU is added, will there be a path from P to Q?

24

Consider the given disconnected directed network:

a

In order to make the network connected, an edge from vertex P could be drawn to which other vertex?

b

After adding the edge from P to R, is there now a path from R to P?

25

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

a
b
c
Degree of a vertex
26

Consider the following diagram:

a

State the number of vertices.

b

State the number of edges.

c

Copy and complete the following table:

d

Is the graph connected or disconnected?

27

Consider the following diagram:

a

State the number of vertices.

b

State the number of edges.

c

Describe the graph as connected or disconnected.

d

Complete the table below:

28

What degree does a loop have?

29

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.

Subgraphs and bipartite graphs
30

For each of the following pairs of graphs, determine whether Graph 2 is a subgraph of Graph 1:

a

Graph 1

Graph 2

b

Graph 1

Graph 2

c

Graph 1

Graph 2

31

Find the weight of each highlighted subgraph:

a
b
32

Consider the given graph:

a

Find the weight of the subgraph formed by the vertices P, S, and V.

b

Find the weight of the subgraph formed by deleting vertices V, W, T, and S, along with all connecting edges.

33

Define the term "bipartite graph".

34

State whether the following graphs are bipartite graphs:

a
b
c
d
e
f
g
h
i
j
Complete graphs
35

Define the term "complete graph".

36

State whether the following graphs are complete graphs:

a
b
c
d
e
f
g
h
i
j
k
37

Determine the number of edges in a complete graph which has:

a

3 vertices

b

4 vertices

c

5 vertices

d

n vertices

38

Determine the number of vertices in a complete graph which has 6 edges.

39

A complete bipartite graph is a special kind of bipartite graph where every vertex of the one group is connected to every vertex of the other group. State whether the following are complete bipartite graphs:

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

Determine the number of edges in a complete bipartite graph which has:

a

2 vertices in each group.

b

3 vertices in each group.

c

4 vertices in each group.

d

n vertices in each group.

41

Write down the terms that describe each of the following graphs from the list of terms below:

• Complete

• Connected

• Simple

• Directed

• Bipartite

• Weighted

a
b
c