En théorie des graphes, un Cactus est un graphe connecté tel que deux cycles simples distincts dans le graphe partagent au plus un sommet.

Voici un Cactus avec 3 cycles simples soulignés de lignes pointillées.

Le graphique suivant est similaire à celui illustré ci-dessus mais n'est pas un Cactus car les deux sommets étiquetés en rouge sont partagés par deux cycles simples.

Les choses peuvent devenir un peu plus compliquées, par exemple le graphique suivant:

Cela pourrait ressembler à un cactus, mais ce n'est pas le cas. Cela peut être montré en mettant en évidence le cycle suivant:

Ce cycle partage plus d'un point avec un grand nombre des cycles les plus évidents du graphique.

Définitions

Un graphe connecté est un graphe tel qu'il existe au moins un chemin entre deux sommets.
Un cycle simple est un chemin sur un graphique qui commence et se termine au même sommet et ne visite aucun sommet plus d'une fois.
Un graphe simple est un graphe non orienté et non pondéré, de sorte qu'aucun sommet n'est connecté entre eux par plus d'une arête et qu'aucun sommet n'est connecté à lui-même. Un graphique simple est le type de graphique le plus élémentaire et c'est ce que la plupart des gens veulent dire quand ils disent graphique.

Tâche

Prenez un graphique simple en entrée et décidez s'il s'agit d'un graphique Cactus. Vous devez générer deux valeurs distinctes, une pour True et une pour False. Vous pouvez prendre des contributions dans n'importe quel format que vous jugerez bon.

Il s'agit de code-golf , vous devez donc viser à minimiser le nombre d'octets de vos réponses.

Cas de test

Cas de test en tant que matrices d'adjacence

code-golf decision-problem graph-theory Assistant de blé
la source

Pouvez-vous jeter un œil à ma solution, faites-moi savoir si elle est valide? Je suis tombé comme si le schéma évident était trop évident et que j'avais raté quelque chose.

Shaggy

@Shaggy Je ne peux pas lire JavaScript, si vous l'expliquez, je pourrais le faire.

Wheat Wizard

Je peux essayer. Je vérifie 2 choses: 1) Contient eexactement un élément ET vcontient exactement 2 ET est végal au premier élément de e? 2) OU Est-il végal à l'ensemble d'unions des premiers éléments de chaque élément dans e? Le second cas de test passe le premier contrôle ( v=[1,2]=e[0]=[1,2]) et les autres cas de test qui devrait être vrai match de la deuxième, par exemple le cas n ° 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

@Shaggy Cela ne fonctionne pas, par exemple le premier diagramme fourni échoue.

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]]))

Wheat Wizard

Si ce retour trueou false?

Shaggy

Est-ce un cactus?

Définitions

Tâche

Réponses:

Mathematica, 62 octets