Basic Theory

    Digraph self-similarity is an important generalization of self-similarity.  A set is called self-similar if it is composed of several scaled images of itself.  The Koch curve shown below, for example, is composed of four copies of itself, each scaled by the factor .  

    Digraph self-similarity is exhibited by a collection of sets, each of which is composed of scaled images chosen from the collection.  Considering the two curves and shown below, for example,    is composed of 1 copy of itself, scaled by the factor , and 2 copies of , rotated and scaled by the factor    is composed of 1 copy of itself, scaled by the factor and 1 copy of , reflected and scaled by the factor

    Any digraph self-similar set may described using a directed-graph iterated function system, or digraph IFS.
The first indgredient for a digraph IFS is a directed multi-graph, or digraph, which describes the combinatorics of how the pieces fit together.  The digraph for the curves and is shown below.  There are two edges from node to node and one edge from node to itself since consists of two copies of together with one copy of itself.  Similarly, there is one edge from node to node and one edge from to itself since consists of one copy of together with one copy of itself.

    Note that the edges in the digraph above are labeled.  These correspond to affine images which map one set to part of another.  For example, maps onto part of   The exact affine functions are shown below.