Chapter 6Graphs and Treesnotes.en.pdf:86-88

Isomorphism and Labeled Graphs

Same shape, different names

Def 6.1.8 — Graph isomorphismDef 6.1.11 — Labeled graph

Concept

Two graphs with completely different vertex names might still describe the same
structure. That is exactly what isomorphism captures.

Definition 6.1.8 (notes p. 86): An isomorphism between
$G = \langle V, E \rangle$ and $G' = \langle V', E' \rangle$ is a bijective
function $\psi: V \to V'$ such that for all $u, v \in V$ :

(u, v) \in E \iff (\psi(u), \psi(v)) \in E'

Two graphs are equivalent (Definition 6.1.9) iff such a $\psi$ exists.

The map $\psi$ is a "relabeling" that preserves all the edges — the graph is the
same up to naming. This is the graph-theoretic analogue of bijection between sets.

Labeled graphs (Definition 6.1.11, notes p. 88): a graph together with a labeling
function $l: V \cup E \to L$ that assigns extra information (numbers, names, types)
to nodes and edges. Labeled graphs can be isomorphic as graphs even when their
labels differ — the labels are extra annotation, not part of the structure.

Why this matters in AI:
- Canonical forms: two parse trees might represent the same formula even if
built differently; checking isomorphism tells you so.
- Subgraph matching: knowledge-graph queries often reduce to finding a target
pattern as a subgraph of a larger graph.
- Equivalence checking: are two programs structurally identical? Are two
logical formulas logically equivalent? Often reducible to graph isomorphism.

Note carefully: a tree (acyclic) cannot be isomorphic to a graph containing a
cycle — isomorphisms preserve the cycle / acyclic property. This is the key
argument behind exam problem 3.1.3: a parse tree cannot be isomorphic to a cyclic graph.

Animation — iso labels

Transcript — click a line to jump6 cues

0.0sGraph isomorphism
1.2sTwo graphs side by side: G1 as a square cycle, G2 as a diamond
3.0sBoth have four nodes and four edges — different shape, same count
4.8sPair each G1 node with a G2 node — both nodes turn amber
6.8sMatching edges between the pairings turn green — every edge maps
9.0sSame structure under a different labelling: G1 and G2 are isomorphic

Functional computation with labeled trees (SML)

Labeled binary trees (lbt) are easily represented in SML with a datatype and processed recursively.


datatype lbt = Leaf of string
             | Node of string * lbt * lbt;

The recursive weight function (sum of leaf labels as integers):


fun weight (Leaf s)      = valOf (Int.fromString s)
  | weight (Node (_, l, r)) = weight l + weight r;

For trees whose leaves may be non-numeric, a helper extracts numeric weight:


fun wt (Leaf s)       = wt_aux s
  | wt (Node (_, l, r)) = wt l + wt r
and wt_aux s =
    case Int.fromString s of
         SOME n => n
       | NONE   => 0;

The and keyword introduces mutual recursion — wt and wt_aux call each other.

DAGs as trees with sharing. A DAG (directed acyclic graph) is a tree where multiple parents may point to the same subtree. We model sharing by giving each node an identifier and a list of references:


datatype dag = DagNode of { id : int, label : string, refs : int list };

The refs field lists the ids of child nodes; the actual node table is kept separately. The explode function turns a DAG into a tree by copying shared subtrees:


fun explode node =
    case lookup node of
         DagNode { id, label, refs } =>
            Node (label, map (explode o lookup) refs);

Without sharing, explode may exponentially expand a DAG; with memoisation (a dict from id to already-exploded tree) it stays linear in DAG size.

Worked example

Step 0 of 2

Practice — score 100% to advance

Multiple choice

An isomorphism between graphs

G

and

G'

is a…

Why does a parse tree never be isomorphic to a cyclic graph?

What is the labeled graph

G = \langle V, E, L, l \rangle

Which is an invariant preserved by isomorphism?

Two graphs with different degree sequences are…

In SML, mutually recursive functions are declared with:

Match definitions

Match each concept on the left to its definition on the right.

Order the steps

Arrange these proof steps in the correct order using the arrows.

Compare edge counts and other invariants

Compute degree sequences for both graphs

Verify

(u, v) \in E \iff (\psi(u), \psi(v)) \in E'

for all pairs

If invariants match, attempt to build a bijection

\psi

Loading…