Undirected & Directed Graphs

A graph is one of the simplest yet most powerful structures in mathematics.
It consists of two pieces of data: a set of vertices (the "dots") and a set of
edges (the "lines" between them). The same idea shows up everywhere in AI:
knowledge graphs link entities, search spaces link states, and neural networks link
neurons.

According to Definition 6.1.1 (notes p. 82), an undirected graph is a pair
$\langle V, E \rangle$ where $V$ is a set of vertices and the edges come from a
specific kind of set:

Because edges are sets of two, the edge $\{a, b\}$ is the same as $\{b, a\}$ —
direction does not matter. Picture a friendship network: if Alice is friends with
Bob, then Bob is also friends with Alice.

In contrast, Definition 6.1.2 gives us a directed graph (digraph): the same
pair $\langle V, E \rangle$, but with ordered pairs:

Now the edge $(a, b)$ is distinct from $(b, a)$: it points from $a$ to $b$. Picture
a Twitter following: Alice can follow Bob without Bob following her back.

Why care? In AI:
- A knowledge graph (Google, Wikipedia, chatbots) is a directed graph whose
nodes are concepts and edges are relations ("Paris", "capital-of", "France").
- The state space of a search problem is a graph: nodes are configurations,
edges are moves.
- A neural network is a layered directed graph of neurons with weighted edges.

The same definition (vertices + edges) is flexible enough to model all of them.

An adjacency list represents a graph $G = \langle V, E \rangle$ as a function from each vertex to its neighbour set (or list).

In SML:

type graph = int list list;
(* graph[i] = list of vertices adjacent to i *)

Example. The graph with vertices $\{1, 2, 3, 4\}$ and edges $\{(1,2), (2,3), (3,4), (4,1)\}$ (a 4-cycle) has adjacency list:

val G = [[2,4], [1,3], [2,4], [3,1]] : graph;

Operations on adjacency lists:
- isTree G: a graph is a tree iff it's connected and has exactly n - 1 edges.
- size G: $|V| =$ length G.
- depth v G: longest path from $v$ in $G$.
- getNeighbors v G: nth v G.

Worked example. Size of the 4-cycle above: length G = 4. ✓

Used in assignment 6.6.