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...
Algorithm for computing the rank of the fundamental group of a graph?
7
$\begingroup$
algebraic-topology
algorithms
graph-theory
-
0Please give me a little bit of time; I will be busy for a few days, but I will look into it. – 2011-09-13
1 Answers
4
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$.
-
2To be clear, this is correct for connected graphs. For possibly disconnected graphs, you need to count just the vertices and edges in the component of the basepoint. – 2016-12-22