Recherche d'un 4-realizer de l'ordre partiel d'incidence d'un hypergraphe 3-uniforme
Minirecherche - module de "Dessin de graphes"
(DEA de Algorithmique année 2002-03)
Auteur: Luca Castelli Aleardi
Instructions
La applet présente dans cette page (implementation en Java 1.1) permet de faire des calculs sur des petits exemples Posets d'hauteur 2, qui representent l'ordre d'incidence, d'un hypergraphe (dans notre cas 3-uniforme).
Remarque:
Le problème de determiner la dimension de cet ordre partiel, et en trouver un realizer, est probablement NP-complet. Pour cela on s'attend de pouvoir obtenir des solutions, en temps raisonnable, seulement pour des "petits" exemples de hypergraphe (avec un nombre limité de sommets et aretes).
La stratégie choisie pour résoudre notre problème est basée sur la méthode de "Resolution de Robinson", un utile assez efficace, dans certains cas, de "Deduction automatique".
Idée
Une calculé l'ordre d'incidence correspondant au graphe dessiné, on peut trouver un ensemble de "clauses" qui définissent une formule F de logique booléenne.
La satisfaisabilité de cette formule permet de etablir si l'ordre partiel d'incidence est au plus.
En cas de réponse positive, l'applet permet aussi de construire un 4-realizer de ce Poset, en utilisant la méthode de "Model Building": le 4-realizer est constitué de 4 extensions linéaires L1, L2, L3, L4.
Chacune de ces extensions linéaires est donnée par un ensemble de couples (i,j) telles que:
(i,j) appartient à L si et seulement si i<j
Opérations possibles pour l'utilisateur
Changement du nombre de sommets et aretes de l'hypergraphe (par default 3 et 2 respectivement
Construction du graphe biparti qui represente l'ordre partiel d'incidence (tracé avec le "mouse" sur la fenetre en haut à gauche): l'utilisateur peut connecter les "sommets" (points "en bas", numerotés de 1 jusqu'à "n") aux "aretes (points en haut, numerotés de n+1 jusqu'à "n+m")
Avec la touche "créer ordre" on peut, à partir du graphe dessiné, créer l'ordre partiel d'incidence, et l'ensemble de "clauses" qui décrivent le problème.
Finalement avec la touche "start resolution" on peut determiner si l'ensemble de clauses engendré est satisfaisable et donc la dimension de l'ordre partiel est au plus 4.
Attention: après tout changement des paramètres et/ou modification du graphe, il faut presser la touche "restart" pour reinitialiser l'applet.