Graphen

$K$ Knoten

$E \subseteq K \times W \times K$ Kanten (Markierung $w$ dass von einem Knoten zum nächsten führt)

$L: K \mapsto U$ Knotenmarkierungs-Funktion

Wenn es eine bijektive Funktion gibt die alle Kanten mit der gleichen Markierung zueinander mapped.

commonly described as "edge-preserving bijection”

$g=(K, E, L)$

$g^{\prime}=\left(K^{\prime}, E^{\prime}, L^{\prime}\right)$

Bijektive Funktion $\exists f:K \mapsto K'$ sodass $\forall k,l\in K$ und $\forall w \in W:$

Obere Bedingung und zusätzlich auch alle Knoten mit gleicher Markierung zueinander mappen.

$\forall k\in K: L(k)=L^{\prime}(f(k))$

• $\exists n \geq 1: W=\{1, \ldots, n\}$

• Jeder Knoten außer der Wurzelknoten $p_0$ hat genau einen Vorgänger.

• Es gibt von $p_0$ zu jedem anderen Knoten $q$ einen Pfad mit Länge $k \geq 1$ :

  $\left(p_{0}, e_{1}, p_{1}, \ldots, p_{k-1}, e_{k}, q\right)$ wobei

  $\left(p_{i}, e_{i+1}, p_{i+1}\right) \in E, ~~0 \leq i<k, ~~q=p_{k}$

• Jeder Knoten ohne Nachfolger heißt Blatt

• Wenn $p$ Nachfolger hat, sind sie geordnet / die Kanten sind numeriert von $1$ bis bestimmtes $k$ .