Graph (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.

---

In mathematics and computer science, a graph is a generalization of the simple concept of a set of dots, called vertices or nodes, connected by links, edges or arcs. "Nodes" and "arcs" are old notation. Depending on the applications, edges may or may not have a direction; edges joining a vertex to itself may or may not be allowed, and vertices and/or edges may be assigned weights, i.e. numbers. If the edges have a direction associated with them (indicated by an arrow in the graphical representation) we have a directed graph.

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 algorithms.

To do: Add more pictures here.

A graph with 6 vertices and 7 edges.

Table of contents

1 History 2 Formal Definitions 3 Examples 4 Pictorial representation of graphs

History

See graph theory.

Formal Definitions

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.

If, in a pictural representation of a graph, each vertex is given a label, then the graph is said to be labelled graph.

Examples

Formal definition: V={1,2,3,4,5,6}, E={e1,e2,e3,e4,e5,e6,e7} and the function w(e1)={1,2}, w(e2)={2,3}, w(e3)={1,5}, w(e4)={2,5}, w(e5)={3,4}, w(e6)={4,5}, w(e7)={4,6}.

Pictorial representation of graphs

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 these are considered under a branch of graph theory termed as graph drawing.