Discussion :

[deuzef68]

ça fait un joli cube!

oui visuellement c'est chouette

La solution me paraît correcte. Reste à savoir si elle te satisfait, car il y a quelque chose de pas entièrement naturel à devoir passer par un point C obligatoirement pour atteindre un point P

Visuellement...oui... mais intrinséquement par rapport à ce que je voudrais en faire...c'est même plutôt mieux...

et cela pourrait ajouter de la complexité plus tard selon ce que tu souhaites faire.

effectivement tu passes par une étape intermédiaire... qui pour détecter les circuits est beaucoup moins évidente...
mais cette nuit d'insomnie, encore , j'ai eu une idée... faut que je refasse quelques schémas...

ah aussi tu me disais qu'on pourrait déterminer une boucle au fait que tous les points tagué avaient tous des liens avec 2 autres points tagués
j'ai entrevu encore cette nuit un contre exemple... il faut que je le dessine et on en reparlera

D'un autre côté, la solution à laquelle j'ai pensé est tellement simple que je ne comprends pas que nous n'y ayons pas songé plutôt: il suffit d'identifier les points par leurs coordonnées (x, y) puisque les 6 directions sont:
D1 = ( 1, 0)
D4 = (-1, 0)
D2 = (-1, 1)
D5 = ( 1, -1)
D3 = ( 1, 1)
D6 = (-1, -1)

Après nous avons l'assurance que tout fonctionne puisque les calculs sont de l'arithmétique vectorielle tout ce qu'il y a de plus conventionnel.

si ça fonctionne pour D1 et D4 ... pour le reste tu oublies qu'il y a des angles à 30degrés...
les 3 axes auront des normes différentes sinon...
l'optique à la fin est de pouvoir tout représenter graphiquement donc si intérieurement on pouvait éviter de trinqueballer
des nombres à virgules...

[deuzef68]

Pour revenir à la recherche des boucles... quand tu disais "il y a une boucle quand tous les points tagués sont liés à 2 points tagués"

Si tu prends le cas suivant:


les liens en couleur ne sont là que pour visualiser plus facilement les boucles...

On commence en P1 et on crée les co-voisins et les voisins
on va sur P5 on fait idem
puis sur P8... idem
puis sur P10... idem
puis sur P11... idem
puis sur P12...idem
puis sur P14...idem
puis sur P9...idem

à ce stade on devrait détecter une boucle
mais si on prend le principe : "il y a une boucle quand tous les points tagués sont liés à 2 points tagués"
on ne la trouve pas puisqu'en P1 on a qu'un seul lien (en couleur) avec P2

Bon il est sûr que dans une boucle (celle en couleur) tous les points formant cette boucle sont liés à 2 points tagués

[deuzef68]

Pour trouver la liste des points tagué et liés entre eux pas très difficille

sur l'exemple suivant


en P1... pas la peine...au début il n'y a qu'une pièce...
par contre juste après avoir tagué P2
on prend la liste des P1..Pn et on recherche les voisins tagué de la façon suivante
on fait une recherche en "saute mouton"

on va vers le premier co-voisin puis on bifurque vers un des 2 voisins
ici nul besoin d'aller sur les 2 voisins lié au co-voisin, on obtiendrait des doublons.
Il faut juste choisir tout le temps le même sens.. ici je prends le sens direct des aiguilles d'une montre
il faut bien choisir, mais ça marche aussi à l'inverse

Etape 1:

ici de P1 vers C1 on se déplace suivant D2 -> donc on cherche le voisin suivant D4
(les liens en couleur)
P3 est-il tagué -> non donc on n'insère pas le lien P1-P3

Etape 2:

ici de P1 vers C2 on se déplace suivant D4 -> donc on cherche le voisin suivant D6
(les liens en couleur)
P4 est-il tagué -> non donc on n'insère pas le lien P1-P4

Etape 3:

