Triangulation de graphe

Triangulation de graphe

La triangulation de graphe est un problème intervenant en théorie des graphes.

Triangulation d'un graphe
Triangulation d'un graphe

Sommaire

Définition

Un graphe est triangulé si tout cycle de longueur supérieure à 3 admet une corde. On travaille sur un graphe non orienté. 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.

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)

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.

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.

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.

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.

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).

Algorithme

Entrée Un graphe oriente G = (V,ε) 
Sortie La numerotation lambda des sommets de G
Pour   sommet x\ \in\ V
    etiquette(x)=0
FinPour
Pour i=n jusqu'à 1
    Choisir un sommet non numerote  x \in V d'etiquette lexicographique maximum
    \lambda(i) \leftarrow x
    Pour voisin non numerote y de x
      Ajouter i a etiquette(y)
    FinPour
FinPour



Tester si un graphe est triangulé
LexBfs sur un graphe

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Triangulation de graphe de Wikipédia en français (auteurs)

Игры ⚽ Нужна курсовая?

Regardez d'autres dictionnaires:

  • Triangulation d'un ensemble de points — Une triangulation d un ensemble de points P dans le plan est une triangulation de l’enveloppe convexe de P, tous les points de P formant alors des sommets de cette triangulation. Les triangulations sont un sous ensemble de graphes planaires… …   Wikipédia en Français

  • Triangulation de delaunay — Pour les articles homonymes, voir Delaunay. Une triangulation de Delaunay avec les cercles circonscrits visibles …   Wikipédia en Français

  • Graphe Gabriel — Graphe de Gabriel Un graphe de Gabriel est un graphe qui connecte un ensemble de point dans un plan Euclidien. Étant donné un ensemble S de points dans un plan, deux points P et Q de S sont connectés par une arête dans le graphe de Gabriel de S… …   Wikipédia en Français

  • Triangulation de Delaunay — Pour les articles homonymes, voir Delaunay. Une triangulation de Delaunay avec les cercles circonscrits en gris. En mathématiques et plus particulièrement en …   Wikipédia en Français

  • Triangulation de Pitteway — À gauche: Une triangulation de Pitteway. Chaque arrête de la triangulation de Delaunay, en noir, coupe son dual associé dans le diagramme de Voronoi, en pointillé bleu. À droite : une triangulation de Delaunay qui n est pas une triangulation …   Wikipédia en Français

  • Graphe de Gabriel — Un graphe de Gabriel est un graphe qui connecte un ensemble de point dans un plan euclidien. Étant donné un ensemble S de points dans un plan, deux points P et Q de S sont connectés par une arête dans le graphe de Gabriel de S si et seulement si… …   Wikipédia en Français

  • Triangulation (géométrie) — En géométrie, une triangulation est une partition d un objet en un ensemble de simplexes. En particulier dans le plan, une triangulation est composée de triangles. Une triangulation est un complexe simplicial. Une triangulation T d un ensemble X… …   Wikipédia en Français

  • Triangulation d'un polygone — En géométrie algorithmique, la triangulation d un polygone consiste à décomposer ce polygone en un ensemble (fini) de triangles[1]. Une triangulation d un polygone P est une partition de P en un ensemble de triangles qui ne se recouvrent pas, et… …   Wikipédia en Français

  • Delaunay triangulation — Triangulation de Delaunay Pour les articles homonymes, voir Delaunay. Une triangulation de Delaunay avec les cercles circonscrits visibles …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”