Graph
Definition
A graph is a pair of sets:
- A nonempty set called the vertex set, whose elements we call vertices or nodes.
- A (possibly empty) set called the edge set, whose elements we call edges, where each edge is a subset of the vertex set that contains exactly two elements, called the endpoints of the edge. If two vertices are endpoints of an edge, we say that they are adjacent vertices.
We often use G = (V,E) to denote a graph whose name is G, whose vertex set is V, and whose edge set is E.
Notes:
- The definition of a graph is rather abstract because we want room to represent graphs in different ways: both visually, and as pure data structures in several different forms. See Representations of graphs for more.
- Note that the edge set of a graph is a set, whose elements are also sets -- namely, two-element subsets of the vertices. The edge \{u,v\} and the edge \{v,u\} are the same, since they are equal sets.
Examples
-
Consider the graph G = (\{a,b,c,d\}, \{\{a,c\}, \{a,d\}, \{d,c\}, \{a,b\}\}). Note that this is a pair of sets, enclosed in parentheses. The first element of the pair is the set \{a,b,c,d\}, and these are the vertices. The second element is \{\{a,c\}, \{a,d\}, \{d,c\}, \{a,b\}\} and these are the edges. There are four edges: One with endpoints a and c; one with endpoints a and d; a third with endpoints d and c; and a fourth with endpoints a and b. Note that because the edges are given as sets, not as ordered pairs, each edge is the same no matter what order we list the endpoints in. A visualization of the graph G is:
-
When visualized in this way -- with each vertex shown as a point and each edge shown as a line segment between its endpoints -- graphs are representations of networks.
-
Consider the following visualization of a graph:
Note that there are five vertices and 10 edges, one edge between every pair of different vertices. In notation, this graph is G = (V,E) where V = \{1,2,3,4,5\} (the vertices) and E = \{\{1,2\}, \{1,3\}, \{1,4\}, \{1,5\}. \{2,3\}, \{2,4\}, \{2,5\}, \{3,4\}, \{3,5\}, \{4,5\}\}. (This graph is called the Complete graph on five vertices.)
- Not every vertex in a graph needs to be the endpoint of an edge. Consider G = (\{1,2,3\}, \{1,2\}) for example which has three vertices but only one edge, whose endpoints are 1 and 2.
- While every graph must have at least one vertex according to the definition, the edge set can be empty. For example G= (\{1,2,3\}, \emptyset) has three vertices but no edges. Its visualization would just be three dots with no line segments.
- There can only be at most one edge between any two distinct vertices in a graph; two different vertices cannot be connected by two or more edges. (Graph-like structures that allow for multiple edges between the same two vertices are called multigraphs.) This is because in the definition, the edges are a set of two-element sets, and the same two-element set cannot happen twice.
- An edge cannot connect a vertex to itself, forming a loop. This because each edge is actually a two-element subset of the vertices, and the same vertex cannot appear twice.