ici de P1 vers C2 on se déplace suivant D6 -> donc on cherche le voisin suivant D2
(les liens en couleur)
P2 est-il tagué -> oui donc on insère le lien P1-P2 dans la liste des voisins tagué et liés

Etape 4:
On va sur le point suivant... ici P2 et on répète les étape 1 à 3

et ainsi de suite jusque Pn...
on a donc tous les Px tagués et lié entre eux...
maintenant il faut trouver un algo pour déterminer s'il y a boucle

[deuzef68]

J'ai trouvé encore un contre exemple
Dans le cas ci-dessous je n'ai dessiné que les pts tagués pas les voisins non tagué ni les co-voisins
et les liens en couleur sont évidemment fictifs mais sont là pour mieux visualiser les boucles


dans ce cas ci les points ont tous au moins 2 liens avec des pts tagué...
on pourrait donc penser qu'en chaque de ces point on est dans une boucle
mais on voit bien que pour le point en bleu...on est bien relié à 2 point tagués
à gauche et à droite...mais...on est pas dans une boucle

donc le fait d'être relié à 2 points tagués au moins ne veux pas dire que l'on soit
dans une boucle

[stendhal666]

Désolé j'ai eu beaucoup de travail et n'ai pas pu répondre bien vite.

J'ai l'impression que tu as changé les règles du jeu pour ton dernier graphe: si tu tagues le point bleu à ce moment-là, c'est que tu n'as pas construit le graphe à partir d'un point d'origine unique, non?

PS: Tes graphiques sont de plus en plus beaux.

à ce stade on devrait détecter une boucle
mais si on prend le principe : "il y a une boucle quand tous les points tagués sont liés à 2 points tagués"
on ne la trouve pas puisqu'en P1 on a qu'un seul lien (en couleur) avec P2

Bon en fait je crois qu'on ne se comprend plus. Là dans la construction du graphe tu dis:
on crée P1, puis ses voisins et covoisins, puis on va en P5. Mais comment passer de P1 à P5 directement? Cela veut dire qu'on ne passe pas par les voisins pour la création du graphe?

[deuzef68]

Désolé j'ai eu beaucoup de travail et n'ai pas pu répondre bien vite.

ne t'excuse pas on a tous des obligations toujours agréable de te lire

J'ai l'impression que tu as changé les règles du jeu pour ton dernier graphe:

non non je n'ai pas changé les règles...enfin celles du tout début oui...mais je l'ai précisé...
j'ai juste simplifié pour éviter de tout dessiner...et que cela prenne une heure à le faire
j'ai viré tous les pts voisins non tagués et le co-voisins...
sinon le schéma aurait eu pas mal de points...

si tu tagues le point bleu à ce moment-là, c'est que tu n'as pas construit le graphe à partir d'un point d'origine unique, non?

non je l'ai bien construit dans l'ordre...et il est sur que le pt bleu n'est pas tagué en dernier...
mais à chaque fois que tu tagues un pt il faut vérifier qu'il y a une boucle...donc effectivement on a déjà vérifié le point bleu avant
au moment ou on l'a tagué...mai on vérifie aussi la suite après...quand on crée la boucle de droite...

et lorsque l'on referme la boucle de droite, on teste tous les pts tagués et forcément on re-teste le pt bleu...qui lui à ce moment là à 2 liens avec des pts tagués...
il faut pourtant l'exclure...
donc la solution de dire...fait partie de la boucle les pts qui ont 2 (ou plus) liens avec des pts tagués ne suffit pas...

PS: Tes graphiques sont de plus en plus beaux.

merci...pourtant ils sont tout simples
j'ai créé tous les éléments au départ dans visio..les différents types de pts et les différents axes...et je ne fait que des copier-coller
je n'ai pas de mérite

Bon en fait je crois qu'on ne se comprend plus. Là dans la construction du graphe tu dis:
on crée P1, puis ses voisins et covoisins, puis on va en P5. Mais comment passer de P1 à P5 directement? Cela veut dire qu'on ne passe pas par les voisins pour la création du graphe?

