D1

Question 1

Activity Network

Answer 1

A network that shows the order in which activities must be completed. Activities are shown by arcs and their competition is shown by nodes.

Question 2

Adjecency matrix

Answer 2

A matrix (number grid) that shows the number of links between each pair of vertices in a graph.

Question 3

Algorithm

Answer 3

A set of instructions for solving a problem.

Question 4

Alternating path

Answer 4

A way of improving an initial matching.

Question 5

Arc

Answer 5

The line connecting two vertices of a graph. Also called an edge.

Question 6

Binary search

Answer 6

A searching algorithm used to find items in an ordered list.

Question 7

Bipartide graph

Answer 7

A graph with two sets of nodes, joined by arcs. The arcs only join nodes from one set of nodes in the other.

Question 8

Breakthrough

Answer 8

Reaching an unmatched node using the alternating path method.

Question 9

Bubble sort.

Answer 9

An algorithm that sorts a list into oprder by systematically swapping them.

Question 10

Chinease postman problem

Answer 10

Another name for the route inspection problem.

Question 11

Complete graph

Answer 11

A graph where every vertex has a direct connection to every other vertex.

Question 12

Complete matching

Answer 12

A matching with teh same number of arcs as there are nodes in each set.

Question 13

Connected graph

Answer 13

A graph where every vertex is connected to every other vertex by a path (not necessarily a direct arc).

Question 14

Constraint

Answer 14

A limiting factor in a linear programming problem. Usually written as an inequality interms of the decision variables.

Question 15

Critical activity

Answer 15

An activity in an activity network that must be started as soon as possible or the entire project will be delayed.

Question 16

Critical path

Answer 16

A set of critical activities that run from source node to the sink node.

Question 17

Cycle

Answer 17

A closed path through a graph that brings you back to your starting point. Also called a circuit.

Question 18

Decision variable

Answer 18

An item that’s being produced, bought, sold, etc. in a linear programming problem.

Question 19

Degree

Answer 19

The number of arcs connected to a vertex.

Question 20

Digraph

Answer 20

A graph in which some arcs have a direction (known as directed edges).

Question 21

Dijkstra’s algorithm

Answer 21

A method for finding the shortest path between two vertices of a network.

Question 22

Distance matrix

Answer 22

A matrix (number grid) thats shows the distance (or weight) between each pair of vertices in a graph.

Question 23

Dummy

Answer 23

A dummy shows precedence in an activity network without adding any activities to the project.

Question 24

Early event time

Answer 24

The earliest an activity within a project can possibly be started.

Question 25

Edge

Answer 25

A line connecting two vertices of a graph. Also called an arc.

Question 26

Eularian graph

Answer 26

A graph in which every vertex is even.

Question 27

Even vertices

Answer 27

A vertex with an even degree.

Question 28

Feasible region

Answer 28

An area on a graph in which all points are feasible solutions to a linear programming problem.

Question 29

Feasible solution

Answer 29

A set of values that satisfies all the constraints in a linear programming problem.

Question 30

First-fit algorithm

Answer 30

An algorithm used to pack items into bins.

Question 31

First-fit decreasing algorithm

Answer 31

A bin-packing algorithm similar to the first-fit algorithm, but used on an ordered list.

Question 32

Float

Answer 32

The amount of time you can delay an activity for without delaying the project it is part of.

Question 33

Flow chart

Answer 33

A way of visually representing an algorithm.

Question 34

Gantt chart

Answer 34

A diagram that shows the time intervals in which activities can take place. Used for scheduling activities.

Question 35

Graph

Answer 35

A diagram made up of nodes joined by arcs.