Graph Definition/Meaning:
A nonempty but finite set of vertices (or nodes) together with a set of
edges that join pairs of distinct vertices. If an edge e joins vertices v1, and
v2, then v1 and v2 are said to be incident with
e and the vertices are said to be adjacent; e is the unordered pair (v1,v2).
A graph is usually depicted in a
pictorial form in which the vertices appear as dots or other shapes, perhaps
labeled for identification purposes, and the edges are shown as lines joining
the appropriate
points. If direction is added to each edge of a graph, a directed graph or
digraph is obtained. The edges then form a finite set of ordered pairs of
distinct vertices, and are often called arcs. In the pictorial representation,
arrows can be placed on each edge. With no direction specified, the graph is
said to be undirected. Although helpful visually these representations are not
suitable for manipulation by computer. More useful representations use an
incidence matrix or an adjacency matrix.
Graphs are used in a wide variety of ways in computing: the vertices will
usually represent objects of some kind and the edges will represent connections
of a physical or logical nature between the vertices. So graphs can be used to
model in a mathematical fashion such diverse items as a computer and all its
attached peripherals, a network of computers, parse trees, logical dependencies
between subroutines or nonterminals in a
grammar, VLSI diagrams, and related
items in databases. Trees and lists are special kinds of graphs.
Certain variations exist in the definition of a graph. There is some dispute
about whether one edge can join a vertex to itself, whether empty sets are
involved, whether an infinite number of vertices and edges are permitted, and so
on. See also connected graph.
|