ben il ont veux que ça fonctionne avec le calculs des axes...
on ne peux plus construire directement Pn+1 à partir de Pn...mais passer par Cp

on part de P1 et on fait C1,C2,C3....puis de ces pts on fait P2,P3,P4
donc les liens "REELS" ne sont pas directement entre P1 et P2 (et les autres)
MAIS... on peux VISUELLEMENT...voir une boucle (ou pas) si on crée VISUELLEMENT des liens entre les pts tagués qui sont voisins...

d'ailleurs comme j'ai dit...un peu plus haut...quand je décris le saute mouton
on fait une recherche...
on trouve les pts tagué voisins et on fait une liste (à part de la construction bien sûr) des pts tagués voisins...liés VISUELLEMENT entre eux

[deuzef68]

Bon en fait je crois qu'on ne se comprend plus. Là dans la construction du graphe tu dis:
on crée P1, puis ses voisins et covoisins, puis on va en P5. Mais comment passer de P1 à P5 directement? Cela veut dire qu'on ne passe pas par les voisins pour la création du graphe?

j'ai sauté quelques étapes alors je reprends
donc j'ai construit tout le graphe comme ci-dessous


depuis ce graphe j'ai extériorisé la liste des point qui visuellement sont tagués et je les ai lié
car au final ce ne sont que eux que l'on a besoin
ne sont lié que les pts tagué qui ont de co-voisins en communs suivant le critère expliqué auparavant


C'est plus clair ?

[stendhal666]

non je l'ai bien construit dans l'ordre...et il est sur que le pt bleu n'est pas tagué en dernier...
mais à chaque fois que tu tagues un pt il faut vérifier qu'il y a une boucle...donc effectivement on a déjà vérifié le point bleu avant
au moment ou on l'a tagué...mai on vérifie aussi la suite après...quand on crée la boucle de droite...

Au moment où le point bleu est tagué, il n'a qu'un voisin tagué, à sa gauche, donc il ne génère pas de boucles
Et au moment de la clôture de la boucle de droite, il y aura forcément un voisin d'écart avec le point bleu.
Donc le principe de départ: "une boucle est formée au moment où on tague un sommet qui a au moins deux sommets voisins déjà tagués" reste bien valable. Il faut bien voir que ce principe est valable au moment de la création du graphe mais ne l'est plus quand on lève le crayon et qu'on regarde l'oeuvre finie.

Ce qui m'amène à ma question: au fait, quel est ton objectif ultime avec la construction de ce graphe?

[deuzef68]

Au moment où le point bleu est tagué, il n'a qu'un voisin tagué, à sa gauche, donc il ne génère pas de boucles

On est en phase tout les 2... au moment ou on tague le bleu... le bleu ne fait pas partie d'un boucle... il n'a qu'un lien avec un point tagué

Et au moment de la clôture de la boucle de droite, il y aura forcément un voisin d'écart avec le point bleu.

à chaque fois qu'on tague...on liste tous les pts tagué et on cherche la ou les boucles
mais quel serait l'algorithme pour déterminer si il y a une boucle et quelle est la boucle...
pour l'instant on ne l'a toujours pas énoncé...

Donc le principe de départ: "une boucle est formée au moment où on tague un sommet qui a au moins deux sommets voisins déjà tagués" reste bien valable.

euh...hé ben pas si sûr
ce qui est sûr...
un pt tagué peux avoir 0,1,2 ou 3 liens, visuel pas ceux pour créer le graphe bien sûr, avec des pts tagués
0 il n'y a qu'un seul cas le 1er point au 1er tour donc ça ne compte pas

on peut lever le crayon pour taguer un pt mais tel une racine ou un arbre on crée forcément à partir de cette racine
il n'y a pas de génération spontanée loin de l'arbre ce serait un cas avec 0 lien visuel...à par le 1er point au 1er tour c'est impossible...
et une branche peut rejoindre une autre branche...mais à ce moment là le pt de jonction à au moins 2 liens...mais ça ne forme pas forcément une boucle

