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 |
|
2 Basic Formal Definitions 3 Examples 4 Pictorial representation of graphs 5 Related articles 6 External links |
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
Basic Formal Definitions
An undirected graph (or graph for short) is given by
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.
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 labelled graph. Consequently, graphs without labels on vertices are called unlabelled.
For more definitions, see Glossary of graph theory.
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 external link #2). 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.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