Graphs

Posted on September 9th, 2022

Part of (Re)Learning CS

Talks aboutComputer Science

Graphs come from maths, and allow computers to model many types of related data like geographical maps or social networks.

The Basics

A node, or vertex, is a element (a house).

An edge, is a connection between nodes (the road between houses). These are not required: nodes are connected when they have an edge to another node and are disconnected without.

A path is a sequence of edges (driving from house 1 to 3). Acycle is a path starting and ending at the same node (driving from house 1 to 2 to 1).

A graph is a collection of nodes and edges, like a linked list (a map of the street).

There's also the multigraph, which allows two nodes to have multiple undirected edges between them — we aren't talking about these 🤫

Directionality

Directionality is a property of an edge, indicating how the edge can be traversed (which way can you drive down the street).

In an directedgraph, defining an edge $e = (v, w)$ means we can only traverse from $v$ to $w$. In an undirected graph, we can go both ways.

To convert from an undirected graph, for each $(v, w)$ in $E$, we add $(w, v)$ to allow traversal in both directions.

Weight

Another property of edges is weight (or cost); on a map, the cost betweentwo places could be distance or elevation change.

We define an edge with weight as $e = (v, w, 2)$, where $2$ represents the cost.

Density

What's the most edges a graph can have? Excluding multigraphs, defining a edge from each vertex to every other vertex, plus itself, gives an upper-bound of $|E| = |V| \times |V| = |V|^2$;

Therefore we consider a graph to be denseorsparsewhen its amount of edges is near or far to the upper-bound respectively.

Notation

Graphs can be proper big so we can't always traverse a pretty picture.

We represent graph $G = (V, E)$, where $V$ is the set of vertices in $G$ and $E$ is the set of edges in $G$.

An edge $E$ is represented as a pair $(v, w)$ such that $v$ and $w$ are vertices.

When considering the size of a graph, $|V|$ (or $n$) is the total number of vertices and $|E|$ (or $m$) is the total number of edges.

For a full list, see this document.

Representations

An adjacency matrix is a wham table, where rows represent the vertex 'from' and columns represent 'to'. The cell value comes from the edge's weight or simply a boolean when unweighted.

Undirected graphs have a party trick; because each edge runs in both directions, the table is symmetric through the diagonal.

Adjacency matrices are suited for dense graphs, as they reserve space for every edge, whereas an adjacency list only specifies existant edges to minimise space. For each vertex, its connected nodes are listed, plus the weight is necessary (with something tuple-y).