AQA A2 Computing 2.5 Graphs and Trees

Question 1

Graph

Answer 1

a diagram consisting of circles, called vertices, joined by lines, called edges or arcs; each edge joins exactly two vertices

Question 2

Neighbours

Answer 2

two vertices are neighbours if they are connected by an edge

Question 3

Degree

Answer 3

of a vertex, the number of neighbours for that vertex

Question 4

Labelled or weighted graph

Answer 4

a graph in which the edges are labelled or given a value called a weight

Question 5

Automation

Answer 5

turning an abstraction into a form that can be processed by a computer

Question 6

Directed graph or digraph

Answer 6

a diagram consisting of circles, called vertices, joined by directed lines, called edges.

Question 7

Simple graph

Answer 7

an undirected graph without multiple edges and in which each edge connects two different vertices

Question 8

Exoplorer’s problem

Answer 8

the solution finds a route that traverses each road exactly once before returning to the starting point

Question 9

Traveller’s problem

Answer 9

the solution finds a route that visits each city exactly once before returning to the starting point

Question 10

Closed path or circuit

Answer 10

a sequence of edges that starts and ends at the same vertex and such that any two successive edges in the sequence share a vertex

Question 11

Cycle

Answer 11

a closed path in whch all the edges are different and all the intermediate vertices are different

Question 12

Tree

Answer 12

a connected undirected graph with no cycles

Question 13

Rooted tree

Answer 13

a tree in which one vertex has been designated as the root and every edge is directed away from the root