kleiner Zyklus Befund in einem planaren Graphen

Question

I ein geometrisches ungerichteten planar Graph , das ist ein Diagramm, in dem jeder Knoten eine Stelle hat und keine zwei Kanten kreuzen, und ich möchte alle Zyklen finden, haben keine Kanten, sie kreuzen.

Gibt es gute Lösungen für dieses Problem bekannt?

---

Was ich plane, auf tut, ist eine Art A* ähnliche Lösung:

• insert jede Kante in einem Haufen min als Pfad
• erweitert den kürzesten Weg mit jeder Option
• Keulung Pfade, die Schleife zu anderen zurück, als dort zu starten (möglicherweise nicht erforderlich)
• ausgemerzte Pfade, die die dritte würde Ang gegebene Kante verwenden

Sieht jemand ein Problem damit? Wird es überhaupt?

Answer 1

Mein erster Instinkt ist, ein Verfahren ähnlich ein Wand folgenden Labyrinth-Solver zu verwenden. Im Wesentlichen folgen Kanten und immer den am weitesten rechts liegenden Rand aus einem Scheitelpunkt treffen. Irgendwelche Zyklen Sie mit dieser Methode begegnen Grenzen eines Gesichts sein. Sie werden verfolgt, welche zu halten haben Kanten Sie in welche Richtung durchquert haben. Sobald Sie eine Kante in beiden Richtungen durchlaufen haben, haben Sie die Gesichter identifiziert sie trennt. Sobald alle Kanten in beiden Richtungen durchlaufen wurden, finden Sie alle Gesichter in ihren Grenzen identifiziert haben.

Answer 2

A "crossing edge", wie Sie es nennen, ist allgemein bekannt als Akkord . So Ihr Problem ist es, alle Zyklen sehnenloser zu finden.

Dieses Papier wie es aussieht, kann helfen.

Answer 3

Ein einfacher Weg, dies zu tun, ist einfach jedes Gesicht zu gehen und aufzuzählen. Das Prinzip ist einfach:

• Wir pflegen ‚α-visited‘ und ‚β-visited‘ Flags für jede Kante und ein Paar von doppelt verketteten Listen von unvisited Kanten für jede solche Fahne. Die ‚α‘ und ‚β‘ die Division auf eine Partition der Ebene auf der Leitung entsprechend den Rand in Frage entsprechen; welche Seite ist α und welche Seite ist β willkürlich ist.
• Für jede Ecke V:
  • für jedes benachbarte Paar von Kanten E = (V_1, V), E '= (V_2, V) (das heißt, sortiert nach Winkel, benachbarte Paare nehmen, sowie erste + last):
  • Bestimmen, welche Seite von E S (S = α oder β) V_2 liegt an.
  • die Fliese Gehen, bei V beginnend mit Seite S von E, wie unten beschrieben:

Gehen die Kachel erfolgt durch:

• Sei V = V_init
• Loop:
  • V_next = die Ecke von E, die nicht V ist
  • E‘= die benachbarte Kante E von V_next, die auf der aktuellen Seite ist E
  • S '= Die Seite von E', die V
  enthält
  • Wenn V_next = V, wir haben eine Schleife gefunden; notieren alle Kanten wir auf dem Weg vorbei, und diese Randpaare markieren, wie besucht.
  • Wenn E‘= E (nur ein Rand ist), dann haben wir eine Sackgasse getroffen; abbrechen diese Wanderung
  • Andernfalls sei V = V_next, E = E 'S = S' und weiter.

Ich hoffe, diese sinnvoll; es braucht vielleicht einige Diagramme zu erklären ...