Java

TOPIC 24 – INTRO TO GRAPHS

LESSON WORK

QUESTION 1A

For the graph below, if possible, give a path from

a) 0 to 6

b) 0 to 4

c) 2 to 5

QUESTION 1B

For the graph below, if possible, give a path from

d) 1 to 7

e) 2 to 13

f) 10 to 3

QUESTION 1C

For the graph below, if possible, give a path from

g) 1 to 2

h) 10 to 7

i) 8 to 7

QUESTION 2

You have created a video game that consists of 11 rooms. Each room has teleports that bring you to other rooms (denoted by arrows). To win, the player simply needs to visit each room. Which room do you need to visit last in order to win?

QUESTION 3

A fully connected graph is a graph that has a single edge between every pair of vertices.

a) How many edges does a 5-vertex graph have?

b) How many edges does an 8-vertex graph have?

c) How many edges does an n-vertex graph have?

Hint: Find the solution for a 2-vertext graph, then a 3-vertext graph, then a 4-vertex graph and so on…

QUESTION 4

Is the following graph connected? If it's disconnected, how many different connected sections are there?

a)
b)

QUESTION 5

Give all the simple paths (no cycles) from 1 to 6.

QUESTION 6

Find a simple path that goes through all vertices.

QUESTION 7

Find the shortest path (lowest cost path) to go from vertex 0 to vertex 3. Give both the path and the cost.

QUESTION 8

Here are the distances between different areas around our city.

	Valley East	Sudbury	Lively	Chelmsford	Garson	Onaping Falls
Valley East	0	20	40	25	26	44
Sudbury	20	0	24	24	9	41
Lively	40	24	0	21	39	38
Chelmsford	25	24	21	0	33	19
Garson	26	9	39	33	0	49
Onaping F.	44	41	38	19	49	0

a) Create a graph of this data. Try to place the areas in about the actual areas relate to each other. For example, Valley East should be north of Sudbury. You can always use a map and work overtop it.

b) Can you suggest an optimal (lowest cost) path that starts at one vertex and travels to all other vertices before returning to the starting point?