Definitions and Algorithms 1

A graph is a finite set of vertices (dots) connected by edges.
The degree (valence) of  a vertex is the number of edges incident to the vertex.
Theorem: The sum over all vertices of the degrees = 2 * number of edges.
A path is a connected sequence of edges.
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.
Euler's Theorem 1: Suppose G is a connected graph. Equivalent:
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: Theorem: A bipartite graph, where the sets S and T have an unequal number of vertices, doesn't have a Hamiltonian circuit.

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
     sort edges by increasing weight
          add lowest weight edge that doesn't complete a circuit.
          so long as no unvisited vertices are left
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

Next Fit:
    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

First Fit:
     fit the next object into the first among the currently used bin where it fits.

Worst Fit:
     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 vertices sharing an edge are colored with the same color.
The chromatic number is the least number of colors needed to do the vertex coloring.