*This article just presents the basic definitions. For a broader view see graph theory.* *For another mathematical use of "graph", see graph of a function.* A graph with 6 vertices and 7 edges. In mathematics and computer science a **graph** is the basic object of study in graph theory. Informally, a graph is a set of objects called **vertices** connected by links called **edges**. Typically, a graph is depicted as a set of dots (the vertices) connected by lines (the edges). Depending on the application some edges can directed. ## Definitions
Definitions in graph theory vary in the literature. Here are the conventions used in this encyclopedia.
### Undirected graph An **undirected graph** or **graph** *G* is an ordered pair *G*:=(*V*, *E*) with *V* a set of **vertices** or **nodes**, *E* a set of unordered pairs of distinct vertices, called **edges** or **lines**. ### Directed graph A **directed graph**, **digraph** or **quiver** *G* is an ordered pair *G*:=(*V*,*A*) with *V* a set of **vertices** or **nodes**, *A* a set of ordered pairs of vertices called **directed edges**, **arcs** or **arrows**. Note that a directed graph is allowed to have **loops**, that is, edges where the start and end vertices are the same.
### Mixed graph A **mixed graph** *G* is a 3-tuple *G*:=(*V*,*E*,*A*) with *V*, *E* and *A* defined as above.
### Variations in the definitions As defined above, edges of undirected graphs have distinct ends, and *E* and *A* are sets (with distinct elements as sets always do). Many applications require more general possibilities, but terminology varies. A **loop** is an edge (directed or undirected) with both ends the same; these may be permitted or not permitted according to the application. Sometimes *E* or *A* are allowed to be multisets, so that there can be more than one edge between the same two vertices. The unqualified word "graph" might allow or disallow multiple edges in the literature, according to the preferences of the author. If it is intended to exclude multiple edges (and, in the undirected case, to exclude loops), the graph can be called **simple**. On the other hand, if it is intended to allow multiple edges, the graph can be called a **multigraph**. Sometimes the word **pseudograph** is used to indicate that both multiple edges and loops are allowed.
### Further definitions *For more definitions see Glossary of graph theory.* Two edges of a graph are called **adjacent** (sometimes **coincident**) if they have a common vertex. Similarly, two vertices are called **adjacent** if they are the ends of the same edge. An edge and a vertex on that edge are called **incident**. The graph with only one vertex and no edges is the **trivial graph**. A graph with only vertices and no edges is known as an **empty graph**; the graph with no vertices and no edges is the **null graph**, but not all mathematicians allow this concept. In a **weighted** graph or digraph, each edge is associated with some value, variously called its *cost*, *weight*, *length* or other term depending on the application; such graphs arise in many contexts, for example 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*.
## Examples The picture is a graphic representation of the following graph *V*:={1,2,3,4,5,6} *E*:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,5}} ## Important graphs ## Generalizations In a hypergraph, an edge can connect more than two vertices. An undirected graph can be seen as a simplicial complex consisting of 1-simplices (the edges) and 0-simplices (the vertices). As such, complexes are generalizations of graphs since they allow for higher-dimensional simplices. Every graph gives rise to a matroid, but in general the graph cannot be recovered from its matroid, so matroids are not truly generalizations of graphs. In model theory, a graph is just a structure. But in that case, there is no limitation on the number of edges: it can be any cardinal number. |