trouver un petit cycle dans un graphe planaire

Question

J'ai un graphe planaire non géométrique, à savoir un graphe dans lequel chaque nœud a un emplacement. et 2 arêtes ne se croisent pas et je veux trouver tous les cycles sans arêtes qui les traversent.

Existe-t-il de bonnes solutions à ce problème?

Ce que je prévois de faire est une sorte de A * comme solution:

• insère chaque chemin dans un tas min en tant que chemin
• étendre le chemin le plus court avec chaque option
• les chemins de rejet qui sont renvoyés en boucle autre que leur début (peut ne pas être nécessaire)
• chemins de sélection qui seraient le troisième à utiliser un bord donné

Quelqu'un voit-il un problème avec cela? Cela fonctionnera-t-il même?

Answer 1

Mon premier réflexe est d’utiliser une méthode similaire à un solutionneur de labyrinthe de mur. En gros, suivez les arêtes et prenez toujours l'arête la plus à droite d'un sommet. Tous les cycles que vous rencontrez avec cette méthode seront les limites d'un visage. Vous devrez suivre les bords que vous avez traversés dans quelle direction. Une fois que vous avez traversé un bord dans les deux sens, vous avez identifié les faces qu'il sépare. Une fois que toutes les arêtes ont été traversées dans les deux sens, vous aurez identifié toutes les faces par leurs limites.

Answer 2

Un "point de passage", comme vous l'appelez, est généralement appelé accord . . Votre problème est donc de trouver tous les cycles sans accords.

Ce document semble pouvoir être utile.

Answer 3

Un moyen simple de le faire est simplement d’énumérer chaque visage. Le principe est simple:

• Nous conservons des drapeaux "a-Visité" et "ß-visité" pour chaque bord, ainsi qu'une paire de listes doublement chaînées d'arêtes non visitées pour chacun de ces drapeaux. Les divisions "a" et "ß" doivent correspondre à une partition du plan sur la ligne correspondant à l'arête en question; quel côté est a et quel côté est ß est arbitraire.
• Pour chaque sommet V:
  • Pour chaque paire d'arêtes adjacentes E = (V_1, V), E '= (V_2, V) (c'est-à-dire, triez par angle, prenez des paires adjacentes, ainsi que le premier + dernier):
  • Déterminez le côté S de E (S = a ou ß) V_2 qui se trouve.
  • Parcourez la tuile à partir de V en utilisant le côté S de E, comme décrit ci-dessous:

La marche de la tuile est effectuée par:

• Soit V = V_init
• boucle:
  • V_next = le sommet de E qui n'est pas V
  • E '= le bord adjacent à E de V_next situé sur le côté actuel de E
  • S '= le côté de E' contenant V
  • Si V_next = V, nous avons trouvé une boucle; enregistrez toutes les arêtes que nous avons empruntées et marquez ces paires d'arêtes comme visitées.
  • Si E '= E (il n'y a qu'un seul bord), alors nous sommes dans l'impasse; abandonner cette promenade
  • Sinon, passons V = V_next, E = E ', S = S' et continuez.

J'espère que cela a du sens; il faut peut-être des diagrammes pour expliquer ...