Decision Revision

  • Created by: becca159
  • Created on: 15-06-16 13:44

Bin Packing Lower Bound

Sum of weights/heights                                                                                                             capacity of bin

1 of 17


A graph is made up of points (called vertices/nodes) joined by lines (called edges/arcs).

2 of 17


A subgraph of graph G is a graph where all the vertices and edges belong to G. 

3 of 17

Degree / Valency

The degree or valency of a vertex is the number of edges connected to it. 

4 of 17


A path is just a route in the graph. A path is a sequence of edges that flow on, end to end. You can't go through a vertex more than once. 

5 of 17


A cycle is a path that brings you back to your starting point. It is a closed path, the end vertex is the same as the start vertex. 

6 of 17


Trees are graphs that have no cycles. 

7 of 17

Spanning Trees

Spanning trees are subgraphs that are also trees. They have to include all of the vertices. 

8 of 17

Minimum Spanning Tree

A minimum spanning tree is a spanning tree where the total length of the arcs is as small as possible. 

9 of 17

Eularian Graphs

If all the vertices in a graph have an even degree/valency, the graph is eularian.

10 of 17

Semi-Eularian Graphs

If exactly two vertices have an odd degree, and the rest are even, the graph is semi-eularian. 

11 of 17


Dummies help show the order that activities must be done in. Dummy activities aren't real activitites, they just show that one real activity depends on another real activity when it can't be shown clearly otherwise. 

12 of 17

Early Event Time

The earliest time you can reach an event. It depends on the durations of the preceding activities.

13 of 17

Late Event Time

The latest time you can get to an event without increasing the duration of the entire project. 

14 of 17

Critical Activity

If the duration of a critical activity increases, the duration of the whole project increases by the same amount. 

15 of 17

Critical Path

A critical path runs from the source node to the sink node and is made up of critical activities. 

16 of 17

Number of Workers Lower Bound

Sum of all activity durations                                                                                                        critical time of project

17 of 17


No comments have yet been made

Similar Mathematics resources:

See all Mathematics resources »See all Networks, algorithms and problem solving resources »