Triangulation de graphe

On travaille sur un graphe non orienté. Un graphe est triangulé si tout cycle de longueur supérieure à 3 admet une corde. On dit aussi qu'il est cordal.

La triangulation d'un graphe non triangulé consiste à le rendre triangulé. La triangulation d'un graphe n'est pas unique et la recherche de la triangulation optimale (au sens du nombre d'arêtes ajoutées minimum) est un problème NP-Complet.

On peut constater que l'efficacité de l'algorithme dépend de la manière de prendre les sommets. On peut donc naturellement faire intervenir différentes heuristiques pour améliorer grandement le résultat.

Le score est calculé en fonction du nombre de voisins d'un sommet et du nombre de ses voisins reliés deux à deux. On essaye donc à chaque fois de prendre le sommet où le nombre d'arêtes à rajouter est le plus faible.

${\displaystyle {\text{score}}=\deg \times \deg -2\times {\text{NombreDeVoisinsRelies}}}$

Avec deg égal au degré du sommet et nombreVoisinRelie le nombre de voisins reliés deux à deux du sommet en question.

Bien que l'heuristique avec score se révèle efficace, il est souvent nécessaire de développer ses propres heuristiques en fonction du graphe. Par exemple en prenant en compte ses particularités symétriques.

Entrée Un graphe orienté ${\displaystyle G=(V,\varepsilon )}$ 
Sortie La numérotation lambda des sommets de G
Pour   sommet ${\displaystyle x\ \in \ V}$
    étiquette(x)=0
FinPour
Pour i=n jusqu'à 1
    Choisir un sommet non numéroté ${\displaystyle x\in V}$ d'étiquette lexicographique maximum
    ${\displaystyle \lambda (i)\leftarrow x}$
    Pour voisin non numéroté y de x
      Ajouter i à étiquette(y)
    FinPour
FinPour

LexBfs sur un graphe