Definition:Graph (Graph Theory)
This page is about Graph in the context of Graph Theory. For other uses, see Graph.
Definition
A graph is intuitively defined as a pair consisting of a set of vertices and a set of edges each with a vertex at each end.
Vertex
Let $G = \struct {V, E}$ be a graph.
The vertices (singular: vertex) are the elements of $V$.
Informally, the vertices are the points that are connected by the edges.
Edge
Let $G = \struct {V, E}$ be a graph.
The edges are the elements of $E$.
Order
Let $G = \struct {V, E}$ be a graph.
The order of $G$ is the cardinality of its vertex set.
Size
Let $G = \struct {V, E}$ be a graph.
The size of $G$ is the count of its edges.
Notation
Let $G$ be a graph whose order is $p$ and whose size is $q$.
Then $G$ can be referred to as a $\tuple {p, q}$-graph.
A wider category: a graph whose order is $n$ can be referred to as an $n$-graph.
Also presented as
While it is commonplace to present a graph as a diagram consisting of dots connected by lines, some sources use circles for the vertices.
In that way, the labels for the vertices can be written neatly inside the circles.
Examples
Arbitrary Example 1
Arbitrary Example 2
Also see
- Definition:Simple Graph: a graph which:
- Definition:Multigraph: A graph which may have more than one edge between a given pair of vertices
- Definition:Loop-Graph: A graph which allows an edge to start and end at the same vertex
- Definition:Loop-Multigraph: A multigraph which is allowed to have loops
- Definition:Directed Graph or Definition:Digraph: A graph in which the edges are ordered pairs of vertices.
- Definition:Weighted Graph, where in addition the edges are each mapped to a number
- Definition:Null Graph: A graph whose vertex set is empty.
- Results about graphs can be found here.
Also defined as
Many treatments of this subject require that $V$ is non-empty, and so do not recognise the concept of a null graph.
Sources
- 1979: John E. Hopcroft and Jeffrey D. Ullman: Introduction to Automata Theory, Languages, and Computation ... (previous) ... (next): Chapter $1$: Preliminaries: $1.2$ Graphs and Trees
- 1992: George F. Simmons: Calculus Gems ... (previous) ... (next): Chapter $\text {A}.21$: Euler ($\text {1707}$ – $\text {1783}$)
- 1992: David Wells: Curious and Interesting Puzzles ... (previous) ... (next): The Bridges of Königsberg
- 1993: Richard J. Trudeau: Introduction to Graph Theory ... (previous) ... (next): $2$. Graphs: Graphs
- 1997: Donald E. Knuth: The Art of Computer Programming: Volume 1: Fundamental Algorithms (3rd ed.) ... (next): $\S 2.3.4.1$: Free Trees
- 2014: Christopher Clapham and James Nicholson: The Concise Oxford Dictionary of Mathematics (5th ed.) ... (previous) ... (next): graph