Terminology

Question 1

A tree

Answer 1

A connected graph with no cycles e.g. Probability tree

Question 2

A spanning tree

Answer 2

A subgraph that includes all the vertices of the graph and is also a tree

Question 3

A complete graph Kn

Answer 3

Has n vertices where all the vertices are connected by an edge to each of the other vertices

Question 4

A bipartite graph

Answer 4

Two sets of vertices (X and Y) where edges only join vertices in X to Y, not within their set

Question 5

A planar graph

Answer 5

A graph which can be drawn in a plane so that no two edges meet each other, except at a vertex to which they are both incident

Question 6

Isomorphic

Answer 6

If two graphs have the same number of vertices and the degrees of the corresponding vertices are the same

Question 7

Network

Answer 7

A graph with weighted edges

Question 8

Triangle inequality

Answer 8

If weight BC is less than or equal to weight AB + AC for all sets of three vertices (ABC) then it satisfies this

Question 9

Path

Answer 9

A finite sequence of edges such that the end vertex of one edge is the start vertex of the next. No vertex appears more than once

Question 10

Cycle

Answer 10

A closed path, the end vertex of the last edge is the start vertex of the first edge

Question 11

Hamiltonian cycle

Answer 11

A cycle that passes through every vertex of the graph once and only once, and returns to its start vertex

Question 12

Eulerian cycle

Answer 12

A cycle that includes every edge of a graph exactly once

Question 13

Edge set

Answer 13

Set of all edges

Question 14

Vertex set

Answer 14

Set of all vertices

Question 15

Graph

Answer 15

A collection of nodes (or vertices) which are connected by arcs (or edges)

Question 16

Subgraph

Answer 16

A subset of the vertices together with a subset of the edges

Question 17

Two connected vertices

Answer 17

Two vertices with a path inbetween them

Question 18

Connected graph

Answer 18

All of the vertices are connected

Question 19

Loop

Answer 19

An edge with the same vertex at each end

Question 20

Simple graph

Answer 20

Does not contain any ‘parallel’ arcs nor any loops

Question 21

Degree (or valency or order) of a vertex

Answer 21

The number of edges connected to it

Question 22

Directed edges

Answer 22

The edges of a graph have a direction associated with them

Question 23

Digraph

Answer 23

When the edges of a graph have a direction associated with them

Question 24

Kr,s

Answer 24

Bipartite graph where every vertex in x is joined to every vertex in y and vice versa

Question 25

Matching

Answer 25

A one to one pairing of some or all of the vertices in set X with vertices in set Y

Question 26

Linear programming

Answer 26

A method of maximising or minimising a variable subject to constraints

Question 27

Critical path

Answer 27

Critical activities from source node to sink node

Question 28

Critical activity

Answer 28

It’s duration cannot be increased without increasing the duration of the whole project

Question 29

Decision variables

Answer 29

The axis labelled on the graph

Question 30

Slack

Answer 30

How much delay between finishing one activity and starting another

Question 31

Constraints

Answer 31

Inequalities shown on a graph

Question 32

Gantt chart

Answer 32

Earliest possible start, latest possible finish

Question 33

Feasible region

Answer 33

Area which satisfies the constraints