Triangulation de graphe
Un article de Wikipédia, l'encyclopédie libre.
 |
Cet article est une ébauche concernant les mathématiques.
Vous pouvez partager vos connaissances en l’améliorant. (Comment ?).
|
La triangulation de graphe est un problème intervenant en théorie des graphes.
 |
| Triangulation d'un graphe |
Sommaire |
[modifier] Définition
Un graphe est triangulé si tout cycle de longueur supérieur à 3 admet une corde. On travaille sur un graphe non orienté. La triangulation de graphe consiste à rendre un graphe non triangulé, 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.
[modifier] Algorithme
soit G un graphe non orienté
soit size la taille du graphe
tantque size != 0
sommet <- Choisir un Sommet
Relier les voisins de sommet
Marquer(sommet)
[modifier] Amélioration et Heuristique
L'algorithme ci-dessus est extrêmement simpliste. Il consiste à parcourir tous les sommets, de relier deux à deux les voisins du sommet, puis de le "supprimer" du graphe. Ceci pour tous les sommets. Complexité en O(n) sans compter le temps du choix du sommet. Cet algorithme ne trouve en rien une triangulation optimale (au sens du nombre d'arêtes ajoutées). Il permet juste de trouver une triangulation du graphe.
[modifier] Choix de l'heuristique
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.
[modifier] Heuristique avec score
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.
score = deg * deg − 2 * nombreVoisinRelie
Avec deg égal au degré du sommet et nombreVoisinRelie le nombre de voisins reliés deux à deux du sommet en question.
[modifier] Heuristique spécialisée
Bien que l'heuristique avec score se révèle efficace, il est souvent nécessaire de développer ses propres heuristiques en fonctions du graphe. Par exemple en prenant en compte ses particularités symétriques.
[modifier] Tester si un graphe est triangulé
L'algorithme le plus utilisé pour vérifier si un graphe est triangulé est un parcours en largeur lexicographique (dit Lex-BFS). Cet algorithme commence par numéroter chacun des sommets selon l'ordre défini dans l'algorithme qui est linéaire, O(m + n).
[modifier] Algorithme
Entrée Un graphe orienteSortie La numerotation lambda des sommets de G Pour sommet
etiquette(x)=0 FinPour Pour i=n jusqu'a 1 Choisir un sommet non numerote
d'etiquette lexicographique maximum
Pour voisin non numerote y de x Ajouter i a etiquette(y) FinPour FinPour
 |
| LexBfs sur un graphe |