Ce qui m'amène à ma question: au fait, quel est ton objectif ultime avec la construction de ce graphe?

on est curieux c'est pour un moteur de jeux... tu joues contre l'ordinateur... et c'est pour le "système de réflexion" on va dire

[deuzef68]

Bon...alors ...après avoir pas mal cogité et dessiné... émis des hypothèses
je pense qu'effectivement... au moment où on tague le pt si on trouve plus d'un lien visuel avec des pts tagués
alors...mais seulement lui...on peut dire qu'il fait partie d'au moins une boucle...c'est le seul pt dont on soit sûr...

par contre pour trouver la ou les boucles...pas facile...

exemple
si on part de l'étape ci-dessous


dont on peut extraire les pts tagués pour plus de facilité comme ci-après


à l'étape suivante on peut arriver à

dernier pt tagué en bleu


dont on peut extraire les pts tagués pour plus de facilité comme ci-après


effectivement le pt bleu est "lié" à plus d'un pt tagué... mais quelle est la boucle... et combien il y en a t'il ?
2 ? 3 ? 4 ? plus ?
moi j'en vois 3 : la boucle de gauche, celle de droite et la grande qui englobe tout

mais un algo combien pourrait-il en trouver ?

si on part du pt bleu... le seul dont on sait maintenant qu'il fait partie d'une boucle.. 3 chemins partent...
chemin vers le bas à gauche, chemin vers le bas à droite, et chemin vers le haut...

en haut on bifurque...vers la gauche et la droite...
et si on est parti en bas à gauche ou à droite...en remontant en haut on retombe à la bifurcation du haut
donc des 3 départs on se retrouve à trouver 2 + 2 + 2 = 6 boucles...
certes il y a doublons...mais il faut alors pouvoir les éliminer...

et encore là c'est relativement facile...imagine quand tu as 5 hexagones ou plus collé les uns aux autres
le nombre de possibilité va devenir exponentiel

[stendhal666]

C'est ce que je te disais il y a quelques messages de cela:
- à la construction, on peut détecter les boucles simples: si on tague un point dont deux voisins sont tagués, nb_boucles = nb_boucles + 1
"" trois "" , nb_boucles = nb_boucles + 2
- mais cela ne permet pas de détecter toutes les boucles: quand deux boucles sont contiguës par au moins deux sommets, on a une boucle supplémentaire, quand trois boucles sont contiguës deux par deux par deux sommets, on a 3 boucles supplémentaires, etc.
- pour éviter un algorithme exponentiel, je proposais de s'appuyer sur la propriété des cycles eulériens, qui correspondent à la définition de la boucle, que tous leurs sommets sont de nombre pair:
a) quand un sommet est de degré 1, il marque la fin d'un chemin. Il faut donc nettoyer tous les sommets de degré 1 pour avoir des candidats au titre de boucle
b) quand un sommet est de degré 3, c'est le cas difficile. On peut observer, sur un graphe "nettoyé" des sommets de degré 1:
1. un sommet de de degré 3 est nécessairement relié à au moins un autre sommet de degré 3.
2. Chaque paire de sommets de degré 3 peut signifier 2 choses: soit deux boucles simples sont reliées par un segment; si on efface le segment, on se retrouve avec 2 boucles séparées / soit deux boucles sont contiguës et forment également une boucle extérieure; si on efface le segment qui sépare les deux boucles simples, on se retrouve avec une boucle extérieure qui a bien la propriété des cycles eulériens.

[deuzef68]

- pour éviter un algorithme exponentiel, je proposais de s'appuyer sur la propriété des cycles eulériens,

j'ai regardé des anciens cours cette nuit... je suis justement sur les cycles eulériens et autre

qui correspondent à la définition de la boucle, que tous leurs sommets sont de nombre pair:
a) quand un sommet est de degré 1, il marque la fin d'un chemin. .

on est d'accord

