I've been learning a bit about applications of algebraic topology to graph theory and I'm interested in figuring out how to compute the fundamental group $\pi_1(X,x_0)$ of an arbitrary graph $G=(V,E)$. It seems to me you could use a simple DFS to compute the number of distinct cycles with any arbitrary $x_0$ as the base point. That would give you the number of generators in $\pi_1(X,x_0)$ and you'd know it's just the free group over those generators. Am I off base? If not, is that the most computationally efficient way to go about it? I'm pretty sure I can't (in general) use any simple formula like the Euler chracteristic...
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
In case anyone else wants to know the answer, I figured it out. The fundamental group $\pi_1(X)$ of a graph $X=(V,E)$ is the free group on $k$ generators, $k = 1 - |V| + |E|$,. This is given by $ 1 - \chi$, where $\chi$ is the usual Euler characteristic, $V-E$.