I am a computer science student working in graph algorithms. I am unable to understand what the fundamental group of a graph means. I have some intuition regarding the fundamental group of a topological space and homotopy equivalence (capturing smooth transformation of closed paths, and "holes" in the space).
But in the case of a graph, what exactly is the topology (open sets) defined on it to talk about fundamental groups and homotopy? Or am I wrongly mixing up very different notions with the same name?
Also, could someone provide elementary references on this with examples? The references I found are all too rigorous with algebraic topology machinery, and unsuitable for big picture intuition and quick learning through examples, which is what I want to start with for now. If that is not possible, do suggest a linear sequence of topics I need to be familiar with so that I can get a working knowledge of fundamental groups of graphs (I noticed mentions of covering spaces, but I digressed with that and am not sure how to proceed). I am interested in its relationship with Cayley graphs and the Ihara zeta function, which I hope to get into once I clear up the fundamentals.
Thanks.
It is the same concept as the fundamental group in topology. The topological space in question is simply a drawing of the graph (with non-intersecting edges, so the drawing may have to live on a surface of positive genus) -- in other words there's a point for each vertex, and each edge is represented by its own copy of the unit interval, glued to its endpoints in the "obvious" way.
A closed path in this graph is then essentially the same as a circuit in the graph. The only difference is that a topological path may reach a vertex, then go halfway out along an edge and then double back to the same vertex -- but that is obviously homotopic to not going out on that edge at all, so it makes no difference for homotopy purposes.
Assuming that the graph is connected, it turns out that the fundamental group is always a free group. You can construct it by selecting a rooted spanning tree, and then considering the edges not in the spanning tree "special". Every path is then homotopic to a sum of simple circuits that go from the root along the spanning tree to one end of a special edge, then along the edge and back to the root along the spanning tree. These circuits generate the fundamental group, and have no relations except for those implied by the group axioms.