D1 summary

Chapter 1 summary - Algorithms

1. An algorithm is a set of precise instructions which if followed will solve a problem.
   
   
2. The bubble-sort algorithm
   To sort a list compare adjacent members of the list, moving from left to right, and switch them if they are in the wrong order. Continue this process until a pass produces no change in the list.
   
   
3. The quick-sort algorithm
   

   Step 1	Select a specific number (the pivot) from the list, say the middle one.
   Step 2	Write all the numbers smaller than the pivot to the left of the pivot, reading the original list from left to right, and so create a sublist L_1. Write all the numbers larger than the pivot to the right of the pivot, reading the original list from left to right, and so create a sublist L_2.
   Step 3	Apply step 1 and 2 to each sublist until all the sublists contain only one number.

   
   
4. First-fit algorithm
   Taking the boxes in the order listed place the next box to be packed in the first available bin that can take that box.
   
   
5. First-fit decreasing algorithm
   

   Step 1	Reorder the boxes in decreasing order of size.
   Step 2	Apply the first-fit algorithm to the reordered list.

   
   
6. Binary-search algorithm
   May be applied to search a list of names in alphabetical order or a list of numbers in ascending order.
   

   Step 1	Compare the required item with the middle item in the list. If this is the required item then the search is complete. If the required item is before the middle item then consider the top half of the list. If the required item is after the middle item then consider the bottom half of the list.
   Step 2	Apply step 1 to the top half of the list in case (i) or to the bottom half of the list in case (ii).
   Stop	Either when the required item is located or when it has been shown that the required item is not in the list.

Chapter 2 summary - Graphs and networks

1. A graph G consists of a finite number of points (usually called vertices or nodes) connected by lines (usually called edges or arcs).
   
   
2. A path is 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.
   
   
3. A cycle (or circuit) is a closed path, i.e. the end vertex of the last edge is the start vertex of the first edge.
   
   
4. A Hamiltonian cycle is a cycle that passes through every vertex of the graph once and only once, and returns to its start vertex.
   
   
5. A Eulerian cycle is a cycle that includes every edge of a graph exactly once.
   
   
6. The vertex set is the set of all vertices of a graph.
   
   
7. The edge set is the set of all edges of a graph.
   
   
8. A subgraph of a graph is a subset of the vertices together with a subset of edges.
   
   
9. Two vertices are connected if there is a path between them.
   
   
10. A graph is connected if all pairs of its vertices are connected.
    
    
11. A simple graph is one in which there is no edge with the same vertex at each end, i.e. no loops, and not more than one edge connecting any pair of vertices. A complete graph is one in which every vertex is connected by an edge to each of the other vertices.
    
    
12. The degree (or valency or order) of a vertex is the number of edges connected to it.
    
    
13. If the edges of a graph have a direction associated with them they are known as directed edges, and the graph is known as a digraph.
    
    
14. A tree is a connected graph with no cycles.
    
    
15. A spanning tree of a graph G is a subgraph that includes all the vertices of G and is also a tree.
    
    
16. A bipartite graph consists of two sets of vertices, X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set.
    
    
17. If there are r vertices in X and s vertices in Y and every vertex in X is joined to every vertex in Y then the graph is called {\rm K}_{r,s}.

Chapter 3 summary - Algorithms on graphs

1. A minimum spanning tree of a connected and undirected graph is a spanning tree such that the total length of its edges is as small as possible. (This is sometimes called a minimum connector.)
   
   
2. Kruskal's algorithm builds a minimum spanning tree by adding one edge at a time to build a subgraph. At each stage the edge of smallest weight is chosen provided that it does not create a cycle with edges already chosen.
   
   
3. Prim's algorithm builds a minimum spanning tree by adding one vertex at a time to a connected subgraph. The new vertex to be added is the one which is nearest to any vertex already in the subgraph.
   
   
4. Dijkstra's algorithm obtains the shortest route from the initial vertex to any other vertex in a network. At each stage a fresh vertex is assigned a final label which gives the shortest distance from the initial vertex to that vertex.

Chapter 4 summary - The route inspection problem

1. A traversable graph is one that can be drawn without removing your pen from the paper and without going over the same edge twice.
   
   
2. If a graph is not Eulerian but there is a route starting and finishing at different vertices and traversing every edge once and only once then the graph is semi-Eulerian.
   
   
3. If in a graph there is a route that starts and finishes at the same vertex and traverses every edge once and only once then the graph is Eulerian.
   
   
4. The handshaking theorum
   The sum of the valencies, taken over all the vertices of a graph G, is equal to twice the number of edges.
   
   
5. The route inspection problem
   In a given undirected network a route of minimum weight has to be found that traverses every edge at least once, returning to the starting vertex.

Chapter 5 summary - Critical path analysis

