6
$\begingroup$

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

  • 2
    You 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
  • 0
    Interesting -- what is the best algorithmic way to determine the maximal spanning tree? Thanks for your help!2011-09-12
  • 0
    I'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
  • 0
    thanks gary. do you have a link to the proof?2011-09-12
  • 0
    No 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
  • 0
    See too, re the above comment: http://en.wikipedia.org/wiki/Schreier's_subgroup_lemma2011-09-12
  • 0
    Cool, 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
  • 0
    Please 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 1