Finden Sie alle chordless Zyklen in ungerichteten Graphen
So finden Sie alle chordless Zyklen in einem ungerichteten Graphen?
Beispielsweise angesichts der graph
0 --- 1
| | \
| | \
4 --- 3 - 2
sollte der Algorithmus zurück 1-2-3 und 0-1-3-4, aber nie 0-1-2-3-4.
(Hinweis: [1] Diese Frage ist nicht das gleiche wie die kleine-Zyklus finden in einem planaren Graphen, weil der graph nicht notwendigerweise planar. [2] ich habe gelesen das Papier Erzeugen alle Zyklen, chordless Zyklen, und Hamilton-Zyklen mit dem Prinzip der Ausgrenzung aber ich verstehe nicht, was Sie tun :). [3] ich habe versucht CYPATH aber das Programm gibt nur die Anzahl, Algorithmus EnumChordlessPath in readme.txt hat erhebliche Tippfehler, und der C-code ist ein Chaos. [4] ich bin nicht versuchen zu finden, einen beliebigen Satz von fundametal Zyklen. Zyklus haben können Akkorde.)
- Keine Einschränkung, aber das wäre zu ineffizient.
- Ich habe nicht viel gutes tun, veröffentlichen Sie einen link zu einem paper hinter einer paywall.
- manchmal ist es nicht -- Verweise auf Papiere sind nützlich, + ACM ist nicht genau einer obskuren Fachzeitschrift. (obwohl ich don ' T haben Zugang zu Ihr)
- Gibt es mehr als einen Weg, der Bau von Rad-Basen? Etwas scheint faul hier... sieht aus wie chordless Zyklen bilden eine basis, aber ich könnte etwas fehlen offensichtlich.
- ja. Betrachten Sie das komplette 4-Graphen, die hat 4 verschiedene Möglichkeiten zur Auswahl einer basis (3 Dreiecke). Es kann mehr chordless Zyklen als die Anzahl der basis.
- Warum ist ein math.sx-moderator, diese Frage hier? Sind Sie nach Implementierungen? Frage: "gibt es irgendwelche interessanten Eigenschaften der Klasse von chordless Diagramme, die mir helfen würden, generieren Sie effizient?" klingt wie ein nützlicher Ausgangspunkt für mich, da es scheint, dass Ihre motivation ist, um ein Gefühl für die Suche nach Raum, nicht nur werfen gemeinsam einen hack.
- Natürlich bin ich nach der Durchführung, oder ein Algorithmus, der geschrieben ist in pseudo-code, der einfach umgesetzt werden können.
- Ich hatte nicht darauf geachtet, um das [language-agnostic] - tag, sorry. Aber wenn Sie kümmern sich um Umsetzung, nicht Sie haben eine Art worst-case-performance-Einschränkung beachten? aioobe die Lösung ist nur in EXPTIME, das ist durchaus machbar, wenn n begrenzt ist durch eine kleine Konstante...
- Wie unterscheidet sich dies von der Suche nach dem minimum cycle basis eines Graphen? (stackoverflow.com/questions/16782898/...)
- Dies könnte nützlich sein: arxiv.org/pdf/1309.1051.pdf
Du musst angemeldet sein, um einen Kommentar abzugeben.
Ordnen Sie die Nummern der Knoten von 1 bis n.
Wählen Sie den Knoten Nummer 1. Nennen Sie es 'A'.
Aufzählen paar links, die kommen aus 'A'.
Pick. Nennen wir die benachbarten Knoten 'B' und 'C' mit B weniger als C
Wenn B und C verbunden sind, dann ausgeben der Zyklus ABC, kehren Sie zu Schritt 3 und wählen Sie eine andere paar.
Wenn B und C nicht miteinander verbunden sind:
Wiederholen Sie, bis Sie laufen aus Vektoren.
Wiederholen Sie die Schritte 3-5 mit allen Paaren.
Entfernen Sie Knoten 1 und alle links, die zu Ihr führen. Wählen Sie den nächsten Knoten, und gehen Sie zurück zu Schritt 2.
Edit: und Sie tun können, Weg mit einer verschachtelten Schleife.
Diese scheint zu funktionieren auf den ersten Blick, es mag bugs haben, aber Sie sollte auf die Idee kommen:
@aioobe hat einen Punkt. Finden Sie einfach alle Zyklen und schließen Sie die nicht-chordless lieben. Dies kann zu ineffizienten, aber der Suchraum kann beschnitten werden, auf dem Weg zur Reduzierung der Ineffizienzen. Hier ist ein allgemeiner Algorithmus:
Wie über dieses. Reduzieren Sie zunächst das problem zu finden, alle chordless Zyklen Durchlaufen einen bestimmten Scheitelpunkt A. Sobald Sie gefunden haben, alle diese, können Sie entfernen aus dem Graphen, und wiederholen Sie mit einem anderen Punkt, bis es nichts mehr übrig.
Wird und wie Sie alle chordless Zyklen Durchlaufen vertex Ein? Reduzieren Sie diese zu finden, alle chordless Pfade von B nach A, eine Liste der erlaubten vertices, und Suche entweder zuerst der Breite oder Tiefe-zuerst. Beachten Sie, dass bei der Iteration über die Eckpunkte erreichbar (in einem Schritt) von B, wenn Sie einen von Ihnen wählen, die Sie entfernen müssen alle anderen von der Liste der erlaubten vertices (nehmen Sie Besondere Vorsicht, wenn B=A, so nicht zu beseitigen, drei-edge-Pfade).
Nur ein Gedanke:
Lassen Sie uns sagen, Sie sind der Aufzählung von Zyklen auf Ihre Beispiel-Diagramm, und Sie werden ausgehend von dem Knoten 0.
Wenn Sie eine Breite-zuerst-Suche für jeden gegebenen Rand, z.B. 0 - 1, Sie erreichen eine Gabelung, bei der 1. Dann werden die Zyklen, die den Wert 0 erreichen wieder die ersten sind chordless, und der rest sind nicht und können beseitigt werden... zumindest glaube ich, dass dies der Fall ist.
Könnte man einen Ansatz verwenden, der wie dieser? Oder gibt es ein Gegenbeispiel?
Finden Sie alle Zyklen.
Definition von einem chordless-Zyklus ist eine Reihe von Punkten, in denen eine Teilmenge Zyklus dieser Punkte nicht vorhanden sind. Also, wenn Sie alle Zyklen problem ist ganz einfach zu beseitigen Zyklen, in denen eine Teilmenge Zyklus.
Für Effizienz, für jeden Zyklus, die Sie finden, eine Schleife über alle vorhandenen Zyklen und stellen Sie sicher, dass es keine Teilmenge eines anderen Zyklus oder Umgekehrt, und wenn ja, beseitigen Sie die größeren Zyklus.
Darüber hinaus, nur die Schwierigkeit ist, herauszufinden, wie schreibt man einen Algorithmus, der bestimmt, ob eine Menge eine Teilmenge der anderen ist.