D1

Question 1

Define Hamiltonian Cycle.

Answer 1

A cycle which visits all vertices on a graph.

Question 2

Give an example of a graph which would not have a Hamiltonian Cycle.

Answer 2

A tree.

Question 3

Define Tree.

Answer 3

A graph which connects all vertices but has no cycles.

Question 4

If there is a graph with n vertices, how many distinct cycles will there be if we assume each vertex is connected to every other one?

Answer 4

(n-1)!/2 (As if we have a graph ABCDE then A has 4 options, be has 3 and so on, so 4!. However, this also counts reverse cycles, so we have to half it to get the number of distinct cycles).

Question 5

What is a Eulerian Trail (or cycle)?

Answer 5

A graph which covers every edge of the graph exactly once and finishes at the start vertex.

Question 6

What is the condition for a graph to have a Eulerian Trail?

Answer 6

The graph’s vertices all must have even order.

Question 7

What is a semi-Eulerian Trail?

Answer 7

A path in which you can cover all vertices exactly once, while starting and finishing on different, odd vertices.

Question 8

What is the condition for a graph to have a semi-Eulerian Trail?

Answer 8

The graph must have exactly 2 odd vertices, with the rest being even, so the path can start on one odd vertex and finish on the other.

Question 9

Define traversable.

Answer 9

A graph is traversable if you can cover all edges on a graph without taking the pen off the paper (this is only possible if the graph is a Eulerian or semi-Eulerian graph).

Question 10

Define isomorphic.

Answer 10

2 graphs are isomorphic if they have the same vertices and edges (i.e. Their matrices would be identical).

Question 11

Define digraph.

Answer 11

A digraph is one which has arrows to show direction of its edges. It is important if for example an arc could only go from A to B, to name the arc AB not BA.

Question 12

What is the name for a graph that gives weights (numbers) on its arcs?

Answer 12

A network or weighted graph.

Question 13

What is a distance matrix and an incidence matrix?

Answer 13

A distance matrix is a matrix which denotes the weight of each arc; an incidence matrix defines what is connected to what with no quantities.

Question 14

How to we find the number of edges from a matrix (which is NOT a digraph)

Answer 14

We sum up all the values in the matrix and divide them by 2.

Question 15

Define valency.

Answer 15

Another word for order, the valency is the number of edges connected to a certain vertex.

Question 16

What sort of algorithm/complexity of the algorithm is bubble sort?

Answer 16

Quadratic complexity (or has an order of n^2) due to the maximum number of comparisons being n/2(n-1).

Question 17

Define complete enumeration.

Answer 17

Solving a problem by listing all the possible combinations and choosing the best one from that list.

Question 18

Define a heuristic algorithm.

Answer 18

An efficient algorithm which will get us a good (if not perfect) result.

Question 19

Give an advantage and disadvantage of a heuristic algorithm.

Answer 19

Advantage: can give us a solution from large groups in which it would take far too long to guess.
Disadvantage: it may not always give the optimal solution.

Question 20

Outline briefly the first-fit algorithm.

Answer 20

We leave the items in the order given and place them in the first available bin with enough space.

Question 21

Outline briefly the binary first-fit decreasing algorithm.

Answer 21

Items are ordered in descending order of size first, then fit into the first available bin with enough space.

Question 22

Outline briefly the full bin-packing algorithm.

Answer 22

Judging by eye, we place items into sets which will fully (or very nearly fully) fill a bin, and pack them accordingly.

Question 23

How do we find the middle item in a list?

Answer 23

1/2(N+1) if N is odd, and 1/2(N+2) if N is even.