### 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:
• All vertices in G have even degree.
• G has an Eulercircuit.
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:
• All vertices in G, except for two: P, Q have even degree.
• G has an Eulerpath starting at P and ending at Q.
• To Eulerize a graph is to add edges to a graph so that it then 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.

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
repeat:
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
repeat
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
repeat:
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.