Worlds of David Darling
Encyclopedia of Science
   
Home > Encyclopedia of Science

graph





"I'll do algebra, I'll do trig, and I'll even do statistics, but graphing is where I draw the line!"
—anonymous
  1. In common usage, 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.

  2. In strict mathematical usage, 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 graph

A graph in 3-dimensional space; equivalently, a graph drawn in the plane so that when edges cross, one edge goes over the other.


weighted graph

A graph having a weight, or number, associated with each edge. Some algorithms require all weights to be nonnegative, integral, positive, etc. Also known as an edge-weighted graph.


Related entry

   • lattice


Related category

   • GRAPHS AND GRAPH THEORY