Il faut donc nettoyer tous les sommets de degré 1 pour avoir des candidats au titre de boucle
b) quand un sommet est de degré 3, c'est le cas difficile. On peut observer, sur un graphe "nettoyé" des sommets de degré 1:
1. un sommet de de degré 3 est nécessairement relié à au moins un autre sommet de degré 3.

oui... je te suis toujours

2. Chaque paire de sommets de degré 3 peut signifier 2 choses: soit deux boucles simples sont reliées par un segment;

comme ça

si on efface le segment, on se retrouve avec 2 boucles séparées

soit deux boucles sont contiguës et forment également une boucle extérieure;

comme ça

si on efface le segment qui sépare les deux boucles simples, on se retrouve avec une boucle extérieure qui a bien la propriété des cycles eulériens.

Ok c'est clair mais ça ne me dis pas ce qu'il faudrait comme algo...
je vais continuer à potasser de la doc
j'ai regardé du côté des parcours en profondeur...
en partant du pt bleu... tant qu'on arrive pas au même pt on continue...si on arrive sur un pt de degré un on élimine ce bout de branche
à chaque bifurcation on fait 2 appels pour faire 2 sous recherches...
à chaque fois on marque les pts sur lesquels ont est passé... de façon à ne pas y repasser
bon on trouve toutes les boucles...même trop puisqu'en fait on trouve aussi la boucle dans l'autre sens
mais c'est sur que dans ce cas on trouve facilement pour les cas simples

donc je regarde encore des docs...eurélien ou autre


question subsidiaire
Dans un schéma comme ci-dessous tu vois combien de boucles toi ?


moi j'en vois 7

[stendhal666]

Oui, tout à fait!
Non c'est clair que ça ne fait pas un algorithme.
Mais je pense qu'il est possible d'en trouver un en effaçant selon un certain ordre une partie des arêtes partant d'une paire de sommets de degré 3.

[deuzef68]

Oui, tout à fait!
Non c'est clair que ça ne fait pas un algorithme.
Mais je pense qu'il est possible d'en trouver un en effaçant selon un certain ordre une partie des arêtes partant d'une paire de sommets de degré 3.

il y a forcément un algo... on est pas les premiers à chercher des boucles dans les graphes

par contre... quand tu dis "effacer"... tu veux dire mettre de côté ou carrément virer de la liste...
effectivement tu pourrais partir des point de degré 1...l'effacer puis remonter...le précédent...
étant de degré 1 maintenant peux aussi être effacé...jusqu'à un degré 3...;

tu pensais à ça ?

dans le schéma

on recherche les pts de degré 1...c'est le bleu ici...
on le supprime... on arrive donc à


en continuant...on le supprime pour arriver au final après plusieurs étapes à


et là comme ici tous les pts sont de degré 2...peut on oser affirmer qu'il n'y a qu'une boucle ?
je pense que oui...

[stendhal666]

J'ai fait quelques recherches sur les algorithmes de formulation proche: la mauvaise nouvelle c'est que le problème est np-complet... Néanmoins ils portent sur des graphes dont on ne connaît aucune propriété. Donc il reste de l'espoir.

Oui, l'idée en nettoyant les sommets de degré 1 c'est de ne garder que des boucles + l'éventuelle connexion entre elles.
Pour les sommets de degré 3, ils marchent par paire:

A C
\ /
B
|
E
/ \
D F

