Graph Theory37 sections · 1633 units
Open in Course

Example Graph

(Visualizing the structure)

Consider nodes 11 through 66 where f(1)=2f(1) = 2, f(2)=3f(2) = 3, f(3)=4f(3) = 4, f(4)=3f(4) = 3, f(5)=6f(5) = 6, f(6)=6f(6) = 6. Each node has exactly one outgoing edge. From node 11: you go 1234341 \to 2 \to 3 \to 4 \to 3 \to 4 \to \ldots The tail is 121 \to 2, and the cycle is 3433 \to 4 \to 3.

The tail has length 22, the cycle has length 22. From node 66: you stay at 66 forever. A self-loop is a cycle of length 11. Every node eventually reaches a cycle, possibly immediately.