A graph is a set V of vertices
and a set E of edges -- pairs of elements of V. This simple definition makes
Graph Theory the appropriate language for discussing (binary) relations on
sets, which is clearly a broad topic. In a graph, it is important to know which
vertices are connected by which edges. A graph with neither loops nor parallel
edges is a simple graph. If numbers are assigned to the edges, the graph
is a weighted graph. A path from v0 to vn is an
alternating sequence of n + 1 vertices and n edges beginning with vertex
v0 and ending with vertex vn. A simple path is a path with
no repeated vertices. A cycle is a path of nonzero length from v
to v with no repeated edges. An Euler cycle in a graph G is
a cycle that includes all of the edges and all of the vertices of G.
A Hamiltonian cycle in a graph G is a cycle that
contains each vertex in G exactly once, except for the the starting and
ending vertex that appears twice.
In weighted graphs, in order to find the shortest path
(path having minimum length) between two vertices, algorithms such as Dijkstra’s
algorithm can be used.
To represent graphs, the adjacency matrix method is used. This method orders the vertices and labels
the rows and columns of a matrix with the ordered vertices.
Two graphs G1 and G2 are isomorphic if there
is a one-to-one, onto function f from the vertices of G1 to the vertices of G2 and a one-to-one,
onto function g from the edges of G1 to the edges of G2.
A graph is planar is it can be drawn in the plane without
its edges crossing. Two graph are homeomorphic if they can be reduced to
isomorphic graphs by performing a sequence of series reduction.
A rooted tree is a
tree in which a particular vertex is designated the root. In a rooted tree
structure, each vertex represents a file or a folder. Directly under a folder f
are the folders and files contained in f. A Huffman code can be defined
by a rooted tree. The code for a particular character is obtained by following
the simple path from the root to that character. Each edge is labeled with 0 or
1, and the sequence of bits encountered on the simple path is the code for that
character.
A tree T is a spanning tree of a graph G if T is
a subgraph of G that contains all of the vertices of G. A graph G
has a spanning tree if and only if G is connected. A minimal spanning
tree is a spanning tree with minimum weight. Prim’s algorithm builds
a minimal spanning tree by itetatively adding edges. The algorithm begins
with a single vertex. Then at each iteration, it adds to the current tree a
minimum-weight edge that does not complete a cycle.
A greedy algorithm optimizes the choice at each iteration
without regard to previous choices.
A binary tree is a rooted tree in which each vertex has
either no children, one child, or two children. A binary tree is full is each
vertex has either two children or zero children. A binary search tree
is a binary tree T in which data are associated with the vertices. The data are arranged so that, for each
vertex v in T, each data item in the left subtree of v is
less than the data item in v, and each data item in the right subtree of
v is greater than the data item in v.
Preorder traversal
processes the vertices of a binary tree by beginning at the root and
recursively processing the current vertex, the vertex’s left subtree, and then
the vertex’s right subtree. Postorder traversal processes the vertices
of a binary tree by beginning at the root and recursively processing the vertex’s
left subtree, the vertex’s right subtree, and then the current vertex. Inorder
traversal processes the vertices of a binary tree by beginning at the root
and recursively processing the vertex’s left subtree, the current vertex, and
then the vertex’s right subtree.
A decision tree is a binary tree in which the internal
vertices contain questions with two possibles answers, the edges are labeled
with answers to the questions, and the terminal vertices represent decisions.
If we begin at the root, answer each question, and follow the appropriate
edges, we will eventually arrive at a terminal vertex that represents a
decision.
In a game tree, each vertex shows a particular position in
the game. In particular, the root shows the initial configuration of the game.
The children of a vertex show all possible responses by a player to the
position shown in the vertex.
Graphical models for
electrical and communications networks and computer architectures.
URL: www.graphtheory.com
Telephone companies are
particularly interested in minimum spanning trees, because the minimum spanning
tree of a set of sites defines the wiring scheme that connects the sites using
as little wire as possible. It is the mother of all network design problems.
URL: www.cs.columbia.edu
QUESTIONS