Agraphis a finite set ofvertices(dots) connected byedges.

Thedegree(valence) of a vertex is the number of edges incident to the vertex.

Apathis a connected sequence of edges.

A graph isconnectedif and only if for every pair of vertices there is a path in the graph between them.

Acircuit(cycle) is a path that starts and ends at the same point.

AnEulercircuitis a circuit that traverses each edge exactly once.

- All vertices in G have even degree.
- G has an Eulercircuit.

AnEulerpathis a path that traverses each edge exactly once, and is not a circuit.

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

**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

atreeis a graph that does not contain a circuit.

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 thecritical path.

A task isreadyat 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.