¿Un algoritmo para calcular el rango del grupo fundamental de un gráfico?

Question

He estado aprendiendo un poco sobre las aplicaciones de la topología algebraica a la teoría de los gráficos y estoy interesado en averiguar cómo calcular el grupo fundamental $ \pi_1 (X,x_0)$ de un gráfico arbitrario $G=(V,E)$ . Me parece que se podría usar un simple DFS para calcular el número de ciclos distintos con cualquier $x_0$ como el punto base. Eso te daría el número de generadores en $ \pi_1 (X,x_0)$ y sabrías que es sólo el grupo libre sobre esos generadores. ¿Estoy fuera de la base? Si no, ¿es la forma más eficiente de hacerlo? Estoy bastante seguro de que no puedo (en general) usar ninguna fórmula simple como la característica de Euler...

Answer 1

En caso de que alguien más quiera saber la respuesta, lo he averiguado. El grupo fundamental $ \pi_1 (X)$ de un gráfico $X=(V,E)$ es el grupo libre de $k$ generadores, $k = 1 - |V| + |E|$ ,. Esto está dado por $ 1 - \chi $ donde $ \chi $ es la característica habitual de Euler, $V-E$ .