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

$\endgroup$
8
  • 2
    $\begingroup$ 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. $\endgroup$
    – gary
    Sep 12, 2011 at 0:36
  • $\begingroup$ Interesting -- what is the best algorithmic way to determine the maximal spanning tree? Thanks for your help! $\endgroup$
    – William
    Sep 12, 2011 at 14:48
  • $\begingroup$ 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 . $\endgroup$
    – gary
    Sep 12, 2011 at 16:20
  • $\begingroup$ thanks gary. do you have a link to the proof? $\endgroup$
    – William
    Sep 12, 2011 at 17:47
  • $\begingroup$ 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. $\endgroup$
    – gary
    Sep 12, 2011 at 18:05

1 Answer 1

4
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$ Sep 16, 2011 at 20:28
  • $\begingroup$ @Arturo I think you meant "edges" in the first line. :) $\endgroup$
    – Srivatsan
    Sep 16, 2011 at 21:21
  • $\begingroup$ @Srivatsan: Oops; quite so. Too bad I can't edit it anymore... $\endgroup$ Sep 17, 2011 at 4:20
  • 3
    $\begingroup$ To 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. $\endgroup$ Dec 22, 2016 at 21:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .