Algorithme à usage général pour la triangulation d'un graphe non orienté?

Question

Je suis en train de jouer avec la mise en œuvre d'un algorithme d'arbre de jonction pour la propagation de croyances sur un réseau bayésien. Je me bats un peu avec la triangulation du graphe pour que les arbres de jonction puissent se former.

Je comprends que trouver la triangulation optimale est NP-complet, mais pouvez-vous me désigner un algorithme général qui aboutit à une triangulation «assez bonne» pour des réseaux bayésiens relativement simples? Ceci est un exercice d'apprentissage (passe-temps, pas de devoirs), donc je ne me soucie pas beaucoup de la complexité de l'espace/temps tant que l'algorithme donne un graphe triangulé pour tout graphe non orienté. En fin de compte, j'essaie de comprendre comment fonctionnent les algorithmes d'inférence exacte avant même d'essayer d'effectuer une quelconque approximation.

Je bricoler en Python en utilisant NetworkX, mais toute description de pseudo-code d'un tel algorithme utilisant une terminologie typique de traversée de graphe serait précieuse.

Merci!

Answer 1

Si Xi est une variable possible (nœud) à supprimer puis,

• S (i) sera la taille de la clique créée par la suppression de cette variable
• C (i) seront les somme de la taille des cliques de la sous-graphe données par Xi et de ses nœuds adjacents

Heuristic:

Dans chaque cas, choisir une variable Xi parmi l'ensemble de variables possibles pour être dé effacé est avec S minimale (i)/C (i)

Référence: Heuristic Algorithms for the Triangulation of Graphs