Decision Year 1 Terms

Question 1

Algorthim

Answer 1

A finite sequence of instructions for solving a problem.

Question 2

Bipartite graph

Answer 2

A graph with two sets of nodes such that arcs only connect to nodes from one set to the other.

Question 3

Complete graph, Kn

Answer 3

A simple graph such that each of its n nodes is directly connected by an arc to every other node.

Question 4

Connected graph

Answer 4

A graph such there is a path between any two nodes of the graph.

Question 5

Cycle

Answer 5

A closed trail where only the initial and final nodes are the same.

Question 6

Digraph

Answer 6

A graph with directed arcs.

Question 7

Euler’s relationship

Answer 7

R + N = A + 2

Question 8

Eulerian graph

Answer 8

A connected graph which has a closed trail containing every arc precisely once.

Question 9

Graph

Answer 9

A set of points (called nodes or vertices) joined by lines (called arcs or edges).

Question 10

Greedy algorthim

Answer 10

An algorithm where the immediately ‘best’ step is made without any concern about the long-term consequences of this choice.

Question 11

Hamiltonian cycle

Answer 11

A cycle which passes through every node on a graph.

Question 12

Minimum connector

Answer 12

A spanning tree whose arcs have the minimum possible total weight.

Question 13

Network

Answer 13

A graph with numbers (called weights) associated with its arcs.

Question 14

Order (of a node)

Answer 14

The number of arcs meeting at that node.

Question 15

Order (of an algorithm)

Answer 15

A measure of the ‘run-time’ of the algorithm as a function of the size of the problem.

Question 16

Path

Answer 16

A trail such that no node is passed more than once.

Question 17

Planar graph

Answer 17

A graph which can be drawn in a plane in such a way that arcs only meet at nodes.

Question 18

Semi-Eularian graph

Answer 18

A connected graph with a trail which is not closed that contains every arc precisely once.

Question 19

Simple graph

Answer 19

A graph without loops or multiple arcs.

Question 20

Spanning tree

Answer 20

A subgraph which is a tree connecting all the nodes of the graph.

Question 21

Subgraph of G

Answer 21

A graph whose nodes and arcs are all in the graph G.

Question 22

Trail

Answer 22

A sequence of arcs such that the end node of one arc is the start node of the next.

Question 23

Travelling salesperson problem

Answer 23

A classical problem of finding a Hamiltonian cycle of minimum weight. (In the practical problem, nodes and arcs may be revisited).

Question 24

Tree

Answer 24

A connected graph with no cycles.