23
4
In graph theory, a Cactus is a connected graph such that any distinct two simple cycles in the graph share at most one vertex.
Here is a Cactus with 3 simple cycles outlined with dashed lines.
The following graph is similar to the one pictured above but is not a Cactus because the two vertices labeled in red are shared by two simple cycles.
Things can get a little bit trickier, for example the following graph:
Might look like a Cactus but it is not. This can be shown by highlighting the following cycle:
This cycle shares more than one point with a lot of the more obvious cycles in the graph.
Definitions
A connected graph is a graph such that there exists at least one path between any two vertices.
A simple cycle is a path on a graph that starts and ends at the same vertex and visits no vertex more than once.
A simple graph is an undirected, unweighted graph such that no vertices are connected two each other by more than one edge and no vertex is connected to itself. A simple graph is the most basic type of graph and is what most people mean when they say graph.
Task
Take a simple graph as input and decide whether it is a Cactus graph. You should output two distinct values one for True and one for False. You may take input in any format you see fit.
This is code-golf so you should aim to minimize the byte count of your answers.
Post Rock Garf Hunter
Posted 2017-05-14T18:50:48.463
Reputation: 55 382
Can you have a look at my solution, let me know if it's valid? I fell like the obvious pattern was too obvious and that I've missed something. – Shaggy – 2017-05-18T10:24:07.270
@Shaggy I can't read JavaScript, If you explain it I might be able to. – Post Rock Garf Hunter – 2017-05-18T15:01:18.857
I can try. I'm checking for 2 things: 1) Does
econtain exactly one element AND doesvcontain exactly 2 AND isvequal to the first element ofe? 2) OR Isvequal to the union set of the first elements of each element ine? The second test case passes the first check (v=[1,2]=e[0]=[1,2]) and the other test cases that should be true match the second, e.g. case#4:v=[1,2,3,4,5,6]=[e[0][0],e[1][0],e[2][0],e[4][0]]=[1,2,3,4,5,6]. – Shaggy – 2017-05-18T15:10:15.107@Shaggy This does not work for example the first diagram provided fails.
console.log(f([1,2,3,4,5,6,7,8,9,10,11,12,13])([[1,2],[1,3],[3,4],[2,4],[3,5],[5,6],[6,7],[7,8],[8,5],[7,9],[9,10],[10,11],[11,7],[8,12],[8,13]]))– Post Rock Garf Hunter – 2017-05-18T15:31:11.417Should that return
trueorfalse? – Shaggy – 2017-05-18T15:34:44.960@Shaggy It should be true. – Post Rock Garf Hunter – 2017-05-18T15:35:30.670
Ah, nuts! Could you add that to the test cases, please? – Shaggy – 2017-05-18T15:46:46.923