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$.