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 labels. A numeric label is often called a "weight". If the edges have a direction associated with them (indicated by an arrow in the graphical representation) we have a directed graph. This means it is possible to follow a path from one vertex to another, but not in the opposite direction. If there are no directed edges, the graph is an undirected graph. There may be more than one edge between two vertices (directed or undirected), this is known as a multigraph.
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.
An undirected 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
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 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.
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. This can complicate things as some graphical representations are easier to work with or easier to understand than others.
While it is usually easy to represent graphs with pictures, it will not always clarify the problems you face. For example, you may have a graph with many verticies, each one connecting many others, thus the graphical representation can look like a mess. Further, graphical representations are only useful to humans. A pictorial simplification is of no use to a computer. Thus it is necessary to come up with algorithms that can solve your problems without requiring a picture.
There are different approaches to graph layout, and these are considered under a branch of graph theory termed as graph drawing.Basic formal definitions
An undirected graph (or graph for short) is given by
Informally, it is said that a graph is a set of vertices, some pairs of which being connected by edges.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