notes

Personal notes
git clone git://git.laack.co/notes.git
Log | Files | Refs

SuccessorGraph.md (1051B)


      1 # Successor Graph
      2 
      3 **Source:** Competitive Programmer's Handbook Ch 16
      4 
      5 **Definition:** A successor graph is a directed graph where the out-degree of every node is exactly 1. 
      6 
      7 ## Implication
      8 
      9 Since each node has an out-degree of 1, a successor graph with $n$ vertices has $n$ edges. This means the graph must have at least one cycle. Specifically, successor graphs must have one cycle per connected component. 
     10 
     11 Since each vertex has one edge, there's a function $f: V \to V$ where V is the set of all vertices, and $f(v_i) = v_j$ where $v_j$ is the successor to $v_i$. For this reason, successor graphs are sometimes called functional graphs.
     12 
     13 Additionally, we may also define a function $s: V \times \mathbb{N} \to V$ such that $s(v_i,k)$ is the vertex that will be reached from $v_i$ after walking $k$ steps forwards.
     14 
     15 This successor function may be naively evaluated by performing a walk, with a worst case asymptotic time complexity of $O(k)$, but a better approach that involves pre-processing is in the complexity class of $O(\text{log}(n))$.