A graph is a finite set of vertices (dots) connected by edges.Theorem: The sum over all vertices of the degrees = 2 * number of edges.
The degree (valence) of a vertex is the number of edges incident to the vertex.
A path is a connected sequence of edges.Euler's Theorem 1: Suppose G is a connected graph. Equivalent:
A graph is connected if and only if for every pair of vertices there is a path in the graph between them.
A circuit (cycle) is a path that starts and ends at the same point.
An Eulercircuit is a circuit that traverses each edge exactly once.
An Eulerpath is a path that traverses each edge exactly once, and is not a circuit.Euler's Theorem 2: Suppose G is a connected graph. Equivalent:
To Eulerize a graph is to add edges to a graph so
has an Eulercircuit.
A Hamiltonian Circuit is a circuit that visits every vertex exactly once.
A complete graph on n vertices is a graph that has exactly one edge between any two vertices.
A graph is bipartite if the vertices can be grouped into two sets S and T, so that every edge in the graph has one endpoint in S and the other in T.
Nearest Neighbor Algorithm:
start from home
visit the nearest neighbor that hasn't been visited yet
return to home when no other choice is available
Sorted Edge Algorithm
sort the edges by increasing weight
choose the edge with lowest weight such that
1. it never requires that 3 used edges meet at a vertex
2. it never closes up a circular tour that doesn't include all vertices
a tree is a graph that does not contain a circuit.Kruskal's Algorithm: for finding a minimum cost spanning tree
Order Requirement Directed Graph (Digraph): it tells you what has to be done before something else can be started.
the path with the longest duration is the critical path.
A task is ready at a particular time, if all its predecessors in the requirement digraph have been completed.
List Processing Algorithm
repeat until all tasks are done:
assign the first ready and not yet assigned task on the priority list to the lowest numbered processor
Critical Path Scheduling Algorithm
repeat until no more vertices are left in the directed graph:
find task that heads a critical path (break tie by choosing the task with the lower number)
place task next on the priorities list
remove task from the directed graph
Decreasing Time List Processing Algorithm
sort the tasks in order of decreasing time lengths to get a priority list
apply the list processing algorithm
see if next object fits into the current bin
if yes -- put it in
if no -- move to next bin and put it in there and make that bin the current one
fit the next object into the first among the currently used bin where it fits.
Fit the next object into the currently used and not yet filled bin with the most open space.
Decreasing Time Heuristics:
sort the object list by decreasing weight and apply the previous heuristics.
Vertex Coloring: color the vertices so that no two
an edge are colored with the same color.
The chromatic number is the least number of colors needed to do the vertex coloring.