## graph
- In common usage, a graph is a plot of
*x*values (the domain) against*y*values (the codomain) for a given function,*y*=*f*(*x*). Such a graph is also known as a**function graph**or the**graph of a function**. - In strict mathematical usage, a graph is any set of dots, known as
*nodes*or*vertices*, in which at least some pairs are joined by lines known as**edges**or**arcs**. What follows applies only to this second definition.
Often the lines on a graph are used to represent relationships between objects (represented by dots). Depending on the application, edges may or may not have a direction, as indicated by an arrow (see directed graph); edges joining a node to itself may or may not be allowed, and nodes and/or edges may be assigned weights (see 'weighted graph' below). A path is a series of nodes such that each
node is adjacent to both the preceding and succeeding node. A path is considered simple if none of the nodes in the path is repeated. The length of a path is the number of edges that the path uses,
counting multiple edges multiple times. If it's possible to establish a
path from any node to any other node of a graph, the graph is said to be
a connected graph. A circuit or cycle is a path that begins and ends with the same node
and has a length at least two. A tree is a connected acyclic
graph, i.e., a graph without any circuits. A complete
graph is one in which every node is adjacent to every other node. An Euler path in a graph is a path that
uses each edge precisely once. If such a path exists, the graph is said
to be traversable. An Euler
circuit is a path that traverses each edge precisely once. A Hamilton
path in a graph is a path that visits each node once and only once;
a Hamiltonian circuit is a circuit
that visits each node once and only once. Well known problems whose solution
involves graphs and graph theory include the four-color
problem and the traveling
salesman problem. ## tangled graphA graph in 3-dimensional space; equivalently, a graph drawn in the plane so that when edges cross, one edge goes over the other.## weighted graphA graph having a weight, or number, associated with each edge. Some algorithms require all weights to be nonnegative, integral, positive, etc. Also known as anedge-weighted graph. ## Related entry• lattice## Related category• GRAPHS AND GRAPH THEORY | |||||||

Home • About • Copyright © The Worlds of David Darling • Encyclopedia of Alternative Energy • Contact |