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 X\times \mathcal X$ with fixed points of $f^n$ being exactly cycles of length $n$.