2
$\begingroup$

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*} Complexity witness

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Stella Biderman Nov 26 '18 at 17:21
  • 1
    $\begingroup$ 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. $\endgroup$ – David Richerby Nov 26 '18 at 17:58
  • $\begingroup$ @DavidRicherby thanks for the point about cycles vs. loops. I've edited to clarify the rest. $\endgroup$ – Bjørn Kjos-Hanssen Nov 26 '18 at 18:31
  • $\begingroup$ 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? $\endgroup$ – David Richerby Nov 26 '18 at 18:34
  • $\begingroup$ my guess it that these graphs are the series parallel graphs, or equivalently graphs that are K4-minor-free $\endgroup$ – Hendrik Jan Nov 27 '18 at 3:20
1
$\begingroup$

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]

Judging from your example, you are interested in a similar notion for a directed graph.

[1] S.V. Gervacio. Cycle graphs. Lect. Notes Math. 1073, 279-293 (1984)

$\endgroup$
  • $\begingroup$ Thanks, I wonder whether chordless cycles is the right concept though, since the cycle $b$ in my example is apparently not chordless $\endgroup$ – Bjørn Kjos-Hanssen Dec 11 '18 at 1:49
  • $\begingroup$ A face-defining cycle is chordless. $\endgroup$ – Vincenzo Dec 11 '18 at 9:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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