Graph (discrete mathematics)
This article is about graphs in graph theory. See graph of a function and graph of a relation for other uses of "graph" in mathematics.
Definitions of graphs and digraphs
The basic definitions in graph theory vary in the literature. Here are the conventions used in this encyclopedia.
A directed graph (also called digraph or quiver) consists of
- a set V of vertices, and
- a set E of edges, and
- maps s, t : E → V, where s(e) is the source and t(e) is the target of the directed edge e.
An undirected graph (or graph for short) is given by
- a set V of vertices,
- a set E of edges,
- a function w : E → P(V) which associates to each edge a two- or one-element subset of V, interpreted as the endpoints of the edge.
In a weighted graph or digraph, an additional function E → R associates a value with each edge, which can be considered its "cost"; such graphs arise in optimal route problems such as the traveling salesman problem.
Pictorial representation (graph layout)
Graphs are often represented pictorially as follows: draw a dot for every vertex, and for every edge draw an arc connecting its endpoints. If the graph is directed, indicate the endpoint of an edge by an arrow.
Note that this graphical representation (a layout) should not be confused with the graph itself (the abstract, non-graphical structure). Very different layouts can correspond to the same graph (see http://www.aisee.com/gallery/graph23.htm ). All that matters is which vertices are connected to which others by how many edges.
There are different approaches to graph layout and are considered under a branch of graph theory termed as graph drawing. Some of the well known layouts are
- spring layout - by using an energy function that is minimized so that nodes and edges spread out by repulsion.
- orthogonal layout - layout with edges running horizontally or vertically, with approaches that reduce the number of edge crossovers and area covered. These are of great interest in the VLSI and chip design areas.
- symmetric layout - these attempt to find symmetry groups within the graph
- tree layout - these show a rooted tree like formation, suitable for trees (ie graphs without cycles)
- hierarchical layouts - these attempt to find a source and sink within a directed graph and arrange the nodes in layers with most edges starting from the source and flowing in the direction of the sink.
Here are some examples of graph layouts: