Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
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. –  gary Sep 12 '11 at 0:36
    
Interesting -- what is the best algorithmic way to determine the maximal spanning tree? Thanks for your help! –  Jason Sep 12 '11 at 14:48
    
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 . –  gary Sep 12 '11 at 16:20
    
thanks gary. do you have a link to the proof? –  Jason Sep 12 '11 at 17:47
    
No problem; here is the proof; I posted this question to some other site: at.yorku.ca/cgi-bin/… . 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. –  gary Sep 12 '11 at 18:05
show 3 more comments

1 Answer

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

share|improve this answer
    
Correct: if $T$ is a spanning tree of the graph, then $\pi_1(X)$ is freely generated "by" the vertices in $X$ that are not in $T$. But you don't need to find the maximal spanning tree, you just need to count how edges it has. Since a connected tree with $n$ vertices has $n-1$ edges, the formula follows. –  Arturo Magidin Sep 16 '11 at 20:28
    
@Arturo I think you meant "edges" in the first line. :) –  Srivatsan Sep 16 '11 at 21:21
    
@Srivatsan: Oops; quite so. Too bad I can't edit it anymore... –  Arturo Magidin Sep 17 '11 at 4:20
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.