- a graph is rooted if it has a single root
- a tree is a rooted graph G in which there is a
unique path from the root to every other node in G
- a node is a leaf if it is not the source of any edge
- graphs can have node labels and/or edge labels
- in an edge-labelled graph G = (N,E,FE),
FE is an edge labelling function that maps
each edge to a label
- in a node-labelled graph G = (N,E,FN),
FN is a node labelling function that maps
each node to a label
