A vertex is a point in a graph where one or more edges end.
The valence of a vertex is the number of edges touching that vertex.
Complete graph is a graph in which every pair of vertices is joined by an edge.
A graph is said to be connected if for any pair of its
vertices there is at least one path of one or more edges connecting the two
vertices. If we can find even one pair
of vertices not connected by a path, then we say that the graph is not
connected.
Critical path is the longest path in an order-requirement digraph. the length of this path gives the earlies completion time for all the tasks making up the job consisting of the tasks in the digraph.
A circuit is a path that
starts and ends at the same vertex.
A simple circuit is one in which every vertex has a valence equal to two.
An Euler circuit is a circuit that traverses each edge of a graph exactly once.
Euler’s theorem (used to determine when a graph G has an Euler circuit)
A Hamiltonian circuit is a circuit using distinct edges of a graph that starts and ends at a particular vertex of the graph and visits each vertex once and only once. A Hamiltonian circuit can be thought of as starting at any one of its vertices.
The Traveling Salesman Problem (TSP) is the problem of
finding a minimum-cost Hamiltonian circuit in a complete graph where each edge
has been assigned a cost or weight.
NP-complete problems is a collection of problems which includes the TSP that appear to be very hard to solve quickly for an optimal solution.
Order-requirement digraph is a directed graph that shows which tasks precede other tasks among the collection of tasks making up a job.
A greedy algorithm is an approach for solving an optimization problem where at each state of the algorithm, the best (or cheapest) action is taken. Unfortunatley, greedy algorithms do not always lead to optimal solutions.