L'idée est de "masquer" (donc provisoirement) 3 arêtes de la figure successivement: (AB), (BE), puis (EF). Entre chaque masque, on nettoie les sommets de degré 1 et on a une boucle s'il ne reste que des sommets de degré 2.
ça marche bien pour les figures composées de deux boucles et qui, pour certaines, constituent également une troisième boucle qui contient les deux plus petites (graphe qui ressemble au symbole de l'infini)
Dès qu'on passe à un nombre de boucles supérieur, en revanche, cela ne suffit plus. Il faudrait trouver une façon de généraliser. Par exemple, pour la figure à 7 boucles, on a du mal à ne pas en compter deux fois certaines.

[deuzef68]

J'ai fait quelques recherches sur les algorithmes de formulation proche: la mauvaise nouvelle c'est que le problème est np-complet... Néanmoins ils portent sur des graphes dont on ne connaît aucune propriété. Donc il reste de l'espoir.

c'est bien tu es optimiste

Oui, l'idée en nettoyant les sommets de degré 1 c'est de ne garder que des boucles + l'éventuelle connexion entre elles.

oui ça éclairci

Pour les sommets de degré 3, ils marchent par paire:

tout à fait... mais pas facile de trouver la paire...si l'hexagone est "entouré" d'autres boucles...

A C
\ /
B
|
E
/ \
D F

L'idée est de "masquer" (donc provisoirement) 3 arêtes de la figure successivement: (AB), (BE), puis (EF). Entre chaque masque, on nettoie les sommets de degré 1 et on a une boucle s'il ne reste que des sommets de degré 2.
ça marche bien pour les figures composées de deux boucles et qui, pour certaines, constituent également une troisième boucle qui contient les deux plus petites (graphe qui ressemble au symbole de l'infini)
Dès qu'on passe à un nombre de boucles supérieur, en revanche, cela ne suffit plus. Il faudrait trouver une façon de généraliser. Par exemple, pour la figure à 7 boucles, on a du mal à ne pas en compter deux fois certaines.

ben à la limite ce n'est pas si grave de faire des doublons dans la recherche tant qu'on n'oublie aucune boucle

on pourrait toujours après avoir trouvé toutes les boucles les comparer...

car par exemple P1-P2-P3-P4-P5-P6-P1 et P6-P1-P2-P3-P4-P5-P6 sont identiques
on devrait pouvoir en éliminer une sur 2 en les "comparant"
tu enlèves l'élément final à chaque... et tu fais une comparaison...
P1-P2-P3-P4-P5-P6 <-?-> P6-P1-P2-P3-P4-P5
si identique tu en vires un...sinon tu prends le premier élément de la première boucle et tu le colles à la fin
P1-P2-P3-P4-P5-P6 devient P2-P3-P4-P5-P6-P1 que tu compares à P6-P1-P2-P3-P4-P5
et ainsi de suite en faisant un tour complet...

mais tu dois aussi gérer les parcours en inverse
comparer P1-P2-P3-P4-P5-P6 et P6-P5-P4-P3-P2-P1 qui sont aussi la même boucle

ou alors pour faire plus vite...de la liste des boucles trouvées
tu prends la première...et tu génères tous les cas
de boucle dérivant de cette boucle... aussi bien dans le sens direct que dans l'inverse...
et de cette boucle et ces dérivées (il n'y en aura pas 300 000 générées )...tu les compares aux autres boucles de la liste...
si au final ça ne matche pas.... la boucle est unique sans doublon (ou triplet va savoir)

[deuzef68]

imaginons que l'on parte du schéma suivant
on a auparavant déjà enlevé tous les pts de degrés 1...itérativement

on trouve 2 pts de degré 3

1) on prend un des 2 pts de couleur le bleu par exemple
et on enlève un lien sur les 3

on enlève le ou les pts de degré 1 jusqu'à ce que l'on ne puisse plus le faire
on arrive donc à ce schéma

tous les pts restants sont de degré 2...et sont lié entre eux donc on a une boucle

on revient en 1) au début et on enlève le 2ème lien

on enlève itérativement les pts de degré 1...là il n'y en a pas... les pts restants sont de degrés 2... et sont lié entre eux donc on a une autre boucle




on revient en 1) au début et on enlève le 3ème lien

on enlève le ou les pts de degré 1 jusqu'à ce que l'on ne puisse plus le faire
on arrive donc à ce schéma

tous les pts restants sont de degré 2...et sont liés entre eux donc on a une boucle

on en a fini avec le pt bleu on passe au pt orange

le traitement est identique
1er lien
2ème lien
et 3ème lien
on retrouve les même boucles

[stendhal666]

