# Name for the tree formed after collapsing cycles

What do you call a structure which becomes a tree after collapsing cycles (so the new vertices are the old faces)? For instance, the digraph (given by an NFA; ignore edge labels please) below becomes a tree $$\{a,b,c,d\}$$ with edges $$(a,b), (b,c), (b,d)$$ via: $$\begin{eqnarray*} a\mapsto&\text{the cycle }&S_0,S_1,S_2,S_3,S_4,S_5,S_6,S_7,S_0 \\ b\mapsto &\text{the cycle }&S_5,S_6,S_7,S_8,S_9,S_{10},S_{11},S_{12},S_5\\ c\mapsto &\text{the cycle }&S_8,S_9,S_8\\ d\mapsto &\text{the cycle }&S_{10},S_{11},S_{12},S_{10} \end{eqnarray*}$$

• How are you collapsing loops? Every acyclic connected graph is a tree, so if your collapsing doesn't disconnect the graph you'll always end up with a tree. – Stella Biderman Nov 26 '18 at 17:21
• I edited your question to replace "loops" with "cycles": a loop is an edge from a vertex to itself. But I can't tell what you're asking, here. First, what do you mean by "collapsing"? Second, what do you mean by "a tree like $\{0,00,000,001\}$? Third, are these graphs or automata? Those aren't the same thing but you talk about them as if they are. – David Richerby Nov 26 '18 at 17:58
• @DavidRicherby thanks for the point about cycles vs. loops. I've edited to clarify the rest. – Bjørn Kjos-Hanssen Nov 26 '18 at 18:31
• OK but you need to give a definition, not just an example. Actually, I don't understand your example at all. Going round the cycle $S_{10}S_{11}S_{12}S_{10}$ generates the string $110$, not $01$; So where do these strings come from? – David Richerby Nov 26 '18 at 18:34
• my guess it that these graphs are the series parallel graphs, or equivalently graphs that are K4-minor-free – Hendrik Jan Nov 27 '18 at 3:20

For any given undirected graph $$G$$, the cycle graph $$C(G)$$ has vertices which correspond to the chordless cycles of $$G$$, and two distinct vertices of $$C(G)$$ are adjacent if and only if the corresponding chordless cycles have at least one edge in common. [1]
• Thanks, I wonder whether chordless cycles is the right concept though, since the cycle $b$ in my example is apparently not chordless – Bjørn Kjos-Hanssen Dec 11 '18 at 1:49