Graph (mathematics)
From open-encyclopedia.com - the free encyclopedia.
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. Unless otherwise indicated, the term graph typically is assumed to mean a simple graph, in which at most one edge exists between any two vertices (directed or undirected). If any two vertices share more than one edge, this is known as a multigraph. A multigraph that additionally allows graph loops, or edges which connect a vertex to itself, is called a pseudograph.
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.
| Contents |
History
See graph theory.
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 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 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.
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 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 vertices, 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.
Related topics
External links
bg:Граф (математика) de:Graph (Graphentheorie) pl:Graf (matematyka) ru:Граф (математика) zh-cn:图
