Introduction to Graphs
Graph theory was founded in the 18th century, with Euler’s article on the Seven Bridges of Königsberg problem. The city of Königsberg had seven bridges, connecting the north and south banks of the river, and two fluvial islands (Kneiphof and Lomse). Back then, Königsberg looked roughly like this:
---
config:
layout: elk
look: handDrawn
---
graph LR
N[North Bank]
K[Kneiphof Island]
L[Lomse Island]
S[South Bank]
N === K
N === K
N === L
S === L
S === K
S === K
K === L
The problem was to find a path such that a walker would cross each bridge exactly once. To solve this problem (by proving it had no solution), Euler found two useful abstractions: vertices representing land masses, and edges representing bridges. A key insight of framing the problem like this was that a graph can be represented in many ways (e.g., where to position the vertices), and all of them are equivalent.
In the 21st century, we define graphs as sets of objects (vertices) and pairwise relations between them (edges). Graphs are also known as networks; vertices as nodes; and edges as links. Königsberg is a graph with 4 vertices and 6 edges. Importantly, graphs represent similarities between objects. In maths, equivalence formalize the notion than objects can have a relationship of “sameness”. An equivalence relation is a binary relation that is reflexive, transitive and symmetric. It is noted like
Importantly, graphs are mathematical objects. A graph
Where
Notation note:
and above refer sets, specifically to the vertex and edge set of a specific graph ( ). Note that they are in italics. In contrast, the in and refer to the vertex sets of graphs and respectively. Note that they are not in italics. I will follow the same convention elsewhere, e.g. when writing about graph’s matrices.
This notation allows to concisely define multiple types of graph:
-
Undirected graph:
, i.e., the edges do not have directions.--- config: layout: elk look: handDrawn --- graph LR vertex_a((a)) vertex_b((b)) vertex_c((c)) vertex_a === vertex_b vertex_a === vertex_c vertex_b === vertex_c
-
Directed graphs:
, i.e., the edges have directions.--- config: layout: elk look: handDrawn --- graph LR vertex_a((a)) vertex_b((b)) vertex_c((c)) vertex_a --> vertex_b vertex_a --> vertex_c vertex_b --> vertex_c
Sometimes, graphs are defined as triples. An example are multigraphs, graphs in which multiple edges between the same pair of vertices are allowed. They are triples
Another type of graph that requires a triple are weighted graphs, in which each edge has a weight. They are triples
Note: unless specified otherwise, in this series I will focus on simple graphs, which have at most one edge between any pair of vertices and no loops.