Oui c'est bien l'idée! parfaitement illustrée comme d'habitude!
Mais il me semble qu'il serait mieux de masquer une arête de l'autre sommet. Je m'explique:

- les paires de sommets de degré 3 qui se correspondent sont reliées entre elles par un axe (un segment constitué d'une ou plusieurs arêtes dans la même direction)
- les arêtes à masquer sont:
1) une arête qui n'appartient pas à cet axe
2) la ou les arêtes qui constituent l'axe
3) l'arête parallèle à la première appartenant à l'autre sommet
- du coup (et même si ça revient un peu au même à ce stade), on ne compte pas deux fois la même boucle, mais une fois chaque boucle.
- l'intérêt c'est qu'on pourrait faire un appel récursif

compte-boucles (liste_sommets_reliés):
-si liste_sommets_reliés forme une boucle: retourner 1
-sinon
- on applique la technique des masques pour obtenir plusieurs listes de sommets
- on applique compte_boucle à chaque nouvelle liste de sommets après les avoir nettoyés
- et on retourne la somme des résultats de compte-boucles

[deuzef68]

Oui c'est bien l'idée! parfaitement illustrée comme d'habitude!

merci on ce fait plaisir comme on peut

Mais il me semble qu'il serait mieux de masquer une arête de l'autre sommet. Je m'explique:

- les paires de sommets de degré 3 qui se correspondent sont reliées entre elles par un axe (un segment constitué d'une ou plusieurs arêtes dans la même direction)
- les arêtes à masquer sont:
1) une arête qui n'appartient pas à cet axe
2) la ou les arêtes qui constituent l'axe
3) l'arête parallèle à la première appartenant à l'autre sommet

pas idiot... mais tu fais l'hypothèse que la parallèle n'appartient pas à la même boucle
mais je pense avoir des contre exemples

- du coup (et même si ça revient un peu au même à ce stade), on ne compte pas deux fois la même boucle, mais une fois chaque boucle.
- l'intérêt c'est qu'on pourrait faire un appel récursif

exactement j'ai eu la même réflexion... cette nuit j'ai fait une simulation (insomnie quand tu nous tiens )...pas encore totalement complète
mais dès que je l'ai finie je la poste

compte-boucles (liste_sommets_reliés):
-si liste_sommets_reliés forme une boucle: retourner 1
-sinon
- on applique la technique des masques pour obtenir plusieurs listes de sommets
- on applique compte_boucle à chaque nouvelle liste de sommets après les avoir nettoyés
- et on retourne la somme des résultats de compte-boucles

effectivement c'est quasiment ce que j'ai simulé

[deuzef68]

- les paires de sommets de degré 3 qui se correspondent sont reliées entre elles par un axe (un segment constitué d'une ou plusieurs arêtes dans la même direction)
- les arêtes à masquer sont:
1) une arête qui n'appartient pas à cet axe
2) la ou les arêtes qui constituent l'axe
3) l'arête parallèle à la première appartenant à l'autre sommet

dans ce cas ci tu ferais comment ?

le lien en bas à droite du point vert appartient à la même boucle que le lien en haut à gauche du point bleu

idem pour en bas à gauche du vert et en haut à droite du bleu

- l'intérêt c'est qu'on pourrait faire un appel récursif

Bon finis la simulation... elle est assez complète et tu vas te régaler les yeux

c'est tout visuel...avec une codification par idéogramme
la flèche verticale avec le "=" c'est pour dire qu'on peut lancer les autres traitement, listé en dessous, en récursif
et pourquoi pas en parallèle

la flèche vers la droite avec le "D" c'est pour dire qu'on "delete" un lien

la flèche vers la droite avec le "C" c'est pour dire qu'on "Compacte" le schéma en supprimant les pts de degré 1

la flèche rouge... on en déduit que...

les pts de couleur avec les numéros (1,2 ou 3) plus la flèche coudée vers la droite
c'est pour dire que l'on repart du lien 1,2 ou 3 du pt de couleur

tout simple...

bonne visu