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?
6
$\begingroup$
algebraic-topology
algorithms
graph-theory
-
2You can argue, for each connected component K of the graph G, that you can find a spanning tree for K, then the edges of G-T generate the fundamental group; each loop based at p will pass thru an edge in G-T; conversely, for every edge in G-T, you define a unique loop. – 2011-09-12
-
0Interesting -- what is the best algorithmic way to determine the maximal spanning tree? Thanks for your help! – 2011-09-12
-
0I'm not a programmer, but let me think things thru more carefully and see what I can come up with; the proof of the existence of the tree is constructive, so it would not be too hard to turn it into an algorithm . – 2011-09-12
-
0thanks gary. do you have a link to the proof? – 2011-09-12
-
0No problem; here is the proof; I posted this question to some other site: http://at.yorku.ca/cgi-bin/bbqa?forum=ask_a_topologist;task=show_msg;msg=1979.0001 . You may also want to look into the Schreier Subgroup Lemma, which allows you to find the stabilizer of an element under a group action; an element of the stabilizer of some g in the graph G can be seen as a loop based at g. The Schreier subgroup lemma is an application of Reidemeister-Schreier to finding a generating set for a subgroup H og a group G using a transversal T for the quotient group G/H. – 2011-09-12
-
0See too, re the above comment: http://en.wikipedia.org/wiki/Schreier's_subgroup_lemma – 2011-09-12
-
0Cool, thanks! Interesting stuff. I found what I think is a pretty easy way to do it for a finite graph (http://math.stackexchange.com/questions/64192/the-fundamental-group-of-k-3-3-relationship-between-its-generators-and-embed) but I'm still a little confused, because I keep getting the Euler characteristic V - E for the utility graph K_{3,3} to be 4, meaning its fundamental group is free on 4 generators, which confuses me because I know it can be embedded in the torus. what am I missing? – 2011-09-13
-
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