Decision 1 Definitions

Question 1

Graph

Answer 1

Consists of vertices which are connected by edges.

Question 2

Subgraph

Answer 2

Part of a graph.

Question 3

Weighted graph

Answer 3

Graph in which there is a number associated with each edge.

Question 4

Degree of valency/order

Answer 4

Number of edges incident to a vertex.

Question 5

Path

Answer 5

Finite sequence of edges. End vertex of one edge in the sequence is the start vertex of the next. No vertex appears more than once.

Question 6

Walk

Answer 6

Path which you are allowed to return to vertices more than once.

Question 7

Cycle

Answer 7

Closed ‘path’. End vertex of last edge is start vertex of first edge.

Question 8

Connected

Answer 8

Two vertices are connected if there is path between them. Connected graph= all its vertices are connected.

Question 9

Loop

Answer 9

Edge that starts and finishes at the same vertex.

Question 10

Simple graph

Answer 10

Graph with no loops and not more than one edge connecting any pair of vertices.

Question 11

Digraph

Answer 11

Graph with edges that have direction associated with them- edges=connected edges.

Question 12

Tree

Answer 12

Connected graph with no cycles.

Question 13

Spanning tree

Answer 13

Subgraph of a graph which includes all vertices of the graph and is also a tree.

Question 14

Bipartite graph

Answer 14

Graph consisting of two sets of vertices, X and Y. Edges only join vertices in X to vertices in Y, not vertices within a set.

Question 15

Complete graph

Answer 15

Graph in which every vertex is directly connected by an edge to each of the other vertices. If graph has n vertices, connected graph is denoted k(n subscript).

Question 16

Complete partite graph

Answer 16

Graph in which there are r vertices in set X and s vertices in set Y (denoted K(r,s subscript).

Question 17

Isomorphic graph

Answer 17

Graph showing same information as another but which is drawn differently.

Question 18

Distance matrix

Answer 18

Matrix which records the weights on the edges. No weight is indicated by ‘-‘.

Question 19

Minimum spanning tree

Answer 19

A spanning tree such that the total length of its arcs is as small as possible.

Question 20

Early time

Answer 20

Earliest time of arrival at event allowing for completion of all preceding activities.

Question 21

Late time

Answer 21

Latest time that event can be left without extending the time needed for project.

Question 22

Critical activity

Answer 22

Activity where any increase in its duration results in a corresponding increase in the duration of the whole project.

Question 23

Critical path

Answer 23

Path from source to sink which entirely follows critical activities. Longest path in network.

Question 24

Total float

Answer 24

Total float, F (i, j) of activity (i, j) is defined to be F(i, j)=l(sub j) - e(sub i) - duration (i, j), where e(sub i) is the earliest time for event i and l(sub j) is the latest time of event j.

Question 25

Matching

Answer 25

Matching is the 1 to 1 pairing of some, or all, of the elements of one set (X) with elements of second set (Y) in bipartite graph.

Question 26

Maximal matching

Answer 26

Matching in which number of arcs is as large as possible.

Question 27

Complete matching

Answer 27

1 to 1 pairing of all elements of one set, X, with elements of second set, Y, in bipartite graph.

Question 28

Alternating path

Answer 28

Path starting at unmatched node on one side of bipartite graph and finishes at unmatched node on other side. Uses arcs that alternatively ‘not in’ or ‘in’ the initial matching.

Question 29

Why dummy?

Answer 29

(One dependent on one, another on two) so that the 2 events can be described uniquely in terms of their end events.

Question 30

RI: which node should end and why?

Answer 30

“CE” is shortest. So repeat “CE”. Thus start and end at “D” or “G”.

Question 31

3 differences between Prim and Kruskal.

Answer 31

1) K starts with shortest arc. P starts with any node.
2) K adds arcs, whereas P adds nodes to growing tree.
3) P can use distance matrix.

Question 32

Explain why there must always be an even number of vertices with odd valency in every graph.

Answer 32

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

Question 33

Find max number of comparisons in bubble sort.

Answer 33

For list of n numbers, max no. of passes = (n-1). Max no. of swaps= (n-1) + (n-2)+…+1. Thus n(n-1)/2 is max number of comparisons.