Graph

The word "graph" has (at least) two meanings in mathematics.

In elementary mathematics, "graph" refers to a function graph or "graph of a function," i.e., a plot.

In a mathematician's terminology, a graph is a collection of points and lines connecting some (possibly empty) subset of them. The points of a graph are most commonly known as graph vertices, but may also be called "nodes" or simply "points." Similarly, the lines connecting the vertices of a graph are most commonly known as graph edges, but may also be called "arcs" or "lines."

The study of graphs is known as graph theory, and was first systematically investigated by D. König in the 1930s (Gardner 1984, p. 91). Unfortunately, as Gardner (1984, p. 91) notes, "The confusion of this term [i.e., the term "graph" to describe a network of vertices and edges] with the 'graphs' of analytic geometry [i.e., plots of functions] is regrettable, but the term has stuck." Some educators use the term "vertex-edge graph" for a connected set of nodes in an attempt to preserve the common usage of "graph" to mean the plot of a function.

Euler's proof of the nonexistence of a so-called Eulerian cycle across all seven bridges of Königsberg, now known as the Königsberg bridge problem, is a famous precursor to graph theory. In fact, the study of various sorts of paths in graphs (e.g., Eulerian paths, Eulerian cycles, Hamiltonian paths, and Hamiltonian cycles) has many applications in real-world problems.

Graphs come in a wide variety of different sorts. The most common type is graphs in which at most one edge (i.e., either one edge or no edges) may connect any two vertices. Such graphs are called simple graphs. If multiple edges are allowed between vertices, the graph is known as a multigraph. Vertices are usually not allowed to be self-connected, but this restriction is sometimes relaxed to allow such "graph loops." A graph that may contain multiple edges and graph loops is called a pseudograph.

An object maybe be tested to see if it is a graph in the Wolfram Language using the predicate GraphQ[g].

The edges, vertices, or both of a graph may be assigned specific values, labels, or colors, in which case the graph is called a labeled graph. A vertex coloring is an assignment of labels or colors to each vertex of a graph such that no edge connects two identically colored vertices. Similarly, an edge coloring is an assignment of labels or colors to each edge of a graph such that adjacent edges (or the edges bounding different regions) must receive different colors. The assignment of labels or colors to the edges or vertices of a graph based on a set of specified criteria is known as graph coloring. If labels or colors are not permitted so that edges and vertices do not carry any additional properties beyond their intrinsic connectivities, a graph is called an unlabeled graph.

The edges of graphs may also be imbued with directedness. A normal graph in which edges are undirected is said to be undirected. Otherwise, if arrows may be placed on one or both endpoints of the edges of a graph to indicate directedness, the graph is said to be directed. A directed graph in which each edge is given a unique direction (i.e., edges may not be bidirected and point in both directions at once) is called an oriented graph. A graph or directed graph together with a function which assigns a positive real number to each edge (i.e., an oriented edge-labeled graph) is known as a network.

Rather amazingly, there are always an even number of odd vertices (i.e., vertices having an odd number of edges incident on them) for any simple graph.

A large number of operations can be defined on collections of graphs. For example, graph sums, differences, powers, unions, and products can be defined, as can graph eigenvalues.

Formally, graphs may be considered as the one-dimensional case of the more general CW-complexes.

REFERENCES

Bogomolny, A. "Graph Puzzles." http://www.cut-the-knot.org/do_you_know/graphs2.shtml.Fujii, J. N. Puzzles and Graphs. Washington, DC: National Council of Teachers, 1966.

Gardner, M. The Sixth Book of Mathematical Games from Scientific American. Chicago, IL: University of Chicago Press, p. 91, 1984.

Pappas, T. "Networks." The Joy of Mathematics. San Carlos, CA: Wide World Publ./Tetra, pp. 126-127, 1989.

Read, R. C. and Wilson, R. J. Atlas of Graphs. Oxford, England: Oxford University Press, 1998.

Sloane, N. J. A. and Plouffe, S. Figure M1253 in The Encyclopedia of Integer Sequences. San Diego: Academic Press, 1995.

Weisstein, E. W. "Books about Graph Theory." http://www.ericweisstein.com/encyclopedias/books/GraphTheory.html.Wilson, J. C. On the Traversing of Geometrical Figures. Oxford, England: Oxford University Press, 1905.