In der Graphentheorie ist ein Kaktus ein zusammenhängender Graph, so dass zwei verschiedene einfache Zyklen im Graph höchstens einen Scheitelpunkt gemeinsam haben.

Hier ist ein Kaktus mit 3 einfachen Zyklen, die mit gestrichelten Linien dargestellt sind.

Das folgende Diagramm ähnelt dem oben abgebildeten, ist jedoch kein Kaktus, da die beiden rot markierten Scheitelpunkte von zwei einfachen Zyklen geteilt werden.

Die Dinge können etwas kniffliger werden, zum Beispiel die folgende Grafik:

Sieht vielleicht aus wie ein Kaktus, ist es aber nicht. Dies kann durch Hervorheben des folgenden Zyklus gezeigt werden:

Dieser Zyklus hat mehr als einen Punkt gemeinsam mit vielen offensichtlicheren Zyklen in der Grafik.

Definitionen

Ein verbundener Graph ist ein Graph, bei dem mindestens ein Pfad zwischen zwei beliebigen Scheitelpunkten vorhanden ist.
Ein einfacher Zyklus ist ein Pfad in einem Diagramm, der am selben Scheitelpunkt beginnt und endet und keinen Scheitelpunkt mehr als einmal besucht.
Ein einfacher Graph ist ein ungerichteter, ungewichteter Graph, bei dem keine Scheitelpunkte durch mehr als eine Kante miteinander verbunden sind und kein Scheitelpunkt mit sich selbst verbunden ist. Ein einfaches Diagramm ist der grundlegendste Diagrammtyp und das, was die meisten Leute meinen, wenn sie Diagramm sagen.

Aufgabe

Nehmen Sie einen einfachen Graphen als Eingabe und entscheiden Sie, ob es sich um einen Cactus-Graphen handelt. Sie sollten zwei unterschiedliche Werte ausgeben, einen für True und einen für False. Sie können Eingaben in jedem Format vornehmen, das Sie für richtig halten.

Dies ist Codegolf, daher sollten Sie darauf abzielen, die Anzahl der Bytes Ihrer Antworten zu minimieren.

Testfälle

Testfälle als Adjazenzmatrizen

code-golf decision-problem graph-theory Weizen-Assistent
quelle

Können Sie sich meine Lösung ansehen und mir mitteilen, ob sie gültig ist? Ich fiel auf, als wäre das offensichtliche Muster zu offensichtlich und ich hätte etwas verpasst.

Shaggy

@Shaggy Ich kann kein JavaScript lesen. Wenn du es erklärst, kann ich es möglicherweise.

Weizen-Assistent

Ich kann es versuchen. Ich überprüfe auf 2 Dinge: 1) Enthält egenau ein Element UND venthält genau 2 UND ist vgleich dem ersten Element von e? 2) ODER Ist vgleich der Vereinigungsmenge der ersten Elemente jedes Elements in e? Der zweite Testfall besteht die erste Prüfung ( v=[1,2]=e[0]=[1,2]) und die anderen Testfälle, die wahr sein sollten, stimmen mit dem zweiten überein, z 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 Dies funktioniert nicht, zum Beispiel schlägt das erste bereitgestellte Diagramm fehl.

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

Weizen-Zauberer

Sollte das zurückkehren trueoder false?

Shaggy

Ist es ein Kaktus?

Definitionen

Aufgabe

Antworten:

Mathematica, 62 Bytes