Definition:Graph (Graph Theory)
Contents |
Informal Definition
A graph is intuitively defined as a pair consisting of a set of nodes or vertices and a set of edges.
Vertex
In the above, the vertices (singular: vertex) are the points $A, B, C, D, E, F, G$ which are marked as dots.
Edge
The edges are the lines that join the vertices together.
In the above, the edges are $AB, AE, BE, CD, CE, CF, DE, DF, FG$.
Formal Definition
Formally, a graph is an ordered pair $G = \left({V, E}\right)$ such that:
- $V$ is a set, called the vertex set;
- $E$ is a set of 2-element subsets of $V$, called the edge set.
That is: $E \subseteq \left\{{\left\{{u, v}\right\}: u, v \in V}\right\}$.
$E$ can also be described as an antireflexive, symmetric relation on $V$.
It is often convenient to refer to the vertex set and edge set for a given graph $G$ as $V \left({G}\right)$ and $E \left({G}\right)$ respectively, especially if there is at any one time more than one graph under consideration.
A graph whose vertex set is empty is called the null graph.
Many treatments of this subject require that $V$ is non-empty, and so do not recognise the concept of a null graph.
Order
The order of a graph is the count of its vertices.
Size
The size of a graph is the count of its edges.
Notation
A graph $G$ whose order is $p$ and whose size is $q$ is called a $\left({p, q}\right)$-graph.
Also see
- Multigraph: A graph which may have more than one edge between a given pair of vertices;
- Loop-graph: A graph which allows an edge to start and end at the same vertex. Such an edge is called a loop.
- Directed graph or digraph: A graph in which the edges are ordered pairs of vertices.
A graph which is not a multigraph nor a loop-graph nor a directed graph can be called a simple graph if this clarification is necessary.
Note
Not to be confused with the Graph of a Mapping.
Sources
- Gary Chartrand: Introductory Graph Theory (1977): $\S 1.3, \ 2.1$
