Yr2 Graphs And Trees

Question 1

What components are graphs made up of?

Answer 1

Graphs are made of two components: nodes (or vertices) and edges.

Question 2

What is a weighted graph?

Answer 2

A graph that has labels such as distance between nodes, as this ‘weights’ which option should be taken.

Question 3

What’s an adjacency matrix?

Answer 3

A method for representing all the connection in a graph using a table with a one and a zero in the coordinate corresponding to each connection.

Question 4

What’s an adjacency list?

Answer 4

A two column table with each node listed down the left column and each of its adjacent vertices listed in the right.

Question 5

When should adjacency lists be used over adjacency matrixes?

Answer 5

When the graph is sparse i.e. there aren’t many connections between nodes and the connections are only one way. This is to efficiently use storage space.

Question 6

What is a tree?

Answer 6

A connected, undirected graph with no cycles

Question 7

What is a rooted tree?

Answer 7

A tree in which one vertex at the top is designated as the root and all other vertices connect to it

Question 8

What is the explorers problem?

Answer 8

A route that traverses each edge once before returning to the start

Question 9

What is the travellers problem?

Answer 9

A route that visits each vertex once before returning to the start

Question 10

What is a parent node?

Answer 10

The node on a rooted tree from which the child node stems

Question 11

What is a leaf node?

Answer 11

A node with no child nodes

Question 12

What is a binary tree?

Answer 12

A rooted tree where each parent node can have at most two child nodes

Question 13

What are the three types of tree traversals?

Answer 13

PreOrder
PostOrder
InOrder

Question 14

How to carry out preOrder traversal?

Answer 14

Start from root node and go left when you are on the left of a node write it down

Question 15

How do you carry out an inOrder traversal?

Answer 15

Start from root node and go left when you are on the base of a node write it down

Question 16

How do you carry out a postOrder traversal?

Answer 16

Start from root node and go left when you are on the right of a node write it down

Question 17

What is a good way of remembering the traversals?

Answer 17

preOrder - is on the left (before)
postOrder - is on the right (after)
inOrder - is in the middle