[..] Algorithme Graphe

[jcaspar]

B onjour à tous !

Je souhaiterais créer une petite application me permettant d'appliquer un algorithme sur un graphe. En tant qu'étudiant dans la théorie des graphes
je m'aperçois qu'il n'existe pas de véritable application à même de répondre à
un besoin pédagogique.

Serait il possible de créer une représentation d'un graphe en Autoit ?
avec des cercle portant un nom, une flèche reliant les deux avec une valeur
et ensuite appliqué un algorithme..( le but serait de pouvoir appliqué ultérieurement l'algorithme de son choix )

en l’occurrence voici l'algorithme qui m'intéresse

initialement tous les sommets sont non marqués
tant qu'il existe un sommet s non marqué ouvrir s
tant que cela est possible ouvrir une des deux instructions
ouvrir un sommet y non marqué s'il est adjacent à un sommet x ouvert
fermer un sommet x si tous les sommets adjacents sont ouverts ou fermés


Dans mon idée avec une première inputbox on demande le nombre de sommets
puis on demande les noms de chaque sommet... ensuite pour chaque sommet
quels sont les sommets adjacents. A partir de là il me semble possible de
dérouler l'algorithme.

Je vous remercie d'avance pour vos conseils et suggestions !

Jean-Marc

[jchd]

Jette un oeil là-dessus, tu peux éventuellement t'en inspirer. Par ailleurs es-tu certain de la formulation de ton algo ?

EDIT: ooups, j'suis pas cramé, je nage avec du 3G qui découillonne à mort.

[Tlem]

@jchd
Il manque le lien.

[jchd]

Je donne suite ici et j'affine mon opinion : ta formulation est imprécise, et même déconnante pour tout dire.

initialement tous les sommets sont non marqués
tant qu'il existe un sommet s non marqué ouvrir s
tant que cela est possible ouvrir une des deux instructions <-- "exécuter", non ?
ouvrir un sommet y non marqué s'il est adjacent à un sommet x ouvert
fermer un sommet x si tous les sommets adjacents sont ouverts ou fermés

A lire ça, on pourrait croire qu'un sommet est dans un des 4 états possibles: mo, mO, Mo, MO (m=non marqué, M=marqué, o=fermé, O=ouvert), avec un état initial mo (si on est bon prince car rien ne dit que les sommets sont initialement fermés). Mais comme aucune étape ne fait passer de l'état m à M, l'attribut "non marqué" est un invariant. On le sucre et on obtient :

(a) tant qu'il existe un sommet [fermé ?] s ouvrir s <=> while(true) ouvrir s [ça sent déjà bon la boucle infinie]
(b) tant que cela est possible exécuter une des deux instructions
(b1) ouvrir un sommet y s'il est adjacent à un sommet x ouvert <-- comment sont choisis x et y ? En rapport avec s ?
(b2) fermer un sommet x si tous les sommets adjacents sont ouverts ou fermés <-- les adjacents de s, de x ou ???

Puisque ce n'est pas précisé, je choisis d'essayer (b1) en premier dans la boucle (b)

Le seul cas où l'algo présenté ne boucle pas infiniment (hormis l'imprécision de (a)) est celui d'un nuage de points (N sommets sans aucune adjacence). Dans un tel cas, on ouvre les N 1-cliques (les N sommets) dans la boucle (a) puisque rien n'est à faire dans la boucle (b).
Sinon, pour tout sous-graphe connexe non vide, on va successivement ouvrir tous les sommets en faisant (a) (b) (b1) (b) (b1) ... puis on arrive à (b) (b2) qui ferme un sommet (tous les autres sont adjacents et ouverts). Et on repart dans la séquence (b), (b1) qui rouvre le sommet fermé par (b2) puis on fait (b) (b2) (b) (b1) (b) (b2) ... Boucle infinie en (b) !

Si on choisit d'essayer (b2) avant (b1) dans la boucle (b), on arrive à un résultat complètement différent.
pour tout sous-graphe connexe non vide, on fait (a) qui ouvre un sommet puis (b) (b2) qui le referme illico et nous ramène à l'état de départ. Boucle infinie en (a) !