Ist es ein Kaktus?

23

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.

Cactus Graph

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

Nicht Cactus Graph

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

Auch kein Kaktusgraph

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

Markierter Zyklus

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 daher sollten Sie darauf abzielen, die Anzahl der Bytes Ihrer Antworten zu minimieren.

Testfälle

Testfälle als Adjazenzmatrizen

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

Antworten:

9

Mathematica, 62 Bytes

Sort@#==#⋃#&[Join@@FindCycle[#,∞,All]]&&ConnectedGraphQ@#&

Schecks: (find all cycles, there are no duplicate edges)und(The graph is a connected graph)

JungHwan min
quelle
1
gsollte sein #, richtig?
Genisis
6
Also sagst du mir, dass es kein isCactuseingebautes gibt? Ich bin enttäuscht.
Aaron
Jemand sollte einen schreiben.
Draco18s
Sie sollten Mathematica Simplified als separate Antwort angeben.
mbomb007
3
@ Aaron Es wäre, CactusQwenn es existiert, glaube ich.
NieDzejkob