1. The nodes represent events.
   
   
2. The arcs represent activities.
   
   
3. The weights represent the duration of the corresponding activity.
   
   
4. The source node represents the beginning of the project.
   
   
5. The sink node represents the end of the project.
   
   
6. The earliest time e_i for node i is the earliest time we can arrive at event i.
   
   
7. The latest time l_i for node i is the latest time we can leave event i without extending the length of the critical path.
   
   
8. The critical path is the longest path through the network from the source node to the sink node.
   
   
9. Events i for which e_i = l_i are critical events.
   
   
10. Activities (i,j) for which l_j - e_i - [\text {duration} (i,j)] = 0 are critical activities.
    
    
11. For activity (i,j) of duration a_{ij}:
    
    the earliest start time is e_i
    the earliest finish time is e_i+a_{ij}
    the latest finish time is l_j
    the latest start time is l_j - a_{ij}
    the total float on activity (i,j) is l_j - e_i - a_{ij}

Chapter 6 summary - Linear programming

1. Any pair of values of x and y that satisfy all the constraints in a linear programming problem is called a feasible solution.
   
   
2. The region that contains all feasible solutions is called the feasible region.
   
   
3. The optimal solution of a linear programming problem, if it exists, will occur at one or more of the extreme points (vertices) of the feasible region.
   
   
4. The simplex method is an algebraic method for solving linear programming problems.
   
   1. The column that contains the entering variable is called the pivotal column.
   2. The row with the smallest \theta-value is called the pivotal row.
   3. The entry at the intersection of the pivotal row and the pivotal column is called the pivot.
   
   
5. Optimality condition:
   If the objective row of a tableau has zero entries in the columns labelled by basic variables and no negative entries in the columns labelled by non-basic variables then the solution represented by the tableau is optimal.

Chapter 7 summary - Matchings

1. A bipartite graph consists of two sets of vertices X and Y. The edges only join vertices in X to vertices in Y, not vertices within a set.
   
   
2. A matching in a bipartite graph is a subset M of the edges of the graph G such that no two edges in M have a common vertex.
   
   
3. A maximal matching M is a matching in which the number of edges is as large as possible.
   
   
4. In a bipartite graph, with n vertices in each set a complete matching M is a matching in which the number of edges is also n.
   
   
5. An alternating path for a matching M in G is a path in G with the following properties:
   
   1. it joins an unmatched vertex in X to an unmatched vertex in Y
   2. it is such that edges in the path are alternately in and not in the matching M.
   
   
6. The matching improvement algorithm
   

   Step 1	Start with any non-trivial matching M in G.
   Step 2	Search for an alternating path for M in G.
   Step 3	If an alternating path is found, construct a better matching M' by changing the status of the edges in the alternating path and return to step 2 with M' replacing M.
   Step 4	Stop when no alternating path can be found. The matching obtained is maximal.

Chapter 8 summary - Flows in networks

1. A network is a weighted digraph in which the weight on each arc represents the capacity of that arc.
   
   
2. A vertex {\rm S} is called a source if all arcs containing {\rm S} are directed away from {\rm S}.
   
   
3. A vertex {\rm T} is called a sink if all arcs containing {\rm T} are directed towards {\rm T}.
   
   
4. A flow in a network {\rm N} with a single source {\rm S} and a single sink {\rm T} is an assignment to each arc {\rm e} of {\rm N} of a non-negative number called the flow along the arc {\rm e}.
   A flow must satisfy two conditions:
   
   • The feasibility condition, which states that the flow along each arc cannot exceed the capacity of that arc.
   • The conservation condition, which states that for every intermediate vertex {\rm V} (not {\rm S} or {\rm T}), the sum of the flows into {\rm V} is equal to the sum of the flows out of {\rm V}.
5. If the flow along an arc is equal to the capacity of that arc the arc is said to be saturated. If an arc is not saturated it is said to be unsaturated.
   
   
6. A flow-augmenting path in a capacitated network with a single source {\rm S} and a single sink {\rm T} is a path from {\rm S} to {\rm T} consisting of:
   
   • forward arcs - unsaturated arcs directed along the path.
   • backward arcs - arcs directed against the direction of the path and carrying a non-zero flow.
   
   
7. In any capacitated network with a single source {\rm S} and a single sink {\rm T}, the value of a maximal flow is equal to the capacity of a minimum cut.
   
   
8. The maximum flow algorithm is as follows:
   

   Step 1	Obtain an initial flow by inspection.
   Step 2	Find flow-augmenting paths using the labelling procedure until no further flow-augmenting paths can be found.
   Step 3	Check that the flow obtained is maximal by finding a cut whose capacity is equal to the value of the flow.

   
   
9. A network with multiple sources {\rm S}_1, {\rm S}_2, ... , {\rm S}_m and multiple sinks {\rm T}_1, {\rm T}_2, ... , {\rm T}_n can be reduced to a network with only one source and one sink by introducing a supersource {\rm S} and a supersink {\rm T}. Arcs {\rm SS}_1, {\rm SS}_2, ..., {\rm SS}_m are added from the supersource {\rm S} to the sources {\rm S}_1, {\rm S}_2, ... , {\rm S}_m. Arcs {\rm T}_1{\rm T}, {\rm T}_2{\rm T}, ... , {\rm T}_n{\rm T} are added from sinks {\rm T}_1, {\rm T}_2, ... , {\rm T}_n to the supersink {\rm T}. The capacities of the new arcs can be considered to be infinite.