hazel defs

Question 1

Subgraph

Answer 1

a graph whose vertices and edges belong to the original graph

Question 2

Weight

Answer 2

a number associated with an edge

Question 3

Degree/Valency/Order

Answer 3

number of edges incident to a vertex

Question 4

Path

Answer 4

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 than once

Question 5

Cycle

Answer 5

a closed path

Question 6

Connected Graph

Answer 6

a graph that has a path between all the vertices

Question 7

Digraph

Answer 7

a graph that has edges with directions associated with them

Question 8

Tree

Answer 8

connected graph with no cycles

Question 9

Spanning Tree

Answer 9

a subgraph which includes all the vertices of the original graph and is also a tree

Question 10

Minimum Spanning Tree

Answer 10

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

Question 11

Complete Graph

Answer 11

a graph in which each of the vertices is connected to every other vertex

Question 12

Bipartite Graph

Answer 12

a graph which consists of two sets of vertices, where the edges only join vertices to the other set, not vertices within a set

Question 13

Alternating Path

Answer 13

• a path starting at an unmatched node on one side of the bipartite graph and finishes at an unmatched node on the other side. It uses arcs that are alternately ‘not in’ or ‘in’ the initial matching.

Question 14

Matching

Answer 14

the pairing of some or all of the elements of one set to elements of the second set

Question 15

Complete Matching

Answer 15

every member of one set of a bipartite graph is paired with a member of the other set

Question 16

Total Float

Answer 16

Total Float is the amount of time that an activity can be delayed from its early start date without delaying the project finish date.

Total float = (latest time) – (earliest time) – (duration)

Question 17

Explain why there must always be an even [or zero] number of vertices with odd valency.

Answer 17

• Each arc will add two to the total sum of the valencies of the whole graph.
• Therefore, the sum of the valencies is always even.
• Therefore, vertices with an odd number of valencies must exist in pairs.
• Therefore, there is always an even number of odd valencies.

Question 18

The purpose of dummies

Answer 18

1. E.g. If activity D depends only on activity B but activity E depends on activities B and C.
2. E.g. so that I and J are represented uniquely in terms of their end events.

Question 19

Differences between kruskal and prime

Answer 19

1: For Kruskal’s algorithm you need to sort the edges into ascending order. For Prim’s
algorithm you do not.

2: For Kruskal’s algorithm you choose the shortest edge to start the tree. For Prim’s
algorithm you choose any vertex to start a tree.

3: For Kruskal’s algorithm you add edges to the tree. For Prim’s you add vertices to the
tree.

4: For Kruskal’s algorithm you need to check for cycles. For Prim’s algorithm you do not.

5: For Prim’s algorithm, the tree grows in a connected fashion. Kruskal’s algorithm may be
disconnected until the last edge is added.

6: Prim’s algorithm can be applied to a distance matrix. Kruskal’s algorithm cannot.

Question 20

Explain why it is not possible to transport the statues using fewer crates than 5 bins

Answer 20

There are 5 items over half the bin size (30). No two of these 5 can be paired in a bin, so at least 5 bins will be required.

Question 21

Define traversable and semi traversable (eularian)

Answer 21

A Graph is Traversable if you can go over each edge once and only once, starting and finishing at the same vertex.

A Graph is semi-traversable if you can go over each edge once and only once starting and finishing at different vertices.