Bin Packing Lower Bound
Sum of weights/heights capacity of bin
A graph is made up of points (called vertices/nodes) joined by lines (called edges/arcs).
A subgraph of graph G is a graph where all the vertices and edges belong to G.
Degree / Valency
The degree or valency of a vertex is the number of edges connected to it.
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.
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.
Trees are graphs that have no cycles.
Spanning trees are subgraphs that are also trees. They have to include all of the vertices.
Minimum Spanning Tree
A minimum spanning tree is a spanning tree where the total length of the arcs is as small as possible.
If all the vertices in a graph have an even degree/valency, the graph is eularian.
If exactly two vertices have an odd degree, and the rest are even, the graph is semi-eularian.
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.
Early Event Time
The earliest time you can reach an event. It depends on the durations of the preceding activities.
Late Event Time
The latest time you can get to an event without increasing the duration of the entire project.
If the duration of a critical activity increases, the duration of the whole project increases by the same amount.
A critical path runs from the source node to the sink node and is made up of critical activities.
Number of Workers Lower Bound
Sum of all activity durations critical time of project