Home > Graph (mathematics)

Structures that can be represented as graphs are ubiquitous, and many problems of practical interest can be formulated as questions about certain graphs. For example, the link structure of Wikipedia could be represented by a directed graph: the vertices are the articles in Wikipedia, and there's a directed edge from article A to article B if and only if A contains a link to B. Directed graphs are also used to represent finite state machines. The development of algorithms to handle graphs is therefore of major interest in computer science: see graph algorithm s.

1 History

See graph theory.

2 Basic formal definitions

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.

Informally, it is said that a graph is a set of vertices, some pairs of which being connected by edges.

Two edges of a graph are called coincident if they have a common vertex. Two vertices are called adjacent if they are the ends of the same 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 problem s such as the traveling salesman problem.

Normally, the vertices of a graph by their nature are undistinguishable. (Of course, they may be distinguishable by the properties of the graph itself, e.g., by the numbers of incident edges). Some branches of graph theory require to uniquely identify vertices. If each vertex is given a label, then the graph is said to be a vertex-labeled graph, whereas graphs which have labeled edges are called edge-labeled graphs. Graphs with labels attached to edges or vertices are more generally designated as labeled. Consequently, graphs without labels are called unlabelled.

For more definitions, see Glossary of graph theory.