GLOSSARY

Question 1

What is the efficiency of an algorithm?

Answer 1

A measure of the ‘run-time’ of the algorithm and in most
cases is proportional to the number of operations that must be carried out (proportional to order/complexity)

Question 2

What is the size of a problem?

Answer 2

A measure of its complexity and so in the case of algorithms on
graphs it is likely to be the number of vertices on the graph.

(In a list it would be the number of items)

Question 3

What is the order of an algorithm?

Answer 3

A measure of its efficiency as a function of the size of the problem

If an algorithm has order f(n), then increasing the size of the problem from n to m will increase the runtime of an algorithm by a factor of f(n)/f(m)

Question 4

How to calculate middle items

Answer 4

1/2(N+1) for odd sets, 1/2(N+2) for even sets

Question 5

What does a graph consist of?

Answer 5

Points (vertices/nodes) which are connected by lines (edges/arcs)

Question 6

What is a subgraph of a graph G?

Answer 6

A graph each of whose vertices belong to G, and edges belong to G

Question 7

What is a weighted graph, and give an alternate name for it

Answer 7

A graph whose edges have a number associated with them,

Also called a network

Question 8

What is the degree/valency of a vertex?

Answer 8

The number of edges incident on it

Question 9

What are odd/even vertices?

Answer 9

Odd vertices have odd degree, even vertices have even degree

Question 10

What is a path?

Answer 10

A finite sequence of edges, such that the end vertex of one edge in the sequence is the start vertex of the next, and in which no vertex appears more then once

Question 11

What is a walk?

Answer 11

A finite sequence of edges such that the end vertex of one edge is the
start vertex of the next.

Question 12

What is a trail?

Answer 12

A walk where no edge is visited more than once

tr”aidgel”

Question 13

What is a cycle/circuit?

Answer 13

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

Question 14

What does it mean for vertices to be connected, and what does it mean for a graph to be connected?

Answer 14

Two vertices are connected if there is a path between them. A graph is connected if all its
vertices are connected.

Question 15

What is a digraph, and what are the edges in a digraph known as?

Answer 15

A digraph contains edges that have a direction associated with them, which are called directed edges

Question 16

What is a tree?

Answer 16

A connected graph with no cycles

Question 17

What is a spanning tree of a graph G?

Answer 17

A subgraph of G containing each vertex of G and is also a tree

Question 18

What is a Eulerian graph?

Answer 18

A graph where every vertex is even

Question 19

What is a semi Eulerian graph?

Answer 19

A graph with exactly 2 odd vertices

Question 20

What is a Eulerian cycle/circuit?

Answer 20

A cycle that contains every arc of the graph ONLY ONCE, returning to the starting vertex

In a circuit number of times visited doesn’t rlly matter

Question 21

What is a Hamiltonian cycle?

Answer 21

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

Question 22

What is a planar graph?

Answer 22

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

Question 23

What makes two graphs isomorphic?

Answer 23

Two graphs are isomorphic if they have the same number of vertices and the degrees of
corresponding vertices are the same

Question 24

What is a tour?

Answer 24

A walk which visits every vertex, returning to its starting vertex

(A closed path)

Question 25

What is Euler’s handshake lemma?

Answer 25

in every finite undirected graph, the number of vertices that touch an odd number of edges is even

As the sum of the degrees of the vertices = 2x the number of edges

Question 26

What is the float of an activity?

Answer 26

The maximum time that the activity can be delayed from its start time, without delaying the finish time of the total project

Question 27

Difference between classical and non classical travelling salesman

Answer 27

Classical - can only traverse each node exactly once

Non Classical - Can visit at least once

Question 28

Difference between chinese postman and travelling salesman

Answer 28

Chinese wants to visit every arc
Salesman wants to visit every node
Both want to start and end at the same point

Question 29

What is a simple graph?

Answer 29

A graph that is undirected and does not have any loops or multiple edges between 2 vertices and at most one arc connecting any two vertices

Question 30

Types of orders of graphs

Answer 30

exponential, linear, factorial, quadratic etc

Question 31

Difference between a distance and adjacency matrix

Answer 31

Distance describes weight of each arc, adjacency describes number of arcs joining corresponding vertices

(Distance matrix only possible with weighted networks)

Question 32

Semi Eulerian graph

Answer 32

One that includes a trail that traverses every arc, but starts and finishes at different vertices

Question 33

Explanation for handshake lemma

Answer 33

(each arc contributes 1 to the orders of two nodes, and so) the
sum of the orders of all the nodes is equal to twice the number of arcs
Which implies that the sum of the orders of all the nodes is even and
therefore there must be an even (or zero) number of vertices of odd
order hence there cannot be an odd number of vertices of odd order

Question 34

If a graph represented a telephone network, why would you want multiple edges?

Answer 34

So an organisation can make multiple phone calls simultaneously.

Question 35

Linear programming cavear

Answer 35

Note the > for “more than”, < for “less than”, ≤ for “no more than” and ≥ for “no less than”

Question 36

Isomorphic meaning

Answer 36

Two graphs are isomorphic when they contain the same number of vertices of the same degree connected in the same way.

Question 37

Planarity check

Answer 37

If arc appears as O in separate list, graph isn’t planar

Question 38

Shape of each box in a flow chart

Answer 38

Oval - start/end
Rectangle - instruction
Diamond - decision