Vocab

Question 1

Graph

Answer 1

A group of vertices connected by arcs

Question 2

Subgraph

Answer 2

A graph where all vertices and edges belong to another graph

Question 3

Degree

Answer 3

Number of edges incident to a vertex

Question 4

Valency

Answer 4

Number of edges incident to a vertex

Question 5

Path

Answer 5

A route along edges where no vertex is visited more than once

Question 6

Walk

Answer 6

A route along a graph through edges from one vertex to the next

Question 7

Trail

Answer 7

A route along edges where no edge is visited more than once

Question 8

Cycle

Answer 8

A route along edges where the end vertex is the same as the start vertex AND no vertex is visited more than once

Question 9

Hamiltonian cycle

Answer 9

A route along edges that includes EVERY vertex only once, and returns to its start vertex

Question 10

Eulerian cycle

Answer 10

A route along edges where no edge is visited more than once, and starts and finishes at the same vertex, AND ALL EDGES ARE INCLUDED

Question 11

Connected graph

Answer 11

A graph where there is a path between any two vertices

Question 12

Loop

Answer 12

An edge that starts and finishes at the same vertex

Question 13

Simple graph

Answer 13

One where there are no loops AND not more than one edge connecting any pair of vertices

Question 14

Digraph

Answer 14

Edges have directions associated with them

Question 15

Explain why total valency must be even

Answer 15

Each edge adds 2 to the total valency, so the total valency will always be a multiple of 2

Question 16

Euler’s Handshaking lemma

Answer 16

Sum of degrees = 2 x number of edges

Question 17

Eulerian graph order of vertices

Answer 17

Every vertex has even degree

Question 18

semi eulerian graph

Answer 18

Exactly two vertices have an odd degree

Question 19

Order of an algorithm

Answer 19

Measure of an algorithm’s efficiency as a function of the size of the problem

Question 20

Efficiency of an algorithm

Answer 20

measure of the ‘run-time’ of the algorithm and in most cases is proportional to the number of operations that must be carried out.

Question 21

Weighted graph

Answer 21

Graph where numbers are associated with each edge

Question 22

Tree

Answer 22

Connected graph with no cycles

Question 23

Spanning tree

Answer 23

Subgraph which includes all vertices of G and is a connected graph with no cycles

Question 24

Planar graph

Answer 24

A graph that can be drawn on a single plane so that no edges cross each other

Question 25

2 Isomorphic graphs

Answer 25

Same number of vertices and degrees of corresponding vertices are the same

Question 26

Walk

Answer 26

a finite sequence of edges such that the end vertex of one edge is the start vertex of the nex

Question 27

Tour

Answer 27

A finite sequence of edges that visits every vertex and returns to its start vertex

Question 28

Travelling salesman problem

Answer 28

‘find a route of minimum length which visits every vertex in an undirected network’.

Question 29

Classical vs practical travelling salesman

Answer 29

Classic - vertex visited once only Practical - a vertex may be revisited

Question 30

Explain why calculation of time of algorithm is only an approximation

Answer 30

Order of f(n) doesn’t mean order is necessarily proportional to f(n), may be a dominant term so there are other terms affecting time

Question 31

Order of Dijkstra

Answer 31

Cubic

Question 32

Order of bubble sort

Answer 32

Quadratic

Question 33

Order of first fit decreasing

Answer 33

Quadratic

Question 34

Order of quick sort (wosrt case)

Answer 34

Quadratic

Question 35

Prim’s order (worst case)

Answer 35

Cubic

Question 36

Minimum number of bubble sort passes and wen

Answer 36

1 - if items already in order

Question 37

Maximum number of passess needed for bubble sort and when

Answer 37

n if the smallest is at the end of the list

Question 38

In a list of n items, how many pairs need to be compared in bubble sort?

Answer 38

n - 1

Question 39

,Maximum number of comparisons for quick sort

Answer 39

= (n -1) + (n - 2) +…+ 2 + 1 = (n(n-1))/2

Question 40

Factor of time increase algorithm increase from n to m times

Answer 40

f(m)/f(n)

Question 41

Number of comparisons for bubble sort in: a) First pass b) Second pass c) Sixth pass d) Final comparison in worst case

Answer 41

a) n - 1 b) n - 2 c) n - 6 d) 1