I think this is how you can construct the required homology theory:
- $n$-chains = maps of chain graphs $[n] = 0 \to 1 \to \dots\to n$ into your graph (where, perhaps, one edge of $[n]$ maps to many edges of your graph)
- boundary comes from the natural boundary operator on $[n]$ which leaves exactly one point and takes the alternating sum
With these definitions, you have $d^2 = 0$ as usual.
Example computation for a circle of $n$ points: chain that wraps the circle is not exact, since the wrapping number of $d$ of any chain is 0. Update: we have to write definition of a chain more carefully, since it's not clear that this chain is closed.
As for Lefschetz, it holds for the computation since your map $f$ takes a vector of points $P$ into $\mathbf AP$.
It looks like you're constructing a nerve of the category of (vertices, paths); the geometric realization $\mathcal X$ of that nerve should have cohomology that indeed describe your dynamic system. Your incidence matrix naturally defines a correspondence $f$ on $\mathcal f\subset\mathcal X\times \mathcal X$ with fixed points of $f^n$ being exactly cycles of length $n$.
I think one can see that this $f$ acts as identity on all homology, so it seems that your fixed points formula has the required form.